가장 가까운 이웃을 해결하기위한 성능에 중요한 알고리즘

Question

우리는 x, y 쌍의 목록을 가지고 있습니다. 모든 쌍은 2D 공간상의 점을 나타냅니다. 이 목록에서 가장 가까운 점을 특정 점 xq, yq로 찾고 싶습니다. 이 문제에 가장 적합한 성능에 중요한 알고리즘은 무엇입니까? 점의 혀짤배기는 변하지 않을 것이다; 즉, 삽입 및 삭제를 수행 할 필요가 없습니다. 이 집합에서 대상 xq, yq 점의 가장 가까운 이웃을 찾고 싶습니다.

편집 1 : 모두에게 감사드립니다! Stephan202가 올바르게 추측 했으므로이 작업을 반복하고 싶습니다. 함수처럼. 목록이 반드시 정렬되지는 않습니다. (실제로 정렬 할 수있는 방법을 모르겠습니까? a와 y의 2 개 열의 기본 키가있는 테이블처럼? 그렇다면 도움이된다면 정렬 할 것입니다.)

목록을 기반으로 데이터 구조를 한 번 생성 한 다음 함수에서이 생성 된 데이터 구조를 사용합니다 (이 프로세스 자체가 관련되어있는 경우).

감사합니다. Jacob; KD-Tree 데이터 구조가 답이 될 수있는 좋은 후보자 인 것 같습니다. (관련성이 높은 결과가 나면 업데이트 할 것입니다.)

편집 2 :이 문제는 "가장 가까운 이웃"이라는 것을 발견했습니다.

편집 3 : 첫 번째 제목은 "공간 검색 및 공간 인덱싱을위한 알고리즘 검색 중 (최근 인접 항목)"이었습니다. 새로운 제목을 선택했습니다 : "가장 가까운 이웃을 해결하기위한 성능 - 중요 알고리즘". 초기 데이터에 삽입 및 삭제 작업을 수행하고 싶지 않고 가장 가까운 것을 새로운 포인트 (삽입하지 않을 예정)에 넣기를 원하기 때문에 KD 트리 작업을 선택했습니다. 모두에게 감사드립니다!

Answer 1

를 포함하는 섹션은 같은 부분에 포인트 인접 섹션으로 시작 수 하나 이상의 포인트에 가장 근접한 것을 찾으려한다면, 나무를 사용해야합니다.

나는 OpenCV 2.0과 같은 여러 패키지에서 쉽게 구현할 수있는 KD 트리를 권장합니다. 아니면 직접 구현할 수도 있습니다.

편집 : kd-tree 구현에 관한 질문이 있습니다. here - 유용 할 수 있습니다.

편집 : NN 검색에 KD 트리가 널리 사용되었습니다. :) 또한 대략적인 일치를 허용하려는 경우 Fast Library for Approximate Nearest Neigbor (FLANN)을 사용할 수 있습니다. FLANN 구현은 OpenCV 2.0에 있습니다.

대략적인 답변을 원하지 않으면 FLANN 매개 변수를 조정하여 전체 트리를 검색 할 수 있습니다.

Answer 2

Q (xq, yq)로부터 최소 거리를 찾기 위해 거리 공식을 사용하여 다른 모든 점을 반복합니다.

그러나 성능에 중요한 대답에 대한 충분한 정보를 제공하지 않았습니다.

예를 들어, Q가 매우 일반적인 점인 경우 Q까지의 거리를 계산하여 각 점에 저장할 수 있습니다. 이 점의 거대한 숫자가있는 경우

두 번째 예를 들어, 당신은 섹션으로 포인트를 구성하고 Stephan202가 언급 한 바와 같이하면 Q.

Answer 3

쿼리 포인트 (xq, yq)가 다양하고 목록에없는 경우 포인트 목록의 Voronoi diagram을 계산해야합니다.이것은 일련의 다각형 또는 "셀"(일부는 무한합니다)을 제공합니다. 각 다각형은 원래 목록에서 해당 셀의 "사이트"라고 부르는 지점에 해당합니다. 하나의 다각형 안에 완전히있는 모든 점은 원래 목록의 다른 사이트에있는 것보다 해당 다각형의 위치에 더 가깝습니다. 두 다각형 사이의 경계에있는 모든 점은 각 사이트에서 동등하게 떨어져 있습니다.

이제까지 다뤘 으면 어떤 폴리곤인지 쉽게 파악할 수 있어야합니다. 이것은 point location problem으로 알려져 있습니다.

정말 좋은 책은 Computational Geometry: Algorithms and Applications입니다. 그들은 Voronoi 다이어그램 계산과 사다리꼴 슬랩 방법으로 점 위치를 자세히 설명합니다.

직접 코딩하지 않으려면 에 CGAL과 같은 라이브러리를 사용하여 대부분의 작업을 수행하십시오. 이것은 아마도 KD 트리 응답에도 적용되지만, 구체적으로 알지는 못합니다.

Answer 4

spatial index이 필요합니다.

자신을 굴리는 경우 R-Tree 또는 Quad-tree 알고리즘을 선택하는 것보다 훨씬 나쁜 작업을 수행 할 수 있습니다.

Answer 5

나는 쿼드 트리로 갈 것입니다. 가장 단순한 공간 구조입니다. 2 차원에서 나는 일반적으로 kd-tree 대신 quadtree를 추천합니다. 왜냐하면 그것은 더 간단하고 빠르기 때문입니다. 치수가 많으면 메모리 소비량이 적지 만 2 차원의 경우에는 그 차이가 크지 않습니다.

좌표가 부동 소수점 형식 인 경우 최적의 최적화 기법이 있습니다. 쿼리에서 가장 가까운 점에 질문하는 지점이 포함 된 리프 노드를 먼저 찾아야합니다. 이렇게하려면 트리에서 루트에서 리프로 이동해야합니다. 각 반복에서 어떤 하위 노드를 밟아야할지 결정해야합니다. 노드 구조의 4 크기 배열에 하위 노드의 식별자/주소를 저장하십시오. 쿼리 알고리즘에서 포인트 좌표를 디지타이징합니다. 그런 다음 디지털화 된 포인트 좌표의 적절한 2 비트를 사용하여 배열을 인덱싱하는 것만으로 적절한 하위 노드를 찾을 수 있습니다. 디지타이징은 빠릅니다 : 간단한 static_cast를 사용하여 구현하십시오.

하지만 비트 연산을 사용하여 버그를 만들기 쉽기 때문에 먼저 최적화없이 쿼드 트리를 구현하십시오. 이러한 최적화가 없어도 여전히 가장 빠른 솔루션이 될 것입니다.