3
다음과 같은 개념을 사용하여 점의 '모양'을 요약 한 다각형 (또는 다각형 집합)을 생성 할 2D 점 집합이 있습니다. :'로컬 볼록 헐 (convex convex hulls)'의 합집합을위한 빠른 알고리즘
집합의 각 점에 대해 그 점의 반경 R 내의 모든 점의 볼록 선체를 계산합니다. 각 점에 대해 이렇게 한 후에는 최종 모양을 생성하기 위해 이러한 볼록한 껍질의 결합을 가져옵니다.
실제로 이러한 모든 볼록 선체를 구성하는 무차별 대입 접근법은 O (N^2 + R^2 log R)와 같습니다. 동일한 결과를 산출하는 알려진 알고리즘이 있습니까? 아니면 문제를 표현하는 다른 방법일까요?
참고 : 알파 모양을 알고 있습니다. 위에서 설명한 내용을 수행하는 알고리즘을 찾고 있습니다.
다음 해결책은 MATLAB에서 실험적으로 반증됩니다.
업데이트 : 제안 된 해결책이 있습니다.
命 令 : 점 집합의 Delaunay 삼각 측량을 취하고 R보다 큰 circumradius를 갖는 모든 삼각형을 제거한 다음 나머지 삼각형의 합집합을 취합니다.
나는 무엇을 성취하려고하는지 잘 모르겠습니다. 볼록한 것보다 포인트 클라우드의 모양을 더 잘 표현하는 볼록하지 않은 선체입니까? –
예, 맞습니다. 알파 모양과 비슷합니다 : http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html. 나는 내 방법으로 내가 작업하고있는 데이터에 대해 더 시각적으로 더 나은 결과 (IMO)를 생성한다는 것을 제외하고는. – James