# Delaunay Triangulation

There are many delaunay triangulation libraries, but not all have a good cross platform build sytem, some have memory leaks or others are just buggy. I've tested and worked with several libraries that provide triangulation, like:

From this list I found Triangle to work best for me because it's compact, is fast, compiles easily and doesn't have any dependencies. It takes some time to read through the documentation, which is mostly found in the triangle.h file.

Triangle comes ase a library and as a application. To use Triangle as a library and not as a command line tool, you need to add the triangle.c to your project. It's also important to know that you need to define some compiler flags when you want to embed the triangle.c in your project. I'm using single floating point precision and therefore added these definitions:

-DTRILIBRARY -DSINGLE

Even when you use Triangle as a library and not as a command line tool you need to pass certain "flags" to the library. I found these the most important ones:

- z: will use indices which start at 0 instead of 1.
- Q: quiet, not verbose output
- p: creates constrained delaunay (use this when you want to triangulate finger like shapes)
- a: imposes a maximum triangle area constraint.

Some examples with flags:

`zpa100`

`zp10000`

`za100`

There are known issues with Triangle and the author is aware of this. The code below is a workaround for these issues. Below you can find the Triangulate class which is a thin wrapper around Triangle. The comments in Triangulate.h show an example of how to use the generated triangles. See this gist for an example of how to use this wrapper.

*Triangulate.h*

