Triangulate

This is a public domain triangulator. It takes 2D point info and produces a list of non-overlapping triangles. It is written in C++.

Triangulate has one public function: void get_triangles(std::vector< General::Point<float> > points, std::vector<int> splits, std::vector<Triangle> &out_triangles);

Notice: Through extended use of this library I've found that there are some corner cases that are not handled correctly by this code. I don't have time or need to fix these problems at present (due to the great triangulator in Allegro 5 that was written by Michal Cichon), but the code stays here for educational purposes, and because I may want to fix the bugs some day.

This is version 1.4. This version does support holes in polygons.

1.4 - Many more bug fixes. Tidied up. Includes makefile, builds as a library not an executable. No external dependencies. Placed things in namespaces.
1.3 - Numerous bug fixes
1.2 - Fix a bug after trying some other input data
1.1 - Added support for holes

Source code

Example output

Here is some example output of a complex polygon. Processing took about 2 ms on a 2GHz CPU.

Back