Delaunay Traingulation

Math and Physics Programming

Started by Tereth March 02, 2015 06:09 AM

20 comments, last by Tereth 9 years, 1 month ago

183

Author

March 02, 2015 06:09 AM

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:
Dirty%20Voronoi.jpg

CulDeVu

3,038

March 02, 2015 08:01 AM

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!

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

Tereth

183

Author

March 02, 2015 09:39 AM

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?

_WeirdCat_

1,512

March 02, 2015 09:39 AM

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

Master & Mentor
https://sites.google.com/site/customprog/

Tereth

183

Author

March 02, 2015 10:10 AM

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 :)

Ryan_001

3,477

March 02, 2015 02:44 PM

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.

ikarth

969

March 02, 2015 02:58 PM

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.

http://procedural-generation.tumblr.com/

CulDeVu

3,038

March 02, 2015 03:38 PM

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!

I'm sorry about any spelling or grammar mistakes or any undue brevity, as I'm most likely typing on my phone

"Hell, there's more evidence that we are just living in a frequency wave that flows in harmonic balance creating the universe and all its existence." ~ GDchat

_WeirdCat_

1,512

March 02, 2015 04:38 PM

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

Master & Mentor
https://sites.google.com/site/customprog/