Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
1–10 of 34 posts
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#2My favorite algorithm for generating Voronoi diagrams is the Jumping flood algorithm:
https://en.wikipedia.org/wiki/Jump_flooding_algorithm
This is an approximate algorithm that only works in pixel space, but it's lots of fun to implement (simpler to implement than Fortune's algorithm).
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#3One of my favorite renderings of this is in this article [1], that shows the relationship between the Delaunay triangulation, Voronoi diagram, a relative neighborhood graph (RNG) and the euclidean minimum spanning tree (EMSP) of a set of 2d points.
I have a theory that the union of the edges of the RNG and EMSP could be used for automatic navigation between widgets in a GUI: combining the two, there's always between 1 and 4 edges coming out of every point, and so each of them could correspond to a direction key up/down/left/right according to some simple heuristic.
--
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#4Wow literally just what I needed to see for a project I’m working on, I love hacker news!
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#5Wow literally just what I needed to see for a project I’m working on, I love hacker news!
Same for me! I just started working on a Voronoi-based experiment[1] yesterday. This is my progress so far.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#6Wow literally just what I needed to see for a project I’m working on, I love hacker news!
Same for me! I just started working on a Voronoi-based experiment[1] yesterday. This is my progress so far. [1] https://7887885e.vorannoy.pages.dev/
It's all fun and games until you leave the euclidean plane and calculate the real distance.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#7Unfortunately, as you move into higher dimensions, these algorithms typically bog down.
Suppose that you have a point that is inside of the convex hull of the mesh that you want to use for triangulation (we‘re talking hyper-triangles here). What are the best points to choose for your triangulation? Since there are a lot of candidates for hyper-triangles you cannot possibly store the set of triangles beforehand.
I approached this problem using linear programming using the distance to the mesh points to find the best triangle. Not sure if this is the best approach though.
Happy to hear if someone knows of a better approach.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#8One of my favorite renderings of this is in this article [1], that shows the relationship between the Delaunay triangulation, Voronoi diagram, a relative neighborhood graph (RNG) and the euclidean minimum spanning tree (EMSP) of a set of 2d points. I have a theory that the union of the edges of the RNG and EMSP could be used for automatic navigation between widgets in a GUI: combining the two, there's always between…
Super cool resource! Thanks for sharing this!
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#9I would be interested in an explanation why it's O(nlog(n)).
It requires sorting the points along one axis which already gives O(nlog(n)) as a lower bound, but I'd be interested in how the line-sweeping would need to be done to not go over that.
The number of points in the beach front should roughly scale with the square root of points, so a naive search/replace per point insertion would take sqrt(n) operations and a O(n*sqrt(n)) overall runtime.
Re: Voronoi Diagram and Delaunay Triangulation in O(nlog(n)) (2020)
#10Earlier quoted context omitted.
Same for me! I just started working on a Voronoi-based experiment[1] yesterday. This is my progress so far. [1] https://7887885e.vorannoy.pages.dev/
It's all fun and games until you leave the euclidean plane and calculate the real distance.
Distance isn't so much a problem. The real problem is that the surface is closed.