2 차원 그래프에서 주어진 점에 가장 가까운 좌표를 찾는 알고리즘

Question

문제점 : 고정 된 파란색 좌표가 있습니다. 모든 파란색 점의 직교 거리를 얻고 그것의 최소한을 찾는

: 나는 가장 가까운 blue이 Here is the graph

이 내 방식이었다 좌표 주어진 red 좌표 찾고 싶어요.

float min=Float.MAX_VALUE; 
float temp=0; 
for(int i=0;i<cordinateList.size;i++){ 
    temp=cordinateList.get(i).x*cordinateList.get(i).x+cordinateList.get(i).y*cordinateList.get(i).y; 
    if(temp<min){ 
     min=temp; 
    } 
} 

내가해야 할 일 : cordinateList 모두 매우 비효율적이며 내 프로그램은 주어진 시간에 작업을 수행 실패에 너무 거리를 찾는 매우 크기 때문에

내 접근이 가능하지 않습니다 .

광산과 제안보다 효율적인 알고리즘이 있습니까?

업데이트 : 빨간색 점은 한 번에 하나씩 약 백만 번 있습니다. 파란색 점 목록은 고정되어 있습니다. 그래서 필자는 필요하다면 정렬과 같은 청색 포인트 목록에 초기 변경을 할 수 있다고 생각한다.

감사합니다.

Answer 1

간단히 포인트 목록이 있고이 작업을 한 번 수행해야하는 경우 더 효율적인 방법은 없습니다.

그러나 많은 다른 점에 대해이 절차를 여러 번 수행해야한다면 효율성을 향상시킬 수있는 방법이 있습니다. 예를 들어

• 생성하고 quadtreekd-tree 또는 데이터 구조를 사용하거나
• 생성하고 Voronoi diagram를 사용한다.

그러나 이러한 접근 방식은 심지어 휴식을 취하기 전에 여러 조회 (즉, 가장 가까운 지점 찾기 계산)를 통해 상환해야하는 설정 오버 헤드를 필요로합니다.

Answer 2

솔루션은 계층 적 트리입니다. 덴도 그램 또는 계층 적 클러스터. clusterfck JS 라이브러리를 사용할 수 있습니다.