Menu
I am implementing Voronoi diagram to find out the nearest location in a map visually. Right now I want to do this using integer coordinates (x,y) only in a canvas.
Problem is- I am really confused about this algorithm. I read the Computational Geometry book, few more theory on Fortune's algorithm. And I am really confused now. It seems very complex to me when I am going for coding.
Please advice me very simple implementation of voronoi diagram (with given coordinates). Please advice me simple java or python or scheme code preferably without- hash, multi-threading, Delaunay Traingulation, fancy colors etc.
Isn't it possible to implement Voronoi diagram using Fortune's algorithm without multithreading or hash map?
756
A Voronoi diagram is a collection of geometric regions that encapsulate classifying points in such a way that any point within the region is closest to the encapsulated classifier than any other adjacent classifiers based on their distance from one another.
Generalized Voronoi Diagram: A Geometry-Based Approach to Computational Intelligence.
Voronoi diagrams were considered as early as 1644 by philosopher René Descartes and are named after the Russian mathematician Georgy Voronoi, who defined and studied the general n-dimensional case in 1908. This type of diagram is created by scattering points at random on a Euclidean plane.
What is the farthest-point Voronoi diagram? The farthest-point Voronoi diagram of a finite set of points P (usually called "sites"), is a decomposition of the plain in regions. Each region is characterized by being the geometric location of the points which the farthest site is the site itself.
I opened a github repository with a port of Fortune's original paper. Fortune's implementation was very tough to follow mostly due to how he handled data structures.
This book appears a lot more modern
Fortune's original paper requires a few reads.
Ken Wong's paper describes the algorithm with arguably more clarity than Fortune in the original paper
Ken Wong's presentation has great slides (10, 11) on how to process a site and a vertex
There is an interactive JavaScript demo (Archived version) you can watch to help you visualize the algorithm.
A pdf (Archived version) describes the algorithm as well.
Steven Fortune's original implementation is on his homepage.
This Stony Brook site lists more implementations
Triangle is "A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator."
There is an entire book called "Spatial Tesselations Concepts and Applications of Voronoi Diagrams" by Atsuyuki Okabe, Barry Boots et al on Voronoi diagrams
189
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
