Delaunay Triangulation

This is yet another homework programming assignment (IGAD). This time it's about algorithms. We had to make a delaunay triagulator. Obviously, that is not enough for me, so I did a little more and added a voronoi diagram and some nifty zoom functions. The voronoi diagram has some flaws (the infite edges intersect eachother and keep on going). Did not have time left for that, but the lecturer didn't mind it.

Category:

Gaming

Tags:

• Delaunay
• Triangulation
• Voronoi
• IGAD

[llascha]

I accidently deleted a comment by Blasconelt, but it was still saved in my inbox, here it is:

"very nice job !! What algorithms did you use ?

I agree with the previous comments, the program runs very fast !!

I also like the voronoi diagram which is not easy to implement.

But I am sorry to tell you that the triangulation has some problems, a Delaunay Triangulation always forms a convex hull and in this case, it doesn't always."

[llascha]

@llascha I used an algorithm by Sjaak Priester. Googling him along with delaunay triangulation should give you a page on codeguru where he explains his algorithm in detail. When points are inserted the whole triangulation is recalculated; adding points was not even part of the assignment let alone optimizing the insertion of another point with sectors. I used the set container in stl which makes sure that the vertices are shared, boost has a faster set container.

[llascha]

@llascha Lastly, the voronoi is indeed not easy to implement, but once you have the the delaunay calculated then it is very easy. For this I did not use any particular algorithm I found, but made up my own which goes something like this (see next post, not enough characters...)

[llascha]

@llascha

If i remember correectly it was something like this for the voronoi:

for each edge from in daulanay triangulation

-- if edge has a triangle at both sides

---- create an edge by connecting the center points of the triangles circumcircles

-- else if the edge only has one triangle

---- create an edge from that triangles' center to infinity in the direction of the center of the edge

[llascha]

@llascha

Exceptions to that voronoi algorithm:

1) Vertex can lie outside of triangle in which case you will be extending towards infinity in the wrong direction. Resolution: count amount of intersections with edges, if its more more than one, inverse direction.

2) Lines going towards infinity have to intersect. Resolution: calculate intersection point and create an additional edge going into the new direction

[LAnonHubbard]

Very impressive. Smooth and fast. Thanks for including information on your sources/methods. I thought Voronoi was typically computed first then Delaunay from Voronoi, but reading your comments suggests that might not be the case here. I'm at the early stages of studying but need to get my head around it pronto.

[TimJSwan89]

I really liked this! So how did you make it run so quickly? Are each point an object and when you insert one does it only try to calculate the points in the sector that you clicked?