Context
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.
The problem
I can't figure out how to differentiate start vertices from split vertices, or end vertices from merge vertices. How can I do it?
Additional info
My data struct for the DCEL is something like this
class HalfEdge {
HalfEdge *previous, *next, *twin;
Point *to, *from;
};