|
|
Polygon Triangulation is a classic problem in computational geometry and has been a problem of a great appeal to computational geometers for nearly one century and becomes a hot research topic in past decades. A brief histroy of the polygon triangulation algorithms can be found from Godfried T. Toussaint homepage. However, "is there a deterministic, linear-time polygon triangulation algorithm significantly simpler than that of Chazelle?" is still a open problem in computational geometry community[1].
There are at least three popular polygon triangulation algorithms: Recursive Ear Cutting algorithm improved by ElGindy, Everett and Toussaint[2], Sweep Line algorithm presented by Garey et al[3] and Incremental Randomized Algorithm by Sediel[4] and Amato[5]. Of them, recursive ear cutting algorithm has the worst performance and diffcult extend to polygon with holes, although it's much easy to implement compared with other complicated angorithms. On the other hand, the incremental randomized algorithm has better performance, but the improved algorithm presented by Amato[5] is very diffcult to implement. The first linear algorithm proposed by Chazelle[6] is extremely diffcult to implement, and up to now i didn't find its implementation on the web. I believe the sweep line algorithm is the most widely used algorithm in nowdays real applications.
 |
 |
 |
|
a. Six types of Vertex:
Start vertex(5,7,14) End vertex(1,3,11) Split vertex(2,10,12) Merge vertex(6,9,13) Regular Up Vertex(4), polygon internal on its left Regular Down Vertex(8), polygon internal on its right |
b. Monotone polygons with an additional auxiliary diagonal
|
c. Final Triangulation
|
A polygon can be partitioned to monontone pieces by getting rid of its split or merge vertices (adding diagonals). When a diagonal is inserted, an auxliary diagonal is inserted at the same time on the opposite direction for monotone piece searching purpose (all monotone pieces can be easily constructed by these auxiliary diagonals since each diagonal is always shared by two adjacent monontone pieces), see Figure 1.b. Specificly, for each split vertex vi, a diagonal is inserted to the lowest vertex above it. On the contrary, for each merge vertex, a diagonal is inserted to the highest vertex below it. This lowest/highest vertex is often called helper of directly left edge of vi.
The input file of polygon is an ascii BDM (boundary mesh) file sampled as follows.
karman:~/Poly2Tri> cat sample.bdm
#Simple Polygon outer bounary vertices oriented in counter clockwise direction. 4 #number of vertices; 0 0 #coordinates for first vertex; 10.0 0 ... 10.0 10.0 0 10 #Here are the all vertices for holes oriented in clockwise direction; #The first hole loop 4 #number of vertices; 2.5 7.5 #coordinates for first vertex; 7.5 7.5 #coordinates for second vertex; 7.5 2.5 ... 2.5 2.5 #The second hole loop 5 #number of vertices; 5 1 #coordinates for first vertex; 6 1 #coordinates for second vertex; 6 0.5 ... 5 0.5 ... 4.0 0.75 ... #The third hole loop 6 #number of vertices; 5 9 #coordinates for first vertex; 6 9 #coordinates for second vertex; 7 8.5 ... 6 8 ... 5 8 ... 4.0 8.5 ... #continue if there are any additional holes. ... ... ... run Poly2Tri sample.bdm to check and triangulate this sample fileAbove it's a sample file, which can be found from Poly2Tri's distribution. Poly2Tri assumes that your input is a simple polygon, although the polygon may have holes as many as you wish. If Poly2Tri runs sucessfully, it will generate (n-2)+2*m triangles, where n is total number of vertices and m number of holes. Default Poly2tri's output is a MetaPost source file (to generate high-quality EPS/PS files), Poly2tri also can output results as ASCII TECPLOT FEM mesh file and .ele and .node files which can be visualized by TECPLOT and free tooklit ShowMe developed by Shewchuk respectively. If you'd like to output other file format, just drop email to me.
Download Poly2Tri for Linux/Unix from the link above and
> tar zxvf poly2tri.tar.gz > cd poly2tri > makeIt should work on most Linux/Unix like distributions.
Download Poly2Tri (binary/source code) for Microsoft Windows from the link above. If you'd like to compile the source code, the lastest version of Microsoft Visual C++ Express Edition is necessary (it's free).
Usage: poly2tri [-hpstmd] filename.
Options:
-p: DO NOT parse input bdm (boundary mesh) file.
Use this option if the input is very large without any comments.
-s: Output results as ShowMe formats.
-t: Output results as TECPLOT ASCII PLT format.
-m: DO NOT output monotone polygons and triangulation results
as metapost source file.
-d: Output debug information (log file).
-h: This help message.
Examples:
./poly2tri sample.bdm
Poly2Tri will parse the sample.bdm and then triangulate it to triangles.
One file sample.mp will be generated. This file is a metapost source file,
you may compile it by metapost (go to the following link to download one
if you don't have. http://cm.bell-labs.com/who/hobby/MetaPost.html).
mpost sample.mp
waiting few seconds then enter "end", another three files sample.1 and
sample.2 and simple.3 will be generated. These are three EPS/PS files
and can be viewed by gsview, kghostview etc. sample.1 is an EPS/PS file
of input polygon and sample.2 is an EPS/PS file with all inserted diagonals
which paritition the polygon to monotone pieces, and all shadowed monotone
polygons; sample.3 is an EPS/PS file with all triangles.
If you want to show the vertex index labels, remove the comments from
metapost source file. See the sample.mp source code for details. Please
be noticed that if you do like that, you have to run mps2eps before you
view by gsview, kghostview etc. About mps2eps, see
http://www.ida.liu.se/~joned/download/mps2eps/ for details.
./poly2tri sample.bdm -spm
Poly2Tri will NOT parse the sample.bdm and triangulate it to triangles.
Metapost source file sample.mp is ingnored and two sample.ele and
sample.node are generated, which can be visualized by ShowMe developed
by Jonathan Shewchuk. if you don't have it, go to Jonathan's website to
download one, http://www.cs.cmu.edu/~quake/triangle.html.
./poly2tri sample.bdm -tsd
Four files will be generated.
sample.mp (metapost source file)
sample.ele and sample.node (visualized by ShowMe)
sample.log (debug file, for debugging purpose only)
sample.plt (TECPLOT ASCII FEM mesh file format)
Poly2Tri is one of the fastest codes open to public according to my primary testings. Detailed comparsions and discussions with other popular triangulation codes like Triangle developed by Jonathan Shewchuk by divide-and-conquer, incremental and sweepline algorithms[11], FIST developed by Martin Held by "fancy" ear-clipping algorithm[13] and "triangulation" code implemented by Atul Narkhede and Dinesh Manocha by Seidel's incremental randomize algorithm[12] are presented below. My primary compasions show that Poly2Tri is very competitive and tends to be faster than several popular codes mentioned above.
However, Poly2Tri's performance is extremely poor compared with FIST and Triangle for those random polygons that zig-zag widely (see the last running time comparsions in Table 1 and application example of Figure 2 below). The reason is simple: to triangulate such kind of polygons, the size of splay tree (to locate the directly left edge of an event vertex) is much much larger than those "smoother" polygon with small edges and Poly2Tri will spend most of the time on tree transversing and search key updating. For example, for the last appliaction example of Figure 2 below, 98% time is spent on monontone polygon partitioning (splaytree transversing and search key updating), while only around 2% time on monotone piece seaching and monotone piece triangulation.
Notes:A C++ implementation for simple polygon (with/without holes) by sweep line algorithm is presented here. In order to well understand the source code, the reader should have a basic understanding on Standard Tempate Library (STL), since most of the data structures I used is from STL like list, map, pripority queue, stack etc., unless those data structures i couldn't find from STL, like splay tree for efficient edge binary searching. I didn't use circular double-linked list in Poly2Tri, unlike most papers/textbooks recommended. Since Poly2Tri was developed by standard C++ and didn't use any additional libraries, so it could be complied on most Linux/UNIX distributions. I will port it to windows platform soon.
Poly2Tri is robust and can handle all degeneranced cases I tested thanks to routines from Shewchuk arbitrary precision floating-point arithmetic and fast robust geometric predicates[9][10]. Also thanks to FEMAGSfot SA's agreement , I can open this source code to public, but at the same, kindly please be noticed that Poly2Tri acutally now works as the initial triangulation code built in Mesh2d, a commerical unstructured mesh generator currently used by most major single silicon crystal growth players around the world, so all the source code copyrights (except the exact arithmetic algorithm by Shewchuk) belong to FEMAGSoft SA and me (UCL/CESAME), and may not be sold or included in any commercial products without a license. Please check the COPYRIGHTS in the source codes for details.
The kernel algorithm of Poly2Tri was implemented in very short time, although I thought the sweep line algorithm and data structures for quite a long time. You are welcome to report bugs, send comments by email.
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
a. Boundary mesh
|
b. Shadowed monotone pieces
|
c. Polygon triangulation
|
d. Polygon Delaunay triangulation
|