Simple 2d polygon triangulation

问题:

Trying to triangulate a set of simple 2d polygons, I've come up with this algorithm:

• 1) For each vertex in the polygon, compute the angle between the two linked edges
• 2) Sort vertices by decreasing angle relative to the interior of the polygon
• 3) If there is less than 3 vertices in the set, we're done
• 4) Take the last vertex in the set and output the triangle formed by it and its two neighbours
• 5) Remove the vertex from the set
• 6) Update the angle of the two neighbours
• 7) Jump to 2

I've tested it, and found it to work even on really big and complicated simple 2d polygon (it don't work for polygon with a hole or self intersecting polygons).

Is there corner cases that will produce degenerate result?

Does this algorithm is a known one?

If not, I would like to be sure this algorithm is rock solid but I have not the mathematical background to prove it.

Thanks a lot.

回答1:

You are doing a version of "ear clipping" approach to triangulation, see: http://en.wikipedia.org/wiki/Polygon_triangulation

Your algorithm fails if another polygon vertex (say from the other side of the polygon) ends up inside the triangle 'ear' you form. Consider this example:

Your algorithm will choose A first, and make a triangle with the two adjacent edges (connected with the dashed line). But this triangle includes another vertex (B) and is clearly incorrect.

The generalized ear clipping approach depends on finding ears you can clip off that do not have any included vertices.

回答2:

Simple Convex Polygons are O(n)

This is when you want to handle simple polygons like rectangles, pentagons, hexagons and so on. Here you just take a starting point and connect it to all other vertices. This algorithm is trivial and what I really wanted was a more general solution that could handle concave and polygons with holes.

In order to deal with more complex polygons like the one Payne provided...

Arbitrary Polygon to Triangle in O(n log n)

While there are algorithms that run faster, the faster algorithms become very complicated. Kirkpatrick et al. found an algorithm to run in O(n log log n) and Chazelle did it in O(n). However, the easiest thing to implement is probably the Seidel algorithm that runs in O(n log n).

The algorithm is a 3-step process

1. Decompose the polygon into trapezoids
2. Decompose the trapezoids into monotone polygons
3. Decompose the monotone polygons into triangles

C source

If you're interested in C source it can be obtained from University of North Carolina at Chapel Hill. In general the code quality is good, handles holes, but will probably need to be massaged to your needs.

回答3:

If I'm understanding you correctly, you're chopping off triangles starting with the smallest interior angle. This can fail if the polygon is not convex. Consider a polygon with vertices (in order) at: (0,0) (10,9) (9,9) (9,10). The smallest angle is the one at the origin, but you can't safely cut off that triangle.

(If your polygon is convex, then you can just pick any vertex, remove a triangle there, and repeat. So I'm guessing you want your algorithm to work even for non-convex polygons.)

回答4:

I've had to solve a similar problem before, and the resulting code might be useful to you or someone else looking at this:

Demo: http://cecchi.me/portfolio/triangulation
Source: http://cecchi.me/js/point-picking.js.src

The source is a bit mucky to allow for easier animation but you should be able to see how I solved the problem Payne pointed out with convex polygons (the relevant code starts around line 200). Note that my solution still does not allow for complex polygons.

回答5:

While ear clipping works reasonably well, simplistic methods slow down as the polygon increases in complexity since checking the entire polygon when collapsing each ear becomes increasingly slow.

The ear clipping algorithm from libgdx is a good place to start from, since its very robust - using FIST (Fast Industrial-Strength Triangulation of Polygons).

I used this as a basis for polygon tessellation, then added spatial optimizations for the point-in-triangle tests, (O(n log n) instead of O(n^2)).

See:

• C code, tests.
• Rust code, tests
• Original code from libgdx.

---

Note, while the algorithm doesn't explicitly support holes, you can use keyhole edges between separate islands, which will then be correctly triangulated.