다각형의 윤곽 구축 ​​(특히 삼각 측량)

Question

삼각형 만 형성된 2D 다각형의 윤곽을 구성하는 방법은 구멍이있을 수 있으며 외부 윤곽은 오목/볼록 할 수 있으며 구멍도 오목/볼록 할 수 있습니다.

에서 무엇을 나는 여기서 읽고있다 그것은 바로 삼각 측량 문제의 역수 인 것 같습니다. 이러한 유형의 문제를 처리하는 기사를 알고 있습니까?

Octrees/Quadtree가 이것과 관련이 있습니까?

Answer 1

나는 당신이 "채워진"삼각형을 구성하는 3 점 세트의 형태로 데이터를 가지고 있다고 생각합니다.이 삼각형은 가장자리를 따라 인접 해 있으며, 완전한 모양의 모서리가 될 모든 정점은 또한 모든 삼각형의 정점입니다. 이 지점을 만지고 있습니다. 그런 다음 두 배가되지 않는 모든 가장자리를 찾아야합니다. 즉, 인접한 두 개의 삼각형에 속하지 않습니다.

Answer 2

삼각형 세트를 나타내는 토폴로지 데이터 구조를 만들어 문제를 해결 한 다음 해당 구조를 사용하여 경계에있는 삼각형 가장자리를 순서대로 반복합니다.

예를 들어, 하프 에디드 데이터 구조를 만들 수 있습니다. 경계에도 절반을 삽입한다고 가정하면 (올바르게) 경계 윤곽을 반복하는 것은 경계에서 하나의 반쪽을 찾는 것만 큼 간단합니다.

Halfedges와 마찬가지로 Winged-Edge 등과 같은 다른 토폴로지 구조를 사용할 수 있지만 개념은 동일합니다.