Search code examples
calgorithmmathcomputational-geometrytriangulation

Triangulation algorithm

I've decided to create a simple demo, dividing a polygon into triangle set. Here what i've got so far:

A sequential vertex list is given (P1) forming polygon edges (polygon is not convex in most cases); a triangle set is needed

Loop through all the vertices within the polygon P1 and find the one (v), which will satisfy next clauses:

  1. remove v from polygon and save the new one to P2 previous vertex to v connected to its next one form a line which do not cross any of P2 edges

  2. v is not inside P2

If these are satisfied, we can replace P1 with (P2 + triangle( prev(v), v, next(v)) ) and repeat this action until P1 contains more than 3 vertices.

So, the questions are: is this algorithm correct and how it could be implemented using C / C++ using the most obvious and simple way?

Solution

  • I think you're describing the ear clipping method. There's code for that method at http://cs.smith.edu/~orourke/books/ftp.html ; it's the code described in the book Computational Geometry in C.