Quadtree algorithm. An image-space algorithm.
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.
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.
|
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. Download a zipped file of all QuickTime movies described on this page by clicking the download button at the right. 
To the left, the quadtree algorithm applied to ten control points with two pixel resolution. [Too large for this site]. Click on the Download button above to download a zipped file containing all the movies described on this page.
Six control points, two pixel resolution. [Too large for this site]. Six control points, four pixel resolution. Show. Six control points, eight pixel resolution, with pauses to pose questions to the student. |