Optimizing Polygon Triangulation

다각형을 삼각 분할하다 보면 일부 삼각형 중에는 한 변의 길이가 나머지 변의 길이에 비해서 매우 작거나 또는 매우 큰 경우가 많이 나타난다. (이런 경우에 외접원의 반지름이 매우 커진다). 삼각 분할에서 만들어진 삼각형을 이용하여 mesh을 형성할 경우에 분할된 삼각형이 보다 균일한  경우가 더 좋을 것이다.

균일한 삼각 분할을 만들기 위해서 이미 완성된 분할 결과를 가지고 다시 수정 작업을 거쳐야 한다. 삼각 분할 결과로 나타난 각 내부 edge(AC, diagonal)에 대해서 그 edge가 대각선이 되는 사각형(ABCD)을 찾고, 이 사각형이 convex인 경우에 한하여 아래의 과정을 적용한다.

1. 사각형 ABCD를 분할하는 두 개의 삼각형 ABC, ACD의 외접원의 반지름의 최솟값을 찾는다.
   min(radius(ABC), radius(ACD))
2. 사각형 ABCD에서 원래 대각선(AC)과 교차하는 대각선(BD)이 나누는 두 개의 삼각형 BCD, BDA의 외접원의 반지름의 최솟값을 찾는다. 
   min(radius(BCD) and radius(BDA))
3. 원래 대각선(AC)이 나누는 삼각형 외접원의 최소 반지름이 교차 대각선(BD)이 나누는 삼각형의 최소 반지름보다 더 작은 경우 이 대각선을 기존의 edge(AC)와 바꾼다. (바꾼 edge는 더 이상 바꾸지 않는다)
4. 다른 내부 edge에 대해서 동일한 과정을 반복한다.

** 내부 edge의  FLIP;

 

** 원래의 삼각화(Ear Clipping)

**최적화 후

 

/**
** http://blog.naver.com/helloktk/80051332733 에서 옮김.
*/