볼록하지 않은 다각형 - convex hull 알고리즘을 사용하는 전처리

Question

convex ... convex 알고리즘을 사용하여 일부 ... 불규칙한 모양의 윤곽을 찾습니다. 내가

내가 사각형의 집합을 가지고 ... 내가 가지고있는 모양이 볼록 보장 할 수 없습니다, 나는 수 있도록하고 싶습니다 때문에 아마도 ...

하지만 충분하지 좋다 등고선 바깥쪽에있는 모든 점을 가져오고 - 등고선 점을 던지지 마십시오.

볼록 선체 알고리즘은 잘 작동 -하지만 오른쪽의 예처럼 작동, 그래서 윤곽에 대한 몇 가지 정보를 잃게됩니다. 이러한 알고리즘은 내가 외부 모서리를 유지하고, 단지 내부의 점을 제거, 왼쪽에있는 버전에 가까운 작동하는 무언가를 원하는

...

있습니까?

또는 모양 (다각형)을 볼록한 모양으로 나눌 수있는 방법이 있습니까? 그래서 볼록한 선체 알고리즘이 제대로 처리 할 수 ​​있습니까?

링크에서 링크까지 저는 Hertel-Mehlhorn 알고리즘과 같은 알고리즘을 설정하는 방법을 알아 내려고 노력해 왔습니다. 그러나 교차 선이이 상황에서 어떤 용도로 사용되는지 모르겠습니다 ...

제안 해 주셔서 감사합니다.

Answer 1

볼록하지 않은 다각형이 표시된대로 (예 : 사변형 요소 집합체) 경계면에있는 사변형의 모서리를 찾아야합니다.

"내부"모서리는 인접한 두 요소에 공통이지만 "외부"모서리는 하나의 요소에만 나타납니다. 이는 다음과 같은 간단한 알고리즘을 의미합니다.

edge_list = {} 
for (i = all elements in mesh) 
for (j = all edges in element(i)) 
    edge_list <- push jth edge of ith element 
endfor 
endfor 
edge_list <- sort 
edge_list <- remove_duplicates 

나머지 고유 한 가장자리는 다각형의 외부 윤곽을 형성합니다. 이 간단한 알고리즘은 O(N*log(N)) 시간에 실행됩니다.

복잡성을 O(N)으로 줄이면 가장자리 비교에 적합한 해시 테이블을 사용하여 복잡성을 개선 할 수 있습니다.