Poly2Tri: constrained Delaunay triangulation for C++

What it triangulates, and what it refuses

Poly2Tri is described in one line as a 2D constrained Delaunay triangulation library, and the README spends its first paragraphs on the contract rather than the features.

The opening notice is that there is no input validation of the data given for triangulation, so you need to think about this. Poly2Tri does not support repeat points within epsilon. If you have a cyclic function that generates random points, make sure you do not add the same coordinate twice. If you are given input and are not sure whether the same point exists twice, you need to check for that yourself.

Then there is the polygon requirement: only simple polygons are supported. You may add holes or interior Steiner points, but interior holes must not touch other holes, nor touch the polyline boundary.

That is an unusually clear statement of limits for a geometry library, and it is worth reading as the specification of the tool rather than as a disclaimer. A simple polygon is one whose boundary does not cross itself. A hole that touches another hole or touches the outer boundary creates a degenerate configuration, and the sweep-line algorithm here is not built to resolve it. So the library draws a line around a well-defined class of input and tells you where that line is.

The final line of the notice is a good summary of how the author expects the tool to be used: make sure you understand the preceding notice before posting an issue, and if you have an issue not covered by the above, include your data-set with the problem.

The four-step usage order

The README gives an explicit order for using the library, and it is not a suggestion.

1. Initialize CDT with a simple polyline, which defines the constrained edges. 2. Add holes if necessary, also simple polylines. 3. Add Steiner points. 4. Triangulate.

The order matters because each step constrains the next. The initial polyline is what makes the triangulation constrained rather than a plain Delaunay triangulation of a point set. Holes are added afterwards and are themselves polylines, which means they participate in the constraint set. Steiner points are interior points that force additional edges through them, which is the standard way to control the triangle shapes in a constrained triangulation. Triangulation comes last because it is the step that consumes all the accumulated constraints.

The practical consequence is that this is not a one-shot function. You build up the constraint structure incrementally and then solve it, which is exactly how the algorithm is designed to work and also why the API looks the way it does. The alternative, handing a finished polygon with holes and interior points to a single call, would hide the ordering requirement that trips people up.

The library is small enough that reading its source alongside this order is a reasonable way to learn the API, and the README's second half points at the algorithm references so you can understand what the code is doing rather than only how to call it.

The algorithm and its references

The References section names two pieces of prior work. The first is Domiter V. and Zalik B. (2008), the sweep-line algorithm for constrained Delaunay triangulation, which is the algorithm the library implements. The second is FlipScan by the library author Thomas Åhlén, and the README links an image of it in the doc directory.

A sweep-line constrained Delaunay algorithm works by sweeping a line across the plane and maintaining the triangulation incrementally, inserting points and edges as it goes and resolving conflicts as it advances. That is a meaningful departure from the simpler incremental algorithms, because the sweep gives a natural way to find the Delaunay property and to handle the constraint edges without a global search.

FlipScan is a different kind of reference and the presence of its diagram is a hint about the implementation. Scanline-based flip algorithms determine whether a point lies inside a triangle by scanning along a horizontal line through it and counting edge crossings, and a flip-based approach to point location uses that test to decide whether an edge can be flipped. The doc/FlipScan.png image in the repository is there because the geometry of that decision is not obvious in prose.

So the library is a well-documented implementation of a published algorithm rather than an original invention, which matters for anyone planning to depend on it. The correctness argument you can check is the literature's, not the maintainer's.

Building the library and the unit tests

The build is CMake-based, and the README gives three variants depending on what you want. With ninja installed, the plain library build is:

mkdir build && cd build
cmake -GNinja ..
cmake --build .

To build and run the unit tests:

mkdir build && cd build
cmake -GNinja -DP2T_BUILD_TESTS=ON ..
cmake --build .
ctest --output-on-failure

And to build the testbed:

mkdir build && cd build
cmake -GNinja -DP2T_BUILD_TESTBED=ON ..
cmake --build .

