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.
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 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 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...)
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
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?
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.
LAnonHubbard 1 week ago
This has been flagged as spam show
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 unlike in your demo.
BlasconeIt 1 year ago
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 1 year ago
@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 1 year ago
@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 1 year ago
@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 1 year ago
@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
llascha 1 year ago
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?
TimJSwan89 1 year ago