1

Unfortunately I cannot find a C++ (or C or C#) library for performing Delaunay triangulations on a set of points (2D or 2.5D) which is able to deliver the output in an input-aware manner.

That is, given a set of points P_1, P_2, .. P_N, the output should consist of a set of triplets (a triangle soup) (i_a, i_b, i_c), where i_a, i_b and i_c are the indices of the P_i points (hence numbers between 1 and N). I've tried Fade2D, but I've found it very wasteful in terms of how it handles input (one has to pack vertices in its own point2d structure), and the output disregards whatever indexing the input had, delivering a set of coordinates together with another ordering of these vertices.

teodron
  • 1,410
  • 1
  • 20
  • 41
  • Try http://www.cs.cmu.edu/~quake/triangle.html or http://www.netlib.org/voronoi/. – lhf Dec 07 '13 at 17:57
  • See also http://stackoverflow.com/questions/1446987/lightweight-delaunay-trianguation-library-for-c. – lhf Dec 07 '13 at 18:00
  • 1
    Thanks for the links! CGAL is definitely the best choice, but it is the Kthulhu of all libraries (you need to install the kitchen sink before you even print something on the screen - it's way too far from being lightweight). Triangle, on the other hand, doesn't seem to deliver the required output either (or I just can't seem to figure it out?). – teodron Dec 07 '13 at 21:41

1 Answers1

3

I'm the author of Fade2D and this is a late answer, I was not aware of your question. You do not need to pack your coordinates into the Point2 class before you insert them. There is also an insert method that takes an array of coordinates:

void Fade2D::insert(int numPoints,double * aCoordinates,Point2 ** aHandles);

This method takes an array of coordinates (x0,y0,x1,y1,...,xn,yn) and returns a vector of Point2* pointers that has exactly the same order. That's virtually no overhead. For your convenience, you can use

Point2::setCustomIndex() and

Point2::getCustomIndex()

to store and retrieve your own indices.

Geom
  • 827
  • 4
  • 15
  • 1
    Thanks for the answer, it's never too late to share this kind of information for the community to benefit from! Congrats for this fine tool :). – teodron Jun 15 '14 at 09:46