볼록하지 않은 폴리곤에 커다란 꼭지점 집합이있는 경우 어떻게하면 그 변을 찾을 수 있습니까?

Question

나는 (A라고하는) 정점 세트를 가지고 있으며이 경계 정점 세트가 모양의 윤곽이되도록 모든 경계 정점을 찾고 싶습니다.

A의 정점 중 상당수는 모양 안에 있기 때문에 중복되어 있으므로이 정점을 제거하고 싶습니다.

내 질문은 Best Algorithm to find the edges (polygon) of vertices과 비슷하지만 볼록하지 않은 다각형의 경우 작동해야합니다.

편집 : 설명 : 아래 이미지는 오목한 다각형입니다. 이것은 내가 볼록하지 않은 것을 의미합니다. 볼록 선체 알고리즘을 실행하면 폴리곤의 오목한 부분이 보존되지 않습니다. (오해하지 않는 한).

나는 내부와 다각형의 경계에 정점의 집합이 : 나는 그래서 세트를 줄이고 자 [[X1, Y1], [X2, Y2] ...] 정점은 모양의 테두리 윤곽입니다.

Answer 1

이 뜨거운 화제가 될 것 같다 .. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

이 논문은 최선을 것으로 보인다. Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Efficient generation of simple polygons for characterizing the shape of a set of points in the plane. Pattern Recognition v41, 3224-3236

Answer 2

설명이 다소 모호하지만 알고리즘 집합을 사용하여 Convex Hull 점을 구성 할 수 있습니다. 간단히 말해 볼록한 선체는 모든 정점에 고무 밴드를 넣으면 얻을 수있는 모양입니다. 2 차원 볼록 선체 알고리즘을 작성
몹시 어려운 일이 아니다 당신은 당신이되는이의 특별한 경우 인 것을 보인다 링크 qhull

(그 대답이 아니라 질문에 주어진 것처럼 그것을 몇 가지 라이브러리가 당신의 질문)

Answer 3

이것은 오래되었거나 어쩌면 버려진 질문이지만 생각해 보았습니다. 볼록 선체를 찾고 있지 않다면, 다각형 모양을 유지하기를 원하지만 선을 따라 "가장자리"사이에있는 점을 제거하십시오.

해결 방법은 인접한 점을 통과하여 첫 번째와 두 번째의 선형 기울기를 계산 한 다음 그 기울기 값을 저장하고 두 번째와 세 번째의 기울기를 계산하고 pt1-pt2의 기울기가 pt2-pt3의 경우, pt2는 라인을 형성하는데있어 중복되므로 제거 될 수있다. pt1로 돌아올 때까지 계속 반복합니다.

이렇게하면 오목한 모양이 유지되지만 무의미한 추가 점이 제거됩니다.