가장 가까운 XY 좌표 찾기

Question

2 차원 이미지에서 점을 얻었습니다. 주어진 그림에서 빨간색 점과 n 점의 집합은 파란색 점 (x1, y1) ... (xn, yn)을 원합니다. 모든 점을 시도하는 것보다 (x0, y0)에 가장 가까운 점을 찾는 것. 최상의 솔루션을 원합니다. 비슷한 수업을 함께 나눠 주시면 감사하겠습니다.

Answer 1

우리가 제안 할 수있는 대부분의 솔루션은 조금 더 많은 지식에 달려 있습니다. 나는 사지에 나가서 이미 짧은 시간에 알지 못한다면 말하려고합니다. 나는. 수만개의 파란색 점이 있거나 짧은 시간에 수천 개의 계산을해야합니다. "Linear Search"은 충분히 도움이 될 것입니다.

실제 거리를 계산하지 마십시오. 제곱근을 계산하지 않고 "거리"로 사용하십시오.

다른 대부분의 방법은 더 복잡한 데이터 구조를 사용하여 점을 기하학적 배열과 관련하여 정렬합니다. 그러나 구현하기가 훨씬 어렵습니다.

Answer 2

이 많은 방법이 있습니다, 가장 일반적인 아마이 O (n)이되지 않도록 검색 속도를 높이기 위해 공간 분할의 형태를 사용하는 것. 자세한 내용은 위키 백과의 Nearest neighbor search을 참조하십시오.