Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Quadtree algorithm.  An image-space algorithm.
Picture
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.


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.



Picture
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.

Download
Proudly powered by Weebly