가장 가까운 이웃을 해결하기위한 최고의 성능 크리티컬 알고리즘
https://stackoverflow.com/questions/1639755
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
x, y 쌍 목록이 있습니다. 모든 쌍은 2D 공간의 지점을 나타냅니다. 이 목록에서 특정 지점 XQ, YQ에 가장 가까운 점을 찾고 싶습니다. 이 문제에 대한 최고의 성능 크리티컬 알고리즘은 무엇입니까? 포인트의 LISP는 변하지 않을 것입니다. 즉, 삽입 및 삭제를 수행 할 필요가 없습니다. 이 세트에서 Target XQ, YQ 포인트의 가장 가까운 이웃을 찾고 싶습니다.
편집 1 : 모두에게 감사합니다! Stephan202가 올바르게 추측했듯이, 나는 이것을 반복적으로하고 싶습니다. 함수처럼. 목록이 반드시 정렬되지는 않습니다 (실제로 어떻게 분류 할 수있는 방법을 이해하지 못하는가? 2 열 A와 y의 기본 키가있는 테이블처럼?
목록을 기준으로 데이터 구조를 한 번 구축 한 다음이 프로세스 자체가 관련된 경우이 생성 된 데이터 구조를 사용합니다 (이 프로세스 자체가 관련이있는 경우).
Jacob에게 감사합니다. KD-Tree 데이터 구조는 답변에 대한 좋은 후보 인 것 같습니다.
편집 2 :이 문제가 "가장 가까운 이웃"이라는 것을 알았습니다!
편집 3 : 첫 번째 제목은 "알고리즘 (공간 정체 및 공간-인덱싱) (가장 가까운 이웃)을 찾는 것"입니다. 새로운 제목을 선택했습니다. "가장 가까운 이웃을 해결하기위한 최고의 성능 크리티컬 알고리즘"을 선택했습니다. 초기 데이터에서 삽입 및 삭제 작업을 수행하고 싶지 않기 때문에 가장 가까운 데이터만으로 새로운 지점 (삽입되지 않을 것임)을 원하기 때문에 (현재) KD-Trees 작업을 선택했습니다. 모두에게 감사합니다!
해결책
Stephan202가 지적했듯이, 한 지점 이상에 가장 가까운 경기를 찾을 계획이라면 나무를 사용해야합니다.
KD-Tree를 추천합니다. opencv 2.0. 또는 직접 구현할 수 있습니다!
편집하다: KD-Tree 구현에 대해 질문했습니다 여기 - 유용 할 수 있습니다.
편집하다: KD -Trees는 NN 검색에 성공적으로 널리 사용되었습니다 :) - 또한 대략적인 일치를 기꺼이 수락하려면 사용할 수 있습니다. 가장 가까운 Neigbor (Flann)를위한 빠른 도서관. Flann 구현이 있습니다 opencv 2.0.
대략적인 답변을 원하지 않으면 Flann 매개 변수를 조정하여 전체 트리를 검색 할 수 있습니다.
다른 팁
쿼리 포인트 (xq, yq)가 다양하고 목록이 없으면 Voronoi 다이어그램 포인트 목록의. 이것은 당신에게 다각형 또는 "세포"세트를 줄 것입니다 (일부는 무한). 각 다각형은 해당 셀의 "사이트"라고하는 원래 목록의 점에 해당합니다. 하나의 다각형 내부에있는 지점은 원래 목록의 다른 사이트보다 해당 다각형의 사이트에 더 가깝습니다. 두 다각형 사이의 경계의 모든 지점은 각 사이트에서 동일하게 먼 곳에 있습니다.
당신이 그 멀리서 얻은 후에는 어떤 다각형을 파악할 수있는 쉬운 방법이 필요합니다. 이것은 포인트 위치 문제.
이런 종류의 정말 좋은 책은 계산 형상 : 알고리즘 및 응용 프로그램. 그들은 보로 노이 다이어그램 계산과 지점 위치의 사다리꼴 슬래브 방법을 자세히 논의합니다.
코드를 직접하고 싶지 않으면 안되는 경우 도서관과 같은 도서관 cgal 그것은 당신을 위해 대부분의 일을 할 것입니다. 이것은 아마도 KD-Tree 답변에도 적용되지만 구체적으로는 모릅니다.
나는 쿼드 트리와 함께 갈 것이다. 가장 단순한 공간 구조입니다. 2 차원에서는 일반적으로 KD-Tree 대신 Quadtree를 권장합니다. 더 간단하고 빠르기 때문입니다. 차원 수가 높으면 단점은 메모리 소비량이 많지만 2 차원의 경우 차이가 중요하지 않습니다.
좌표가 부동 소수점을 입력하면 좋은 최적화 트릭이 있습니다. 쿼리에서 먼저 가장 가까운 지점이 묻는 지점을 포함하는 리프 노드를 찾아야합니다. 이렇게하려면 뿌리에서 잎까지 나무에 들어가야합니다. 하위 노드의 식별자/주소를 노드 구조의 4 크기 배열에 저장하십시오. 쿼리 알고리즘의 포인트 좌표를 디지털화합니다. 그런 다음 디지털화 된 점 좌표의 2 비트로 배열을 색인화하여 적절한 서브 노드를 찾을 수 있습니다. 디지털화는 빠릅니다 : 간단한 static_cast로 구현하십시오.
그러나 먼저 비트 작동으로 버그를 만들 수 있기 때문에 최적화없이 쿼드 트리를 구현하십시오. 이 최적화가 없어도 여전히 가장 빠른 솔루션이 될 것입니다.
Q (xq, yq)에서 최소 거리를 찾기 위해 거리 공식을 사용하여 다른 모든 지점을 반복하십시오.
그러나 성능에 대한 답변을위한 충분한 정보를 제공하지 않았습니다.
예를 들어, Q가 매우 일반적인 지점 인 경우 Q까지의 거리를 계산하고 각 지점에 저장할 수 있습니다.
두 번째 예, 수많은 포인트가있는 경우 점을 섹션으로 구성하고 동일한 섹션에서만 점으로 시작하고 Q가 포함 된 섹션의 인접 섹션으로 시작할 수 있습니다.
