I have to implement a polygon triangulation algorithm for a school assignment. I chose to follow the algorithm described in the book "Computational Geometry: Algorithms and Applications".
The input is a polygon stored as a doubly-connected edge list. The first step is to partition the polygon into monotone pieces. In order to do so, it's necessary to perform a line sweep and process each vertex according to its type. According to the authors, the vertex types are described as follows:
We distinguish five types of vertices in P—see Figure 3.3. Four of these types are turn vertices: start vertices, split vertices, end vertices, and merge vertices. They are defined as follows. A vertex v is a start vertex if its two neighbors lie below it and the interior angle at v is less than π; if the interior angle is greater than π then v is a split vertex. (If both neighbors lie below v, then the interior angle cannot be exactly π.) A vertex is an end vertex if its two neighbors lie above it and the interior angle at v is less than π; if the interior angle is greater than π then v is a merge vertex. The vertices that are not turn vertices are regular vertices. Thus a regular vertex has one of its neighbors above it, and the other neighbor below it.
I can't figure out how to differentiate start vertices from split vertices, or end vertices from merge vertices. How can I do it?
My data struct for the DCEL is something like this
class HalfEdge {
HalfEdge *previous, *next, *twin;
Point *to, *from;
};
Maybe if you keep track of a counter clock-wise orientation of the polygon's boundary (i.e. keep the edges directed), you could distinguish the two. Say the consecutive vertices are v[i-1], v[i], v[i+1] and v[i-1] and v[i+1] are below v[i]. Then form the 2D vectors v[i]-v[i-1] and v[i+1]-v[i]. After that, calculate the determinant det( v[i]-v[i-1] , v[i+1]-v[i] ). If the determinant is positive, then the vertex is start. If the determinant is negative, the vertex is split.