• #### Improvement for convex result

Posted by Wolfgang Ortmann on 06/13/2013 06:02am

The solution mentioned by airproject increases the probability to get the convex hull as border of the result. For a real solution of that problem one has to go further and use the "infinite point" Pi instead of the supertriangle. Than you can start with two points P1 and P2 and the two "infinite" Triangles P1P2Pi and P2P1Pi, consisting of two finite and the infinite point. The algorithm remains nearly the same. The circumcirle of the infinite triangles is the straight line determined by the two finite points and inside means "to the right of that line". An implementation of the Delaunay triangulation based on the original idea and including my improvement is part of the Version 7.0Beta of the image analysis library ICE, available on http://www.inf-cv.uni-jena.de/Lehrstuhl/Software/ICE/Download.html (LGPL). Regards, Wolfgang (wolfgang.ortmann@uni-jena.de)

• #### Improvement for convex result

Posted by airproject on 04/09/2013 05:52am

As some already noticed, there is an issue with this algorithm. In some particular cases of vertices positions, the resulting set of triangles might create concave structure. The cause of such behaviour is the initial supertriangle. In this implementation, it is reduced to the size that is just enough to enclose all vertices. This makes it highly probable to have a significant triangles formed with the supertriangle vertices, and have them deleted in the finalizing step. If the supertriangle was much bigger than the spread of the input vertces (dx, dy), the algorithm would create the triangles in a convex fashion. Simple solution found in Gilles Dumoulin's implementation is to initialize the supertriangle as follows: REAL dMax = (dx dy) ? dx : dy; REAL xMid = (xMax + xMin) / 2.0; REAL yMid = (yMax + yMin) / 2.0; vSuper[0] = Vertex(xMid - 20 * dMax, yMid - dMax); vSuper[1] = Vertex(xMid, yMid + 20 * dMax); vSuper[2] = Vertex(xMid + 20 * dMax,yMid - dMax); This mod should sort out the convexity issue.

• #### artist

Posted by Denyse Le Blanc on 01/05/2013 10:23am

One day while just rinsing my eyes in admiration with Robert Delaunay, I came upon Delaunay triangulation. Could you send me a download to triangulate pictures? thank you Denyse

• #### Worked great

Posted by Jan Ekholm on 08/22/2012 12:12am

I implemented the algorithm just to test how the Delaunay algorithm works and it seems to work perfectly. The only small issue is the need for the "super triangle(s)". You do not always have those bounding triangles when you start. Anyway, the visualization is really great and made it absolutely trivial to implement!

• #### performance time

Posted by posthumus on 06/29/2012 03:09am

hey the time displayed at the bottom-left corner of the screen...... is it the time of the -- total process - ( triangulation + display) or only triangulation

• Posted by Francois Bilodeau on 04/08/2012 12:10pm

Real great and so fast. I compile it with Visual Studio and it worked But I want to integrate Delaunay.cpp with a project in QT I am using the QT4.8 sdk by nokia and compiling with minGW Everything goes well but for 2 lines using the same function remove_if in you code around line 273: tIterator itEnd = remove_if(workset.begin(), workset.end(), triangleIsCompleted(itVertex, output, vSuper)); I get this message from minGW: c:\qtsdk\mingw\bin\..\lib\gcc\mingw32\4.4.0\include\c++\bits\stl_algo.h:-1: In function '_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = std::_Rb_tree_const_iterator, _Predicate = triangleIsCompleted]': c:\qtsdk\mingw\bin\..\lib\gcc\mingw32\4.4.0\include\c++\bits\stl_algo.h:1161: erreur : passing 'const triangle' as 'this' argument of 'triangle Reply

• #### Problem with VIsual Studio 2010

Posted by PabloLiberman on 08/18/2011 02:34am

Hi, I try to use this demo in VIsual Studio 2010 and the remove_if makes bugs, somebody try to run it in vs2010? (it makes compilation bug)

• #### I solved a problem.

Posted by Becky on 01/28/2013 11:10pm

I solved a problem. This problem occurred because that VC2010's and VC2008 are differ. so, we should add some code that operator '=' overriding in class triangle. const triangle& operator=(const triangle &tri;) const { if (this != &tri;) { memcpy ((void*)this, &tri;, sizeof(tri)); } return *this; } have a good time :)

• #### Thank you so much!

Posted by Michal on 02/02/2013 07:59am

Great solution! have a good time :)

• #### pdg

Posted by Francois Bilodeau on 04/08/2012 01:14pm

Hello, same problem with QT and minGW microsoft does not use original algorithm.h As a way around, modify the code like this: /* FB */ tIterator itEnd; /* FB */ for ( itEnd = workset.begin(); itEnd != workset.end(); itEnd++) /* FB */ triangleIsCompleted(itVertex, output, vSuper); /* FB */ -- itEnd; //FB tIterator itEnd = remove_if(workset.begin(), workset.end(), triangleIsCompleted(itVertex, output, vSuper)); edgeSet edges; // A triangle is 'hot' if the current vertex v is inside the circumcircle. // Remove all hot triangles, but keep their edges. // FB itEnd = remove_if(workset.begin(), itEnd, vertexIsInCircumCircle(itVertex, edges)); /* FB */ tIterator itAt; /* FB */ for ( itAt = workset.begin(); itAt != itEnd; itAt++) /* FB */ vertexIsInCircumCircle(itVertex, edges); /* FB */ itEnd = --itAt; workset.erase(itEnd, workset.end()); // remove_if doesn't actually remove; we have to do this explicitly.

• #### polygon with points inside

Posted by Oliver Neuse on 09/17/2010 04:13pm

```It might be, I don't understand anything (then forget this comment), but...
try this:
input:
-3, -3
3, -3
3,  3
-3, 3
-1, 1
-1, -1
0,  0
then you reliably get 7 triangles, instead of 8
regards from germany```

• #### polygon with points inside

Posted by Oliver Neuse on 09/18/2010 11:28am

sorry, points were wrong, too late: -3, -2 3, -2 3, 2 -3, 2 -1, 1 -1, -1 0, 0

• #### How to make the surface have a convex boundary?

Posted by xiaoxiao914 on 08/03/2006 12:10am

I noticed that your result surface may not have a convex boundary. Could you tell me how to modify the algorithm to make the surface have a convex boundary? I wish you can understand me.:-) love from China