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?

Do you need it to be a library, or could a standalone program be ok? — Camille, Sep 19 '09 at 15:20
A standalone program would probably not be ok. I am looking to integrate this into a larger software tool. — Andrew Prock, Sep 19 '09 at 17:26

score 12 · Accepted Answer · answered Sep 19 '09 at 15:37

12

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

answered Sep 19 '09 at 15:37

Camille

1,670
11
11

1

Thank you for pointing me to Triangle. It's a very straightforward and easy to use. – Andrew Prock Sep 21 '09 at 18:32
Could any of these approaches be used in a native iPad app? – Andre Jun 15 '13 at 10:38
@AndrewProck did you use it as a lib ? because I don't find any code example using this triangle lib – jokoon Nov 20 '13 at 19:54
main is in triangle.c – Andrew Prock Nov 20 '13 at 20:09
I don't really see if you can use CGAL as a library, I don't really know what to link against – jokoon Nov 21 '13 at 14:16
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? – Nick X Tsui Feb 12 '14 at 22:14
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. – Nick X Tsui Feb 16 '14 at 21:30

score 3 · Answer 2 · edited Feb 04 '17 at 16:54

3

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

edited Feb 04 '17 at 16:54

Saullo G. P. Castro

56,802
26
179
234

answered Sep 22 '12 at 19:37

prideout

2,895
1
23
25

this is for constrained delaunay, I'm not sure this will work if you use a random set of points. – jokoon Nov 21 '13 at 14:14

timday · Answer 3 · 2011-08-17T22:58:45.127

0

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.

edited Aug 17 '11 at 22:58

answered Aug 17 '11 at 22:50

timday

24,582
12
83
135

Lightweight Delaunay trianguation library (for c++)

3 Answers3

Linked