Lightweight Delaunay trianguation library (for c++) [closed]

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?

Gangway

Do you need it to be a library, or could a standalone program be ok? – Afar

A standalone program would probably not be ok. I am looking to integrate this into a larger software tool. – Gangway

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;
}

Afar

Thank you for pointing me to Triangle. It's a very straightforward and easy to use. – Gangway

Could any of these approaches be used in a native iPad app? – Rangel

@AndrewProck did you use it as a lib ? because I don't find any code example using this triangle lib – Erenow

main is in triangle.c – Gangway

I don't really see if you can use CGAL as a library, I don't really know what to link against – Erenow

I have trouble using Triangle package with VS2012 C++ x64. I generated triangle.o file, inserted triangle.c and triangle.h in my project. But I got tons of errors. How should I set it up in general? Is this package compatible with VS2012 X64? – Recreant

Do you know what changes I should make to let Triangle run in VS2012? Right now, I started a new project and inserted triangle.c, triangle.h, tricall,c, and when I compile, tons of error occurred. – Recreant

Answer 2

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

Boat

this is for constrained delaunay, I'm not sure this will work if you use a random set of points. – Erenow

Answer 3

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.

Tgroup