Application of Fortune's algorithm on triangulation
Fortune's algorithm generates a voronoi diagram with a sweep-line. The conversion of this algorithm for triangulation is trivial, but it produces a delaunay triangulation. I attempted to convert this algorithm into producing a constrained triangulation, useful for filling polygons.
Computational geometry algorithms can be really difficult to understand and implement despite that they have clear visual interpretations. Their implementations can be extremely short and laborious to conjure.
I got some results after working few evenings on this. Here's a visualization that illustrates how the algorithm sweeps through some glyph outlines, producing triangles for their innards.
I can use the results once I clean it up and solve some edge cases that I find interesting. In the rest of this blogpost I'm describing some difficult parts of this algorithm to understand it better.
Overview
This is an extension into Fortune's algorithm, but first that algorithm is stripped down to produce delaunay triangles. Instead of producing edges into a voronoi diagram, it is generating a triangle for every valid circle event that occurs during the sweep.
Marching parabolas
Fortune's algorithm maintains an arc consisting of parabolas. Each parabola is defined as an equal distance between a point and the sweeping line.
distance(k, point) = distance(k, sweep_line)The arc is defined as a sequence of points that have been seen so far. A single point may appear multiple times in the arc.
Shrinking of the parabola
As the sweeping line progresses, some of the parabolas in the arc vanish entirely. Vanishing of a parabola from the arc is a circle event.
The location of the circle event is predicted by picking the point of the parabola, and the adjacent points, then calculating the right edge of a circle that intersects all the three points.
Insertion of a point on a parabola
Whenever a point is inserted into the arc, the arc is split into half by extending the point into a horizontal line.
After the point is inserted into the parabola, the remaining circle events have to be revised.
Insertion of an edge
Whenever a vertex starting an edge is inserted into the arc,
the edge is converted into a line of form y = kx + c.
Whenever this kind of edge is inserted, the arc is split into two, and the point is added on the both arcs. The edge keeps these two arcs separated until it's time to join them.
The edges divide every arc into a 'bin' that has an upper and lower edge that intersects the sweep line. This is used to limit which arcs get the points on the sweep line.
Splitting and merging
The introduction of edges mean that the arcs have to split and merge.
The merge splits two arcs, and joins the pieces using the given point.
The split splits an arc into the two while adding a point.
Both split and merges update the circle events, but the circle events of the discarded arcs are not removed.
Progression of an edge
There's a common case where an edge follows an another one. The neighboring arcs are re-split from the point in the edge. This ensures that the resulting triangulation includes the edge.
Closing of the shape
Whenever the edges converge to close a shape, the vertex is inserted into the arcs and outermost arcs around the shapes are merged.
Blanks and filled spaces
The edge may be used to denote that there should be blank between the edges.
An arc is not produced between the blank spaces, this prevents the triangulation from occuring in there as well.
Intersecting edges
Two edges may intersect. This is something I don't expect to happen, but I know it is very well possible.
The current implementation ignores the possibility that the edges intersect. I still have to see what kind of problems it causes for the algorithm.
When doing triangulation for rendering, it may be preferable to insert a point into the intersecting edges.
Fin
The triangulator will be supplied with adaptive bezier tessellation. I use this code to render all sort of shapes and text into a VR environment.
I am a step closer to the super pretty printer. A module that can generate mixed 2D/3D models from the program's state.