# Delaunay Traingulation

This topic is 1065 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm using a Voronoi Diagram for map generation, but the way I came to my Voronoi Diagram is incredibly dirty; I solved for the pixels within the polygons and not actually the vertices of the polygons.  I then solve the vertices backwards.  This takes an eon and occasionally fails to solve for vertices and adjacent polygons.

I've looked at tutorials and explanations regarding Voronoi diagrams and Delaunay Triangulation and I understand how they work and I can draw them out on graph paper, but I'm having trouble putting these into an algorithm that produces a proper Voronoi Diagram.  Obviously, this has been done before, but all of the tutorials I've found skip steps.

I'll write out what my thoughts are so far and questions regarding each part.  Please let me know where my logic falls short or if you know an answer to my question.

Set -> n random points on a dSizeX x dSizeY grid

My thoughts on a solution:

-For each point (Pn) find all other points with that have non-crossing lines to (Pn)

+The only solution I had for this was to make a line to all other points and cull out all that cross, keeping the lines that have closer points to Pn.  This seems like an incredibly inefficient way to do this.  Is there a better solution?

-Find the bisecting perpendicular line to all lines left over [I've got this]

-Find the intersections between all bisecting perpendicular lines to solve for Voronoi Vertices of the polygon. [I've got this]

If you have any comments, suggestions or links to tutorials that you think would be helpful, I would greatly appreciate it.  Also, if there's a simpler solution, I would be grateful for direction.

Thank you!

Here's a screenshot of my dirty diagram where I colored all polygons random colors:

##### Share on other sites

Just a quick question, do you want a Delaunay Triangulation, like your title suggests, or do you want a Voronoi mesh, like your post suggests? If you're calculating a Voronoi with the end goal of turning it into a Delaunay, then there are far easier ways to do it.

The only issue with your Voronoi algorithm is that your first step essentially requires you to make a Delaunay triangulation. Keep in mind that just because you can find create an arbitrary triangulation over a set of points doesn't mean that you are creating the inverse of the corresponding Voronoi diagram, which is what you need. Everything else about it seems like it should do the trick.

Fortunately, you can construct a Delaunay very easily by:

1) creating an arbitrary triangulation. There are many ways to do this, but the easiest way is to append and subdivide triangles as you add points to the triangulation. I can elaborate on that if you need.

2) edge flip 'till you can't flip no more ( http://en.wikipedia.org/wiki/Delaunay_triangulation#Visual_Delaunay_definition:_Flipping )

Hope this helps!

Edited by CulDeVu

##### Share on other sites

The only issue with your Voronoi algorithm is that your first step essentially requires you to make a Delaunay triangulation

I actually came to this realization after working on this problem a few more hours!  I also see that my title is inaccurate/misleading.  My apologies.  I want to make a Delaunay Triangulation so that I can make a Voronoi Diagram.

Now I'm struggling to produce a Delaunay Traingulation.  I'm trying to make my initial set of triangles by adding points randomly to the grid.  If the point is inside of the triangle, then the triangle splits into three smaller triangles.  If it is outside of another triangle then it finds the two nearest points and makes a new triangle with them.

This is not working at all.  I don't understand Barycentric Coordinates, so I opted for a summation of internal areas with the new Point compared to the total area of the triangle.  This fails miserably, however the math my be wrong.

I'm using Area(Triangle) = |p1X*(p2Y-p3Y)+p2X(p3Y-p1Y)+p3X(p1Y-p2Y)|/2

Is there a better way to make a field of Triangles?

I've seen this concept of edge flipping in my travels.  I haven't been able to wrap my head around it well enough to turn it into code. Do you have a simplish explanation for what is going on?

##### Share on other sites

long time ago i did a program that made out of such image a mesh firstly i had to find all corners of a poly, to do that i firstly found every edge pixel of the shape, then going through them i just found if theresdifferent vector (other than old one) thats a little hard for me to explain where a pixel is surrounded by a pixel which is at 1,1 from the original pixel and when you cant find that pixel there you search for another (but cant be -1,-1) when you find it you add new vertex then after collecting all corners (and with most cases with additional one vertex because you can start anywhere on the edge) you add every vertex pos divide it by the amout and you get the center point (well it works only for convex) then its obvious how to make a mesh out of that

##### Share on other sites

long time ago i did a program that made out of such image a mesh firstly i had to find all corners of a poly, to do that i firstly found every edge pixel of the shape, then going through them i just found if theresdifferent vector (other than old one) thats a little hard for me to explain where a pixel is surrounded by a pixel which is at 1,1 from the original pixel and when you cant find that pixel there you search for another (but cant be -1,-1) when you find it you add new vertex then after collecting all corners (and with most cases with additional one vertex because you can start anywhere on the edge) you add every vertex pos divide it by the amout and you get the center point (well it works only for convex) then its obvious how to make a mesh out of that

I'm not quite sure what you're trying to say.  I'm looking to make a Voronoi type mesh because they have properties that not only make a great map from world gen, but also assist in higher order map problem solving.  Random poly's isn't exactly what I'm looking for.  I appreciate the response :)

