코드 제거: 2012년 9월 4일;  코드 구현: http://kipl.tistory.com/13

Polygon의 내부를 겹치지 않게 분할하는 것을 polygon의 삼각화라고 한다. N개의 꼭짓점이 있는 polygon의 경우에 N-2개의 서로 겹치지 않은 삼각형을 내부에 가지게 되며, polygon의 경계와 겹치지 않는  N-3개의 내부 경계 라인을(diagonal)을 가지게 된다. 

사용자 삽입 이미지


분할된 삼각형의 외접원 반지름에 편차가 심한 경우 삼각형의 면적이 균일하게 분할되지 않는다. 이런 경우 인접하는 두 개의 삼각형으로 형성된 사변형에서 현재의 대각 변에 교차되는 대각 변으로 재분할을 시도한다. 이렇게 새로이 만든 삼각형을 검사하여 이전보다 면적이 균일하면 이 분할을 사용한다. 물론 삼각형의 외접원의 반경이 작을 때는 거의 균일한 분할을 얻을 수 있다. Polygon Optimizing을 참고하기 바란다.

*simple 폴리곤이 아닌 경우는 아래의 링크를 참조하기 바란다.

1). O(n log(n)) 복잡도를 갖는 polygon triangulation algorithm;
==> 'Fast Polygon Triangulation based on Seidel's Algorithm'.
==> http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

2). Poly2Tri 홈페이지:
==> Fast and Robust Simple Polygon Triangulation With/Without Holes by Sweep Line Algorithm
==> http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html

 

 

triangulation notes: (몇 개의 사이트는 없어졌다).
Nice lecture notes:
http://arachne.ics.uci.edu/~eppstein/junkyard/godfried.toussaint.html
▶ Narkhede & Manocha's description/code of Seidel's alg:
http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html
▶ Some school project notes w/ triangulation overview & diagrams:
http://www.mema.ucl.ac.be/~wu/FSA2716-2002/project.html
▶ Toussaint paper about sleeve-following, including interesting
description & opinion on various other algorithms:
http://citeseer.ist.psu.edu/toussaint91efficient.html
▶ Toussaint outline & links:
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html
http://geometryalgorithms.com/algorithms.htm
▶ History Of Triangulation Algorithms
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Thierry/thierry507webprj/complexity.html
▶ Ear Cutting For Simple Polygons
http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian//cutting_ears.html
▶ Intersections for a set of 2D segments
http://geometryalgorithms.com/Archive/algorithm_0108/algorithm_0108.htm
▶ Simple Polygon Triangulation
http://cgafaq.info/wiki/Simple_Polygon_Triangulation
▶ KKT O(n log log n) algo
http://portal.acm.org/citation.cfm?id=150693&dl=ACM&coll=portal&CFID=11111111&CFTOKEN=2222222
▶ Poly2Tri implemenation, good notes and looks like good code, sadly the
license is non-commercial only:(최근에 사이트가 존재하지 않음)
http://www.mema.ucl.ac.be/~wu/Poly2Tri/poly2tri.html
▶ FIST
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html
▶ Nice slides on monotone subdivision & triangulation:
http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf

▶ Interesting forum post re monotone subdivision in Amanith:
http://www.amanith.org/forum/viewtopic.php?pid=43
 

728x90

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

Brute Force Triangulation  (1) 2008.05.28
Polygon Triangulation (II)  (0) 2008.05.26
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Posted by helloktk
,