/* --------------------------------------------------------------------------------- oooo `888 oooo d8b .ooooo. oooo ooo 888 oooo oooo `888""8P d88' `88b `88b..8P' 888 `888 `888 888 888 888 Y888' 888 888 888 888 888 888 .o8"'88b 888 888 888 d888b `Y8bod8P' o88' 888o o888o `V88V"V8P' www.roxlu.com www.apollomedia.nl www.twitter.com/roxlu --------------------------------------------------------------------------------- */ #ifndef ROXLU_TRIANGULATE_H #define ROXLU_TRIANGULATE_H /* Triangulate --------------------------------------- - ! ADD THESE TO YOUR PREPROCESSOR FLAGS: -DTRILIBRARY -DSINGLE - ! AFTER CALLING `Triangulate::triangulate()` MAKE SURE TO CALL `Triangulate::free(out)` TO CLEAN MEMORY! - ! TRIANGLE MAY CRASH, SEE THIS PAGE: http://www.cs.cmu.edu/~quake/triangle.trouble.html WHEN YOU WANT TO TRIANGULATE A CONTOUR, A QUICK FIX WOULD BE TO NOT ADD EVERY POINT, BUT E.G. EVERY 5TH ELEMENT. <example> Triangulate tri; struct triangulateio out; tri.triangulate("zpQ", out); std::vector<vec2> vertices; // Extract the triangles (you could use a GL element buffer for(int i = 0; i < out.numberoftriangles; ++i) { int a = out.trianglelist[i * 3 + 0]; int b = out.trianglelist[i * 3 + 1]; int c = out.trianglelist[i * 3 + 2]; vec2 pa(out.pointlist[(a * 2) + 0], out.pointlist[(a * 2) + 1]); vec2 pb(out.pointlist[(b * 2) + 0], out.pointlist[(b * 2) + 1]); vec2 pc(out.pointlist[(c * 2) + 0], out.pointlist[(c * 2) + 1]); vertices.push_back(pa); vertices.push_back(pb); vertices.push_back(pc); } tri.free(out); </example> Very thin wrapper around the [Triangle library](http://www.cs.cmu.edu/~quake/triangle.html). Important: ---------- After calling Triangualate::triangulate(out), make sure to call Triangulate::free(out) to free up all allocated memory. Of course call Triangulate::free(out), after you've used the data. Usefull options --------------- The triangulate() options expects a string with a couple of characters; where each character defines how the triangulation is done. These are the ones I use most often: - Q Suppress verbose output - p Use this when you want to create "hand" like shapes instead; it will fit the contour basically - a Imposes a maximum triangle area. See: http://www.cs.cmu.edu/~quake/triangle.switch.html for more infor. Examples: --------- - tri.triangulate("zpQ", out); See: http://farm6.staticflickr.com/5504/11995424136_da15c9c991.jpg - tri.triangulate("zpa100", out); See: http://farm6.staticflickr.com/5530/11994959684_43678280ea.jpg - tri.triangulate("zpa10000", out); See: http://farm4.staticflickr.com/3814/11994889643_2d5275765e.jpg - tri.triangulate("za100", out); See: http://farm4.staticflickr.com/3828/11994889833_05cf0984a6.jpg Notes: ----- You need to look into the source to figure out how to use the triangulation library in an application as an library and not just the executable. Before you include the `triangle.h` file, you need to set some #defines, so include like this: <code> extern "C" { # define REAL float # define ANSI_DECLARATORS # define VOID void # include "triangle.h" } </code> Also add these to you compiler flags: <code> -DTRILIBRARY -DSINGLE <code> References: ----------- [0] http://www.cs.cmu.edu/~quake/triangle.html [1] http://www.cs.cmu.edu/~quake/triangle.switch.html [2] http://www.math.umbc.edu/~rouben/2011-01-math625/triangle-demo2.c */ extern "C" { # define REAL float # define ANSI_DECLARATORS # define VOID void # include "triangle.h" } #include <vector> #include <string> #ifndef TRIANGULATE_MIN_DIST # define TRIANGULATE_MIN_DIST 10 #endif #define TRIANGULATE_MIN_DIST_SQ (TRIANGULATE_MIN_DIST * TRIANGULATE_MIN_DIST) namespace rx { // ---------------------------------------------------- struct segment_point { segment_point(float x, float y, size_t dx) : x(x), y(y), dx(dx) { } float x; float y; size_t dx; }; struct tri_point { tri_point(float x, float y) : x(x), y(y) { } float x; float y; }; bool is_equal(const segment_point& p1, const segment_point& p2); bool lex_equal(const segment_point& p1, const segment_point& p2); bool segment_sort(const segment_point& p1, const segment_point& p2); // ---------------------------------------------------- class Triangulate { public: Triangulate(); void add(float x, float y); /* Add a point that you want to use to triangulate */ bool triangulate(std::string opt, struct triangulateio& out); /* Triangulate the points you added. We set the `struct triangulateio& out`. See Triangle documentation for the data which is set; or you see the example above */ void free(struct triangulateio& out); /* Free the `struct triangulateio` that you passed to `triangulate()`. Make sure to call this!! */ size_t size(); /* Return the number of points added */ void clear(); /* Clear the points you've added */ public: std::vector<segment_point> in_points; }; inline size_t Triangulate::size() { return in_points.size(); } inline void Triangulate::clear() { in_points.clear(); } inline bool is_equal(const segment_point& p1, const segment_point& p2) { float dx = p1.x - p2.x; float dy = p1.y - p2.y; float d = (dx * dx) + (dy * dy); if(d < TRIANGULATE_MIN_DIST_SQ) { return true; } return false; } inline bool lex_equal(const segment_point& p1, const segment_point& p2) { return (p1.x < p2.x) || ((p1.x == p2.x) && (p1.y < p2.y) ); } inline bool segment_sort(const segment_point& p1, const segment_point& p2) { return p1.dx < p2.dx; } } // namespace rx #endif

*Triangulate.cpp*

