Correct Polygon Triangulation

[DominicDolan]

Info

Currently there is a basic way of performing triangulation which uses a Graham Scan triangulation technique. This algorithm performs alright in terms of efficiency but it fails for anything but a simple polygon (a polygon that does not intersect itself and has no holes). Additionally, its current implementation has a bug where it skips the starting point if that point is concave.

The current implementation can be used by getting an instance of the GrahamScanTriangulator:

val triangulator: Triangulator = GrahamScanTriangulator(vertices)

where vertices is the set of vertices that describes the polygon. Once the instance is created, the indices for the pollygon can be found from the value returned by triangulate():

val indices: ShortArray = triangulator.triangulate()

These indices can then be passed into OpenGL as an Element Index Array to correctly render the polygon. An example of this procedure can be found in the PolygonModel class.

Motive

It would be helpful to have a method for triangulating polygons that is more powerful more efficient and more reliable

Task

Implement an Algorithm for triangulating polygons that is better than what is there. This can be done by creating a class that extends the Triangulator abstract class and output the triangulation data to indices: ShortArray inside the Triangulator class.

A good algorithm for triangulation can be found in Computational Geometry - Algorithms and Applications by Mark de Berg which uses Monotone Polygon Triangulation.