Lightweight Delaunay trianguation library (for c++

Question

I'd like to play around with some (2D) Delaunay triangulations, and am looking for a reasonably small library to work with. I'm aware of CGAL, but I was wondering if there was something fairly simple and straightforward out there.

Things I would like to do:

• create a triangulation of an arbitrary set of points
• find triangle an arbitrary point is in, and fetch the vertices
• create an image of the triangulation (optional)

Suggestions?

Answer 1

You should probably detail your goals a bit, so that more relevant answers can be provided, but let me first mention Triangle, a 2D Delaunay generation tool, which is written in C, and can be used both as a standalone program, or called from your own code.

Then, about CGAL, here is a typical small example, in case you still consider it:

#include <vector>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K>                   Delaunay;    
typedef K::Point_2                                          Point;

void load_points(std::vector< Point >& points)
{
  points.push_back(Point(1., 1.));
  points.push_back(Point(2., 1.));
  points.push_back(Point(2., 2.));
  points.push_back(Point(1., 2.));      
}

int main()
{
  std::vector< Point > points;
  load_points(points);
  Delaunay dt;
  dt.insert(points.begin(), points.end());
  std::cout << dt.number_of_vertices() << std::endl;
  return 0;
}

Answer 2

I've used the Gnu Triangulated Surface library for 2D Delaunay triangulation and it worked well. Slightly strange to call because it uses that OOP-in-C GLib style, but it can easily be wrapped up.

Answer 3

See also poly2tri, it looks nice: https://github.com/greenm01/poly2tri