The interactive polygon triangulation algorithm tiles the regions defined by a number of multipolygons with constrained Delaunay triangles. The polygons are specified via edges defining their boundaries which can be formatted as JSON or raw point data. The boundaries of the polygon and the triangulation itself can be visualised.
Each interior edge of the output triangulation is Delaunay: that is, there is a circle passing through the two vertices whose interior does not contain any vertices. Over all triangulations of the multipolygons, the result maximises the minimum internal angle and minimises the maximum radius of the circumcircle of a triangle.
The ordering of vertices within a polygon should be such that the interior of the region is on the left while walking around the boundary. An outer polygon would therefore have counterclockwise vertex ordering or positive orientation and an inner or hole polygon would have clockwise vertex ordering or negative orientation.
The format of the input JSON data is an array of one or more multipolygons. A multipolygon is an array of one or more simple polygons, the first having positive orientation and any remaining having negative orientation. A simple polygon is an array of at least three points in order around its boundary. A point is an array of two Cartesian coordinates.
Alternatively, the vertices of the input polygons can be specified with raw points in order around the boundary of the polygon. Each line should contain two Cartesian coordinates, each simple polygon should be separated with a empty line and each multipolygon should be separated by two empty lines. The format of the input data is identified automatically.
The default format of the output data is based on the type of the input; polygons represented as JSON data have the output also formatted as JSON and polygons represented as raw points have output formatted as an OBJ mesh file. The output type can be toggled by holding the Alt/option key when creating the triangulation
The output JSON data is formatted as an array of triangles, where a triangle is an array of three points and a point is an array of two Cartesian coordinates. Each output triangle has positive, counterclockwise, orientation.
The output OBJ format is organised into lines for vertex coordinates and one-based triangle vertex indices. This format is intended for 3-dimensional surface meshes but it can be used for 2-dimensional data by setting the z coordinate of each vertex to zero. This format can be opened in mesh visualisation software.
Icons exist for selecting a file of input data, creating the triangulation, saving the output data as a file, clearing the polygon/triangulation data, choosing some example polygon data at random, and displaying this help. Tabs exist for specifying the polygon data and retrieving the triangulation data, as well as visualising the input and output data.
The Polygon and Mesh visualisation tabs support gestures to pan and zoom the rendering. Devices with touchpads or touchscreens are supported. Otherwise the auxillary mouse button may be used to pan and the mouse wheel may be used to zoom via holding the Ctrl key. Support for interacting with the rendering may vary on different systems/browsers.
The implementation of the triangulation algorithm is robust and uses exact predicates with symbolic perturbation to construct the result. The speed of execution is competitive with polygon meshing via constrained Delaunay triangulation with CGAL. For example, for the Vice-Counties MLWM dataset from the Biological Records Centre, the throughput is 1.02 million polygon triangles per second versus 725 thousand for CGAL version 5.5.1. The code was built with the -O3 and -DNDEBUG compiler settings using clang version 14.0.3 and executed on an Apple M1 Max chip.
This page does not use cookies or otherwise track you. Your data is temporarily passed to the server for processing but it is not stored. Basic usage data is collected but this is anonymised via a one-way function.
This page is free to use and does not display adverts. If you find it useful and would like to contribute to server costs or just buy the developer a coffee then you can visit buymeacoffee.com/geodojo.
This page is built using the GeoDojo Delaunay API.
Please contact hello@geodojo.net with any problems or feedback.