2D에서 원격 포인트 찾기

StackOverflow https://stackoverflow.com/questions/1474793

  •  16-09-2019
  •  | 
  •  

문제

나는 무한 (잘, 이중 정밀) 2D 평면에 포인트 세트가 있습니다.

이 세트의 볼록한 선체가 주어지면 어떻게 내부에 입력 세트의 모든 지점에서 상대적으로 멀리 떨어진 볼록 선체의?

아래 이미지에서 검은 점은 원래 세트의 일부이며 해칭 영역은 반경 R로 "성장"하는 경우 모든 지점에 의해 취해진 공간을 나타냅니다.

오렌지 포인트는 내가 원하는 것의 예입니다. 그들이 모든 검은 점에서 상대적으로 멀리 떨어져있는 한 정확히 어디에 있는지는 중요하지 않습니다.

가장 먼 지점 검색 http://en.wiki.mcneel.com/content/upload/images/point_far_search.png

업데이트 : DelaUnay 알고리즘을 사용하여 큰 빈 삼각형을 찾는 것입니다.Delaunay 솔루션 http://en.wiki.mcneel.com/content/upload/images/delaunaysolutiontointernalfurthestpoints.png

도움이 되었습니까?

해결책

이것은 사용을 사용하여 해결할 수있는 문제의 좋은 예입니다. KD-Trees... 수치 레시피 3 번째 추가에는 좋은 음표가 있습니다.

상대적으로 고립 된 포인트 위치를 찾으려고한다면 ... 아마도 가장 큰 쿼드 요소의 중심이 좋은 후보자 일 것입니다.

복잡성은 kd-tree를 생성하기위한 O (n log^2 n) 일 것입니다 ... 쿼드 크기의 정렬 된 목록을 만드는 것은 O (n log n)입니다. 많은 포인트조차도 합리적으로 보입니다 (물론 요구 사항에 따라).

다른 팁

순진한 알고리즘입니다.

  1. 볼록 모양의 점 목록을 가져옵니다.
  2. 그 중 다른 지점까지의 최소 거리를 찾으십시오.
  3. 각각의 R 값으로 모든 점을 순위를 매깁니다
  4. 상단 X 포인트를 선택하십시오.

(2)의 경우, 이것을 반경 검색으로 생각하면 여전히 각 지점에서 서로 지점까지의 거리를 계산한다는 것을 의미합니다. 지점이 다른 지점의 주어진 반경 내에 있는지 여부를 찾는 것과 동일하기 때문입니다. 포인트 사이.

검색을 최적화하려면 공간을 그리드로 나누고 각 지점을 그리드 위치에 할당 할 수 있습니다. 그러면 위의 (2)에 대한 검색은 먼저 같은 사각형 내에서 확인합니다. 그리고 주변 8 사각형. 다른 지점까지의 최소 거리가 같은 사각형, 그 값을 반환하십시오. 그것이 8 중 하나에서 나오고 거리가 9 외부의 지점이 더 가까워 질 수있는 경우, 당신은 9 내에서 발견 된 것보다 가까운 것보다 9 외부의 그리드 위치의 다음 개요를 확인해야합니다. 린스/반복. .

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top