Menu
What are the easy algorithms to implement Voronoi diagram?
I couldn't find any algorithm specially in pseudo form. Please share some links of Voronoi diagram algorithm, tutorial etc.
985
Voronoi diagrams have applications in almost all areas of science and engineering. Biological structures can be described using them. In aviation, they are used to identify the nearest airport in case of diversions. In mining, they can aid estimation of overall mineral resources based on exploratory drill holes.
We start by joining each pair of vertices by a line. We then draw the perpendicular bisectors to each of these lines. These three bisectors must intersect, since any three points in the plane define a circle. We then remove the portions of each line beyond the intersection and the diagram is complete.
In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators).
If you want the k nearest neighbors, there is something called an order-k Voronoi diagram that has a cell for each possible k nearest neighbors. But nobody uses those, for two reasons. First, the size of an order-k Voronoi diagram is O(k2n) in 2D, and worse in higher dimensions.
An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.
Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune's line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you're lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.
In general, a good book on the topic is Computational Geometry by de Berg et al.
123
Easiest? That's the brute-force approach: For each pixel in your output, iterate through all points, compute distance, use the closest. Slow as can be, but very simple. If performance isn't important, it does the job. I've been working on an interesting refinement myself, but still searching to see if anyone else has had the same (rather obvious) idea.
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
