2D Triangulation

The triangulation algorithm is based on the algorithm presented in Computational Geometry

Initial polygon representation

The polygons are represented as a collection of paths for faces and holes. Faces are ordered in counter-clockwise order and holes in clockwise order.

Edge list

The edge list a data structure containing all edges of the polygons. The edges are directed. A polygon is represented in counter-clockwise order.

Every edge contains:

A reference to the incoming edge
A reference to the outgoing edge
The point of origin

The data structure has a split method. This method inserts two new edges and updates some incoming and outgoing references.

References before splitting:

v_prev -> v
u_prev -> u

References after splitting:

v_prev -> vu -> u
u_prev -> uv -> v

Split returns uv and vu.

Example:

Generate monotone pieces

A polygon is monotone if every line in y direction intersects 0 or 2 edges.

The algorithm is a sweep line algorithm. The line sweeps from +y to -y. The algorithm requires a binary search tree, a hash map and a priority queue. The BST contains every edge that is currently intersecting the sweep line sorted by x position of the intersection. The hash map maps downward facing edges intersecting the sweep line to edges used for splitting.

Add faces and holes to the edge list.
Classify edge origins as Regular, Start, End, Split or Merge vertices.
Add the edges to a priority queue. Priotity relation: y1 > y2 || (y1 == y2 && x1 < x2)
Initialize the BST and HM as empty.
Process entries of the priority queue in order.

Classification

Start:

Polygon begin

End:

Polygon end

Regular:

Standard edge

Merge:

Merge two monotone polygons in one

Split:

Split polygon in two monotone pieces

Processing of a Vertex/Edge

le* denotes an edge in the BST and helper[le*] the corresponding edge in the HM. The left part of each diagram is the state before processing and the right part the state after processing. The dotted line is the current sweep line. The BST and HM can contain more entries than shown. These entries wont be modified.