Saturday, June 12, 2010 0
Voronoi Diagrams by the River
So I want to make a speculative drawing of the river. But how do we go about creating a grammar for procedurally generating city maps? Looking at how generic city maps are drawn, I was thinking that one way I might approach the drawing is to come up with a Voronoi Diagram with additional internal subdivisions.
A Voronoi Diagram is a kind of decomposition of a metric space in which there is a set of specified points in the plane (Voronoi sites), and the walls of the segments of each Voronoi site are equidistant to the nearest other site.
I downloaded Marius Watz's demo of Lee Byron's Mesh Library for Processing:
Voronoi Diagram: displays the regions of space belonging to each randomly generated point.
Delaunay Diagram: displays the optimal triangulation of these points (forming a mesh)
Convex Hull: displays the perimeter line of the most extreme points
The shapes formed are sometimes called Thiessen polygons; there are very many names for this useful concept because they were discovered independently across different disciplines, and have been used in geography, geophysics, and meteorology to estimate the influence of catchment areas or watersheds.
In 1854, the physician John Snow used a Voronoi diagram to illustrate how most of the people who died in the Soho Cholera outbreak lived closer to the Broad Street pump than any other water pump and used this to persuade authorities to remove the handle of the pump to prevent more infections.
Basically, Voronoi Diagrams/Thiessen Polygons can be used to describe the influence of a point. For example, with a Voronoi diagram, one could determine the point at which it would be most ideal to build a 7-11 that would be as far as possible from all other existing convienience stores in the city. Autonomous mobile robot also use Voronoi diagrams to calculate routes which are theorectically furthest from any collisions.
I found an interesting article entitled Dynamic Segmentation and Thiessen Polygons: A Solution to the River Mile Problem which suggests that it may be more accurate to use Voronoi Diagrams/Thiessen Polygons to subdivide a river into seperate regions of influence. River Miles/Kilometres are analogous to the highway road distance markers. However, due to the meandering nature of rivers, the River Mile may not be accurate as a measure for dividing the river into regions of influence, so Thiessen Polygons make more sense because it uses spatial distribution rather than linear division.
also check out this "Voronoi City" by Santiago Ortiz built in flash based on a voronoi algorithm (found via serial consign). i like how he states that "the aim was to construct a city using the minimum information as possible"; because when we draw our own personal maps of places, we often start with very little information and mostly just vague approximations...
See Also:
Wikipedia: Voronoi Diagram
BBC h2g2: Thiessen Polygons
Geometry in Action: Voronoi Diagrams
Wolfram: Voronoi Diagram
