Tessellator
Computes a triangular mesh tessellation for a given polygon.
This is inspired by mapbox's earcut algorithm (https://github.com/mapbox/earcut) which is a modification to FIST (https://www.cosy.sbg.ac.at/~held/projects/triang/triang.html) written by Martin Held, and ear clipping (https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) written by David Eberly.
Notes:
Requires valid polygons:
No self intersections
Holes may only touch at one vertex
Polygon must have an area (e.g., no "line" boxes)
sensitive to overflow (e.g, subatomic values such as E-200 can cause unexpected behavior)
The code is a modified version of the javascript implementation provided by MapBox under the following license:
ISC License
Copyright (c) 2016, Mapbox
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH' REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
Types
Implementation of this interface will receive calls with internal data at each step of the triangulation algorithm. This is of use for debugging complex cases, as well as gaining insight into the way the algorithm works. Data provided includes a status string containing the current mode, list of points representing the current linked-list of internal nodes used for triangulation, and a list of triangles so far created by the algorithm.
Triangle in the tessellated mesh