Hi, Crazy-: [ Triangulation ] Ear Clipping Algorithm 삼각기법 알고리즘

Ear Clipping 알고리즘은, 기존 Triangulation 알고리즘 중 가장 쉽고 널리 알려진 알고리즘이다

http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

위 링크의 논문 참조 바란다.

논문을 바탕으로 정리를 하자면, 우선으로 다음과 같은 조건을 갖춰야한다.

1. Polygon line은 정렬 되어있어야 한다.
2. Polygon line 의 끝점과 시작점은 서로 만나야한다 ( Closed Curve )

다음과 같이 Simple 로 폴리곤이 정의 되어 있어야 한다.

폴리곤의 배열 순서는 다음과 같다.
P = [0,1,2,3,4,5,6,7,8,9] (0과 9는 서로 만남)

삼각화를 하기전 데이타 분류작업이 선 진행 되어야 한다.

데이터는 다음과 같이 3가지 종류로 분류 된다.

1. reflex vertex
2. convex vertex
3. ear tip

reflex vertex는 P(i-1) 점과 P(i), P(i+1) 점을 잇는 각도가 시계방향으로 봣을때, 각이 180도보다 큰 각을 말한다.
reflex vertex는 P(i-1) 점과 P(i), P(i+1) 점을 잇는 각도가 시계방향으로 봣을때, 각이 180도보다 작은 각을 말한다.

ear tip은 P(i-1) 점과 P(i), P(i+1)으로 삼각형을 만들었을때, 삼각형 내에 다른 점들이 포함되지 않는 점의 모음이라고 할 수 있다.

예제 샘플에서의 분류는

C = {0,1,3,4,6,9}

R = {2,5,7,8}

E = {3,4,6,9}

로 나눌 수 있다.

가장 먼저 해야 할 일은 Ear tip의 첫번째 상수인 P3을 제거 하는 일이다.
Ear tip 분류자체가 한점을 포함하지 않는 삼각형에 관한 점이기에 P3이 중심이되는 삼각형은 독립적으로 분류가 가능하다.

P3을 제거함으로써 ,P2와 P4가 변화를 갖게 되는데 첫번째 경우 P4는 convex값이다.

C = {0,1,3,4,6,9}

R = {2,5,7,8}

E = {4,6,9}

그다음 Ear tip인 P4를 제거 한다.

P2는 여전히 Convex값을 가지지만 P5는 더이상 reflex값이 아니라 convex값으로 바뀐다.
relfex 리스트에서 P5는 제거 되고 ear list에 P5가 추가 된다.
C = {0,1,3,5,6,9}
R = {2,6,7,8}
E = {5,6,9} ( P4 제거 되고 P5 추가된 상태 )

변화에 따라 그다음 제거대상자인 P5를 제거한다.

P2가 reflex 였으나 이제 convex로 바뀌였다. 그러나 P2를 ear test 하였을경우 P7이 삼각형 안쪽으로 들어가므로, P2는 ear tip이 아니다.
R = {7,8} ( P2가 리스트에서 제거된 상태)
E = {6,9} ( P5가 제거된 상태 )

P6이 제거된 상태

P2는 convex였으므로, 그대로 남는다. 하지만 Ear 그룹이 아니였음에도 불구하고, P6이 제거된 상황에서 재검을 하면 P2는 Ear그룹에 소속된다.
E = {9,2}

좀 이해안가는 문장이
The ear list is written this way because the new ear is added first before the old ear is removed. Before removing the old ear, it is still considered to be first in the list.

왜 ear list가 이렇게 배열 됬는지에 대해서, 이전 ear가 제거 되기 전에 새 ear가 먼저 추가 되어서라 한다. 이전 ear를 제거하기 전에 리스트내에 첫번째로 있어야할것이 아직 고려되기 때문이라 하지만, list 들을 훑다보면, 제거된 P6의 다음 은 7->8->9->0->1->2 이므로
9,2 순이 아닐까 한다.

아무튼 그다음 제거 대상 ear 인 P9를 제거한다.