Voronoi Diagram: Quadtree algorithm

recursively descend a quadtree to assign a quad to a site

Image Space vs. Object Space

An object space algorithm works in the coordinate system of the objects, the "world," the world coordinate system.  An image space algorithm works in the coordinate system of the image, the view, usually in pixels wide by pixels high.  An image space algorithm constructs an image on the display, often in the form of a pixel-map or pixmap, and not usually in the form of a collection of objects, such as polygons, lines, etc.

A quadtree algorithm is one of the class of image space algorithms.  In a quadtree algorithm, the image is decomposed into a number of quadrilaterals, or quads, each of which has distinctive characteristics (such as color).  The object of the algorithm is to convert a scene, composed of objects, in the world space into a collection of quadrilaterals in image space.  

In particular, a quadtree algorithm collects the quads into a quadtree, which is the two-dimensional analog of a binary tree.  In a quadtree, each node is either a leaf, or it has exactly four child nodes (for example, northwest, northeast, southwest, southeast).  To draw the image, we traverse the quadtree, drawing each leaf node.

The Voronoi Diagram

A quadtree algorithm for the computation of the Voronoi diagram then works like this.  Consider a quad:  if all the pixels within the quad are closer to one particular site than to any other site, then associate that quad with that site, and prepare to color it appropriately.  If not, subdivide the quad into four smaller quads, and recursively descend until either (a) a quad has been assigned to a site, or (b) the quad is too small, and is assigned to no site.

To draw the quadtree, recursively draw each sub-quadtree; the leaves are drawn by filling a quadrilateral with a color appropriate to the site.  

Movies

Seven movies are available.  Four show the Voronoi diagram at differing resolutions for six sites; three show the Voronoi diagram at differing resolutions for ten sites.  One of the six-site movies includes pauses to pose questions to the viewer.  Remember the guidelines for the use of these movies.