##### Share on other sites

An easy way (but a bit slow) that I did it was to use the edge circumcircle property.  From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle.  So this makes for a pretty easy brute force algorithm.  For each candidate edge you simply count the number of vertices in its circumcircle.  Once you have your edges you can easily form triangles, or a Voronoi or what-have you.

##### Share on other sites

One point: you don't need to find a Delaunay triangulation if what you really want is the Voronoi mesh. The Bowyer–Watson algorithm is one way to find a Voronoi diagram via the Delaunay triangulation, but you can also use Fortune's algorithm or one of the other methods (like an incremental method) that don't involve Delaunay triangulation at all.

Edited by ikarth

##### Share on other sites

Now I'm struggling to produce a Delaunay Traingulation.  I'm trying to make my initial set of triangles by adding points randomly to the grid.  If the point is inside of the triangle, then the triangle splits into three smaller triangles.  If it is outside of another triangle then it finds the two nearest points and makes a new triangle with them.

This is not working at all.

I'm not sure what's wrong with this, because this is completely correct, at least to create an arbitrary triangulation. You don't need to know baycentric coordinates to make it work, though. If your triangles are in counter-clockwise winding, a triangle with verts A, B, and C would be split as such: http://i.imgur.com/PNNEtkf.png

I've seen this concept of edge flipping in my travels.  I haven't been able to wrap my head around it well enough to turn it into code. Do you have a simplish explanation for what is going on?

Sure, I'll take a whack at it.

There are many ways to triangulate a set of points. Delaunay triangulation is a specific type of triangulation that seeks to maximize the minimum angle of each triangle, to avoid skinny triangles. Now, this doesn't necessarily mean that it's the correct or the only way of avoiding skinny triangles, it's just one method. See here for a more complete list of different ways to create optimal triangulations: http://en.wikipedia.org/wiki/Point_set_triangulation#Time_complexity_of_various_algorithms

So, in an effort to maximize the minimum angle, and taking advantage of the Delaunay property of circles, the easiest way to go about turning a random triangulation into a Delaunay one is to compare and correct adjacent triangles together. Something like:

for every pair of adjacent triangles
if they aren't delaunay
make them delaunay


, which is actually really nice. Not many other triangulation methods that I know of become correct just by correcting triangles piecewise like this.

The "make delaunay" step is the key here. It just so happens that the easiest way to make a non-Delaunay pair of adjacent triangles correct again is to turn the exterior vertices into interior vertices and vice versa

Hope that helped a little!

Edited by CulDeVu

##### Share on other sites

i meant to go through edge of every polyogn and if its a huge/big/decent change in the angle which you were fololoowing you add a vertex for that polygon, you can always disable the issue with additional vertex for the poly by finding first change and begin from that. no random polies are generated

##### Share on other sites

I think you're better off using Fortune's algorithm. Not only do you get exactly what you're after, the time complexity is pretty good.

##### Share on other sites

I'm working on exactly your problem for my honours project. I've found that the code here http://www.skynet.ie/~sos/mapviewer/voronoi.php is easier to use than Fortune's original C code. I've modified it to output vectors of the input points, the edges, and the end points of the edges. The end points for the edges are joined together, so if two lines end at the same point, the line class points to the same end point. I could send you my code if you'd like.

