Delaunay Triangulation 후기

이 알고리즘에 대해 설명하자면 직역해 들로네 삼각분할 이라 하고

주어진 모든 점으로부터 삼각형을 만드는데

전체적인 형태가 정삼각형인 것으로 해주는 것이다.

정보가 많아 구현하기 쉬웠다.

해깔리는 점들을 나열하자면 -

- 위키에서 Boyer-Watson식과 기본 Incremental식과 차이점,

Incremental은 점을 포함하는 삼각형의 점들과 이어 만든 삼각형들에게 Flip을 적용하는 것이고

Boyer-Watson은 점을 포함하는 삼각형을 기점으로 주변을 살펴

점이 외접원에 포함되는 것만 따로 모은 삼각형들, 즉 나쁜 삼각형들에게

3변 하나씩 나쁜 삼각형들과 포함하지 않는 변들만 점과 이어 새로운 삼각형을 만든다.

두 방식들 모두 삼각형의 탐색방법에 따라 O(n^2) ~ O(nlogn) 정도 걸린다.

- Mesh 데이터구조

HalfEdge 구조인데 시간을 아끼기 위해 충분한 이해 없이 무작정 베끼다가

오류가 터졌을 때 뭐가 틀렸는지 도저히 이해가 안돼 문제점을 찾을 때 까지 고생 좀 했다.

꽤 좋은 경험이였다.

5line