The dependency list is short and explains what each piece is for. The core library needs only the Standard Template Library. The unit tests need Boost, for the filesystem and the test framework. The testbed needs OpenGL and GLFW.

Two details matter for a Windows or unusual-platform build. The unit tests pull in Boost's filesystem component, which is the part that has historically been awkward to depend on. And the testbed is an OpenGL program, so it will not build everywhere, which is why it is behind its own flag rather than being on by default.

The repository carries both a CMakeLists.txt and a meson.build, so Meson is an alternative build system for anyone who prefers it, and there is a .clang-format file, which tells you the project expects its formatting to be enforced rather than merely conventional.

Driving the testbed from the command line

The testbed is an OpenGL viewer, and the README documents how to drive it. Passing a filename, a centre x, a centre y and a zoom loads data points from a file and frames the view on that region. Passing only a filename loads the points and automatically fits the geometry to the window. A third form generates a random distribution of points inside a constrained box, taking the number of points, the box radius and the zoom.

The example invocations show the range:

build/testbed/p2t testbed/data/dude.dat 350 500 3

build/testbed/p2t random 10 100 5.0
build/testbed/p2t random 1000 20000 0.025

The dude.dat example is the classic constrained triangulation test case, a set of points forming a constrained region with holes. The random examples are useful for a different reason: with 10 points at a radius of 100 you can see the triangulation clearly, while 1000 points at a radius of 20000 with a zoom of 0.025 shows the algorithm handling a dense cloud.

The testbed serves a practical purpose beyond demonstration. Because the library does not validate its input, being able to feed it a known point set and look at the triangulation is how you find out whether your own data has the degenerate configuration the README warns about. A self-intersection or a duplicate point shows up immediately on screen, which is faster than reading the code for the edge case.

Where Poly2Tri is the wrong choice

Three limits are structural. The first is the input contract, which is the same one the README leads with and which is a genuine operational hazard. If your pipeline can emit duplicate points, you must deduplicate before calling the library, and the README's warning about cyclic random generators is a hint about how that happens in practice. Feeding duplicate points into a sweep-line constrained triangulation produces a result that is wrong in ways that may not be obvious, and the library will not tell you.

The second is that the constrained edges are the polygon. This library triangulates a simple polygon, with holes and interior points. It does not solve the general constrained triangulation problem, where you impose arbitrary constraints between pairs of points in an otherwise unconstrained point set. The difference in approach is fundamental: the polygon case has a well-defined interior, the sweep proceeds across it, and the output is a triangulation of a region. If your problem is a mesh of scattered points with some segments forced to be edges, this is the wrong library and you need a general constraint solver.

The third is the maintenance and release story. There are no GitHub releases, so there is no version to pin and no changelog to read, and the last push was on 2026-10-20, which is recent, but recent commits are not the same as a versioned artefact. For a library you are embedding in a product, that means you either vendor the source and own it, or you track master and accept that an update can change behaviour without notice.

The alternative is a full geometry kernel such as CGAL, which does general constrained triangulation, handles self-intersecting and degenerate inputs with defined policies, and is far larger and heavier to build and to learn. The difference in approach is precisely the trade Poly2Tri makes: a small, fast, permissive library with a sharp input contract, against a large library that accepts far more inputs and requires far more from you in terms of build complexity and API surface.

Editorial conclusion

Poly2Tri suits a graphics or geometry developer who needs a triangulation of a polygon with holes and does not want to pull in a full geometry kernel, since the library is small, permissive and has a documented input contract. It is the wrong tool for polygons that are not simple, since self-intersecting and touching boundaries are outside what it handles, and it is the wrong tool if you need constraints beyond the polygon edges, since it triangulates rather than solving a general constrained problem. Verify first that your input points contain no duplicates within epsilon and that no hole touches another hole or the boundary, and note that the last push was on 2026-10-20 with no GitHub releases, so you are taking the master branch.

Frequently asked questions

Official sources

1. Issues
2. jhasse/poly2tri on GitHub
3. License: BSD-3-Clause
4. README