#include <Triangulate.h> #include <string> #include <algorithm> #include <stdlib.h> #include <set> namespace rx { // --------------------------------------------------------------- Triangulate::Triangulate() { } void Triangulate::add(float x, float y) { segment_point p(x, y, in_points.size()); in_points.push_back(p); } bool Triangulate::triangulate(std::string opt, struct triangulateio& out) { if(!in_points.size()) { return false; } std::vector<segment_point> sorted_points; std::vector<segment_point> clean_points; // sort + unique will remove lots of points we don't want std::sort(in_points.begin(), in_points.end(), lex_equal); std::vector<segment_point>::iterator it_unique = std::unique(in_points.begin(), in_points.end(), is_equal); std::copy(in_points.begin(), it_unique, std::back_inserter(sorted_points)); // now remove other points which are still to close for(size_t i = 0; i < sorted_points.size(); ++i) { bool can_add = true; segment_point& a = sorted_points[i]; for(size_t j = 0; j < clean_points.size(); ++j) { segment_point& b = clean_points[j]; float dx = a.x - b.x; float dy = a.y - b.y; float d = (dx * dx) + (dy * dy); if(d < TRIANGULATE_MIN_DIST_SQ) { can_add = false; break; } } if(can_add) { clean_points.push_back(a); } } // sort again, now on segment again. std::sort(clean_points.begin(), clean_points.end(), segment_sort); in_points.clear(); std::vector<tri_point> tri_points; for(size_t i = 0; i < clean_points.size(); ++i) { segment_point& p = clean_points[i]; tri_points.push_back(tri_point(p.x, p.y)); in_points.push_back(segment_point(p.x, p.y, in_points.size())); } if(tri_points.size() < 3) { printf("Not enough points to triangulate.\n"); return false; } std::vector<int> edges; for(size_t i = 0; i < tri_points.size() - 1; ++i) { edges.push_back(i); edges.push_back(i + 1); } edges.push_back(edges.back()); edges.push_back(0); struct triangulateio in = { 0 } ; // initialize a nice clean out list out.pointlist = NULL; out.pointattributelist = NULL; out.pointmarkerlist = NULL; out.numberofpoints = 0; out.numberofpointattributes = 0; out.trianglelist = NULL; out.triangleattributelist = NULL; out.trianglearealist = NULL; out.neighborlist = NULL; out.numberoftriangles = 0; out.numberofcorners = 0; out.numberoftriangleattributes = 0; out.segmentlist = NULL; out.segmentmarkerlist = NULL; out.numberofsegments = 0; out.holelist = NULL; out.numberofholes = 0; out.regionlist = NULL; out.numberofregions = 0; out.edgelist = NULL; out.edgemarkerlist = NULL; out.normlist = NULL; out.numberofedges = 0; out.pointlist = NULL; out.pointmarkerlist = NULL; in.pointlist = (float*)&tri_points[0].x; in.numberofpoints = int(tri_points.size()); if(edges.size()) { in.segmentlist = &edges.front(); in.numberofsegments = edges.size() / 2; } ::triangulate((char*)opt.c_str(), &in, &out, NULL); return true; } #define TRIANGULATE_FREE(e) { if (e) { ::free(e); e = NULL; } } void Triangulate::free(struct triangulateio& out) { TRIANGULATE_FREE(out.pointlist); TRIANGULATE_FREE(out.pointmarkerlist); TRIANGULATE_FREE(out.pointattributelist); TRIANGULATE_FREE(out.trianglelist); TRIANGULATE_FREE(out.triangleattributelist); TRIANGULATE_FREE(out.trianglearealist); TRIANGULATE_FREE(out.neighborlist); TRIANGULATE_FREE(out.segmentlist); TRIANGULATE_FREE(out.segmentmarkerlist); TRIANGULATE_FREE(out.holelist); TRIANGULATE_FREE(out.regionlist); TRIANGULATE_FREE(out.edgelist); TRIANGULATE_FREE(out.edgemarkerlist); TRIANGULATE_FREE(out.normlist); out.numberofpoints = 0; out.numberofpointattributes = 0; out.numberoftriangles = 0; out.numberofcorners = 0; out.numberoftriangleattributes = 0; out.numberofsegments = 0; out.numberofholes = 0; out.numberofregions = 0; out.numberofedges = 0; } } // namespace rx