Single header only constrained delaunay tessellator, C++14 & STL only.
This is originally a fork of https://github.com/Bl4ckb0ne/delaunay-triangulation (Bowyer-Watson), refactored, with a few bug fixes and added support for constrained triangulations. (so Kudos to Bl4ckb0ne for original implementation!).
Simply include delaunay.hpp and you're off!
#include "delaunay.hpp"
The Delaunay namespace provides a Tessellator class which you can use to create the tessellation of triangles given the input vertices.
std::vector<delaunay::vector2> vertices({
delaunay::vector2(0, 0),
delaunay::vector2(1.0, 0),
delaunay::vector2(0.5, 1.0)
});
delaunay::tessellator tess(vertices);
std::list<delaunay::triangle> result = tess.getTriangles();
No Steiner points are inserted so the number and ordering of vertices are preserved. The result is a list of triangles with indexes of the original vertices container used for tessellation.
Input vertices must be unique and not duplicated, otherwise this will cause erroneous tessellations. A function is provided for convinience for this.
delaunay::convenience::unique(vertices);
N.B since this function sorts these vertices before uniquing them, the ordering may not be preservered for the original vertices.
Triangle winding is not enforced, this can be achieved by...
For examples of usage. See examples/examples1.cpp.
examples/examples2.cpp is a simple command line program that reads CSV files [vertex definitions (double, double), and edge definitions (int, int) to be used as constraints supplimenting the vertex definitions], and outputs (stdout) Wavefront OBJ valid syntax.
Constraints can be used to enforce edges in the resultant tessellation. First tessellate the vertices as per usual.
e.g This snippet tessellated vertices defining a ellipse which is 2 units wide, 1 unit high, with 16 segments.
unsigned int segments = 16;
double width = 2.0;
double height = 1.0;
std::vector<delaunay::vector2> vertices;
for (unsigned int d = 0; d < segments; ++d)
{
double angle = d * (2.0 * Delaunay::pi) / segments;
vertices.push_back(Delaunay::Vector2(width * cos(angle), height * sin(angle)));
}
delaunay::tessellator tess(vertices);
std::list<delaunay::triangle> result = tess.getTriangles();
Constraints are added as edges (vertex index pairs). Constraints are added individually, a single constraint at a time. If the edge defined by the two vertex indexes is already present in the tessellation, it is ignored.
tessellator.addConstraint(delaunay::edge(0, segments / 2));
Adding a constraint updates the triangles and edges within the tessellator instance. Vertices are unaffected.
When adding multiple constraints, edges defining the constraints should ideally not intersect each other, however since they are added individually, one constraining edge will overwrite the other.
e.g Adding another constraint to the above tessellation which crosses the original constraint will result in the second constraint given priority, effectively loosing the previous one.
tessellator.addConstraint(std::pair<unsigned int, unsigned int>(segments / 4, 3 * (segments / 4)));
For examples of usage. See examples/examples1.cpp.
Please submit bug data (if applicable) as .csv, ideally this will be added as a test to identify regression in future development. A CSV output function is provided for convenience.
delaunay::convenience::csv(std::vector<delaunay::vector2>)
This does not create a csv file, only the syntax for a csv file, so the caller is reposonsible for writing a file.
e.g std::ofstream file("bugData.csv"); file << delaunary::convenience::csv(vertices);
- Doxygenate
