728x90

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

이를 위해서는 완성된 삼각분할 결과를 가지고 다시 수정을 하여야 한다. 삼각분할 결과로 나타난 각각의 내부 에지(AC, diagonal)에 대해서 그 내부 에지를 대각선으로 포함하는 사각형(ABCD)을 찾고, 이 사각형이 convex인 경우에 한하여 아래의 과정을 적용한다.

(1) 사각형 ABCD를 분할하는 두 개의 삼각형 ABC, ACD의 외접원의 반지름을 구하여 그들의 최솟값을 찾는다.
        radius(ABC) and radius(ACD)

(2) 사각형 ABCD에서 원래의 대각선과 교차하는 대각선이 나는 두 개의 삼각형 BCD, BDA의 외접원의 반경을 구하여 그들의 최솟값을 찾는다.
       radius(BCD) and radius(BDA)

만약 원래의 대각선(AC)이 나누는 삼각형의 외접원의 반지름의 최솟값보다도 새로운 대각선(BD)이 나누는 삼각형의 반지름이 더 작은 경우에는 이 대각선을 기존의 에지와 바꾼다. (바꾼 에지는 더 이상 바꾸지 않는다)

(3) 다른 내부 에지에 대해서 동일한 과정을 반복한다.

** 내부 에지의  FLIP;

사용자 삽입 이미지

 

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

사용자 삽입 이미지

**최적화 후

사용자 삽입 이미지

 


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

 

'Computational Geometry' 카테고리의 다른 글

Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Optimizing Polygon Triangulation  (0) 2008.05.22
Sweep Line Algorithm  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요