The Voronoi Diagram
The voronoi diagram, also called the thiessen or dirichlet tessellation,
has applications in many fields, from computer vision to archaeology.
The technical definition is as follows:
Let P be a set of points in the plane. The Voronoi polygon containing
p � P is the set of all points x in the plane for which the distance
from x to p is smaller than or equal to the distance from x to q,
for all other points q in P.
A non-technical definition might go as follows. Imagine a set of cities,
situated at a set of points P. Each city has its own king. Suppose now
peasants in the countryside all pledge their loyalty to the king of the
nearest city. If a cartographer were to draw a map of the land, where would
the borders of the kingdoms be? The cartographer would end up drawing the
voronoi diagram of the cities. In fact, archaeologists have used this very
technique to approximate the boundaries of ancient civilizations.
The DotPlacer Applet (on this site) allows you to
place a set of points on the screen, and have it draw the voronoi diagram
for you. You can even move the points around, and watch the diagram change.
I used the following algorithm to draw the voronoi diagram. First of all,
for each set of three points, I calculate the orthocentre of the three points.
That is, I calculate the point which is equidistant from all three points.
Then, for each orthocentre x, I check all the points in P, to make sure that the three points used to find x are the three closest points of P to x. If they are not, I reject x from consideration. It is not needed to draw the voronoi diagram.
Then, for each orthocentre x not rejected, I find another orthocentre y which "matches" x in the sense that it if x is the orthocentre of pi, pj and pk, then y is the orthocentre of two of these three points (and another point from P). If matches yij, yjk and yki are found for x, I draw a line between x and y. Otherwise, suppose there was no match yij sharing pi and pj with x. Then I draw a ray from x, perpendicular to the line between pi and pj. Roughly speaking, that's the algorithm I use.
This algorithm is certainly not the most efficient one available for
constructing the voronoi diagram, but it works.
The voronoi diagram is very closely related to the
This being the case, the same calculations used to construct the voronoi
diagram are also used to draw the delauney triangulation.
For more information on the voronoi diagram, see this
World of Mathematics article.
r perhaps you'd like a solid text on the subject? Clicking the book on the left will
allow you to get one that covers Voronoi diagrams, and other topcis, in depth.
The book on the right, with code samples and good explanations,
is regarded by many as one of the best books around for
applying java (and smalltalk) to numerical methods. Enjoy!
Perhaps you'd like to read about the time I calculated some of the Voronoi diagram of the Ulam Prime Spiral?
File translated from TEX by TTH, version 2.25.