In this course, we learned the basics of Voronoi Diagrams. The concept is simple yet powerful as Voronoi Diagrams are widely used in many fields.
- Simple concept, easy to understand and to apply.
- Easy to adapt to various problems with customized distance functions.
- Voronoi Diagrams can't deal with real-time distances. A planned emergency response diagram renders useless if traffic jams affect ambulances travel time, as you would have to take all these real-time factors into account from your distance function. This would multiply the overall complexity of the algorithm.
- Resource intensive. Naive implementation is
O(n^2)complex. Fortune's algorithm is
CodinGame.com, the online gaming platform for developers, has several puzzles where you can use Voronoi Diagrams:
Many games’ AI make use of Voronoi Diagrams. Some game AI use cases include maximizing controlled area and knowing which resources can be taken faster than the enemy.
Other interesting links
Raymond Hill's Voronoi Implementation
Philippe Rivière The State of D3 Voronoi
Official D3 Voronoi Implementation
Wikipedia: Voronoi Diagram
Wikipedia: Fortune's Algorithm
Wikipedia: Delaunay Triangulation With a hard relationship with Voronoi Diagrams.
References and Credits
This course make use of external resources:
- Data-Driven Document Library, D3js
- Philippe Rivière The State of D3 Voronoi
- Raymond Hill's implementation of the fortune algorithm
(BSD License Copyright (c) 2015 Mike Bostock)
(MIT License Copyright (c) Philippe Rivière)
(MIT License Copyright (c) 2010-2013 Raymond Hill)