Edited by viper110110

##### Share on other sites

An easy way (but a bit slow) that I did it was to use the edge circumcircle property.  From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle.  So this makes for a pretty easy brute force algorithm.  For each candidate edge you simply count the number of vertices in its circumcircle.  Once you have your edges you can easily form triangles, or a Voronoi or what-have you.

I've actually read through this text and found that the technical language is over my head.  As well, it doesn't provide step by step solutions to the problems, but rather general descriptions.  I'm sure these descriptions are the only road map an experienced programmer with a formal education in upper-lever math would need.  But I'm entirely self taught, so the nomenclature kills me.

So, in an effort to maximize the minimum angle, and taking advantage of the Delaunay property of circles, the easiest way to go about turning a random triangulation into a Delaunay one is to compare and correct adjacent triangles together. Something like:
for every pair of adjacent triangles
if they aren't delaunay
make them delaunay
, which is actually really nice. Not many other triangulation methods that I know of become correct just by correcting triangles piecewise like this.

The "make delaunay" step is the key here. It just so happens that the easiest way to make a non-Delaunay pair of adjacent triangles correct again is to turn the exterior vertices into interior vertices and vice versa

This makes 100% sense.  I got it!  I also solved the whole Point within a triangle business, but found that clicks out side of the triangle are much harder to handle!  Right now I make a traingle with triangle edge with the nearest bisecting point.  This works for the first few, but falls apart.  I'm not sure how to solve for clicks outside of the trianlge.

##### Share on other sites

i meant to go through edge of every polyogn and if its a huge/big/decent change in the angle which you were fololoowing you add a vertex for that polygon, you can always disable the issue with additional vertex for the poly by finding first change and begin from that. no random polies are generated

Do you have an example I could see?

I'm working on exactly your problem for my honours project. I've found that the code here http://www.skynet.ie/~sos/mapviewer/voronoi.php is easier to use than Fortune's original C code. I've modified it to output vectors of the input points, the edges, and the end points of the edges. The end points for the edges are joined together, so if two lines end at the same point, the line class points to the same end point. I could send you my code if you'd like.

This is a great link!  Thank you so much!  I'm not quite sure how this works though, because I don't understand the data types that are being used.  I'm using edges and vertices as well.   How is this solving for the edges?

I would greatly appreciate it if I could take a look at how you solved this!

##### Share on other sites

I would greatly appreciate it if I could take a look at how you solved this!

https://www.dropbox.com/s/3nb5lkh8yybrlbs/voronoi%20stuff.zip?dl=0

That should contain everything I did related to voronoi/delauny. You might also need Vector2 and Vector3 classes. Everything from the link I posted should still work. Use is as follows:

        float* xValues = new float[numNodes];
float* yValues = new float[numNodes];

for (int i = 0; i < numNodes; i++)
{
xValues[i] = RandomFloat(size);
yValues[i] = RandomFloat(size);
}

VoronoiDiagramGenerator vdg;
vdg.generateVoronoi(xValues, yValues, numNodes, 0, size, 0, size, 0.0f);

points = vdg.outputPoints;
edges = vdg.outputEdges;
edgeEndPoints = vdg.outputEndPoints;


You can access the delauny triangulation through:

points[i]->edges[j]->GetOppositePoint(points[i])


##### Share on other sites

An easy way (but a bit slow) that I did it was to use the edge circumcircle property.  From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle.  So this makes for a pretty easy brute force algorithm.  For each candidate edge you simply count the number of vertices in its circumcircle.  Once you have your edges you can easily form triangles, or a Voronoi or what-have you.

Ok, I took a swing at this and got pure chaos.  After about 5 points it really starts to go down hill.

Here's what I did:

Made All Possible Edges Between All Points

Made All Possible Unique Triangles Out of These Points

-In the Constructor of the Triangle Object I Solve for Circumcenter and Radius

Cull Out All Triangles* That Had a non-Triangle* Point Within the Circumecircle

Here's what I got [4 Points Left; 5 Points Middle; 6 Points Right: Red Dots Are Edge Midpoints and Green Circles are the Circumcircles]:

Edited by DontReferenceMyPointer

##### Share on other sites

Just a quick question, do you want a Delaunay Triangulation, like your title suggests, or do you want a Voronoi mesh, like your post suggests? If you're calculating a Voronoi with the end goal of turning it into a Delaunay, then there are far easier ways to do it.

What do you mean with that? They're each others dual, and in memory, they're often stored in the exact same way.

##### Share on other sites

An easy way (but a bit slow) that I did it was to use the edge circumcircle property.  From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle.  So this makes for a pretty easy brute force algorithm.  For each candidate edge you simply count the number of vertices in its circumcircle.  Once you have your edges you can easily form triangles, or a Voronoi or what-have you.

Ok, I took a swing at this and got pure chaos.  After about 5 points it really starts to go down hill.

Here's what I did:

Made All Possible Edges Between All Points

Made All Possible Unique Triangles Out of These Points

-In the Constructor of the Triangle Object I Solve for Circumcenter and Radius

Cull Out All Triangles* That Had a non-Triangle* Point Within the Circumecircle

Here's what I got [4 Points Left; 5 Points Middle; 6 Points Right: Red Dots Are Edge Midpoints and Green Circles are the Circumcircles]:

When you say 'point' in your algorithm you mean vertex and not mid-point right?  From your description your algorithm should work.

Try this:

- for every possible edge calculate its circumcircle (find the midpoint as you already have and then the radius)

- throw away every edge with more than 0 vertices in its circumcircle (use < and not <= as your original two points should be equal/on the circumcircle, or explicitly exclude the original two, also floating point math may mean you might need a small 'fudge'/epsilon factor here)

- create your triangles from the remaining edges

I think that should work.  Or perhaps I hope

Edited by Ryan_001

##### Share on other sites

When you say 'point' in your algorithm you mean vertex and not mid-point right?  From your description your algorithm should work.

Try this:
- for every possible edge calculate its circumcircle (find the midpoint as you already have and then the radius)
- throw away every edge with more than 0 vertices in its circumcircle (use < and not <= as your original two points should be equal/on the circumcircle, or explicitly exclude the original two, also floating point math may mean you might need a small 'fudge'/epsilon factor here)
- create your triangles from the remaining edges

I think that should work.  Or perhaps I hope

I feel like I am getting close!  I am getting some funky spaces in the middle of bunches of triangles though.  What do you think is causing this?

Here's the code I am using to solve for edges [my apologies ahead of time for lack of elegance]:

//Make Edges
for(int a=0;a<pA.size();a++)
{for(int b=a+1;b<pA.size();b++){
}}

//Cull Edges
ArrayList<Edge> cull = new ArrayList<Edge>();
for(int e=0;e<eA.size();e++)
{for(int p =0;p<pA.size();p++){
eA.get(e).remove=true;
}}}

for(int c=0;c<cull.size();c++)
{eA.remove(cull.get(c));
}

##### Share on other sites

Ok so I see what I did wrong with the previous bit of code.  I wasn't making triangles with each edges and every other point. I tried this and the only problem is that it degrades at higher numbers of points.  It doesn't even look like the same program...  What could be going wrong?

So now here's what I did:

-For Each Edge, Make A Triangle

+If that triangle's circumcircle doesn't contain any other points then add that to the list of triangles

##### Share on other sites

Yeah so, after about 30 hours of trying to figure this out, I have thrown in the towel.  I've decided to use Hexagons, which have the properties of Voronoi Polygons, so functionally this is fine.  Perhaps, though, hexagons are not at attractive.  Here's what I've got so far.

Sorry, I don't know how to edit the title, but I would say this problem has been forgone, not exactly solved haha

Edited by DontReferenceMyPointer

##### Share on other sites

So, not to be pedantic, but...what was the problem with Fortune's algorithm again?

##### Share on other sites

So, not to be pedantic, but...what was the problem with Fortune's algorithm again?

Nothing, I couldn't figure out how to implement it.  I'm sure it works, but all of the documentation/pseudo-code was over my head.