NetNews Usenet Archive 1992 #26/NN_1992_26.iso/spool/comp/graphics/11657

Text File | 1992-11-09 | 3.5 KB | 75 lines

Newsgroups: comp.graphics
Path: sparky!uunet!ferkel.ucsb.edu!taco!gatech!news.ans.net!newsgate.watson.ibm.com!yktnews!admin!watson!schultz.kgn.ibm.com!schultz
From: [e-mail] (schultz)
Subject: Re: What are Quad Trees?
Sender: @watson.ibm.com
Message-ID: <[e-mail]>
Date: Mon, 09 Nov 92 23:01:08 GMT
Reply-To: [e-mail]
References:  <[e-mail]>
Organization: IBM AWSD Graphics Systems
Lines: 62

In article <[e-mail]>, [e-mail] (CHAN NICODEMUS) writes:
|> I'd like to know more about Quad trees and what they are.  I have this
|> as a reading assignment for my IT class.
|>
|> What are they specifically and what applications are they suitable for?
|> How fast are they?

I'm not an expert, but......

A quadtree is a tree that can represent the spacial organization of data
by recursively subdividing a rectangle into four pieces.  So, each node
in a qt may have up to four children.

Each non-leaf node in the qt subdivides its rectangle into 4 (usually equal)
rectangles.  A leaf node contains data applicable to the entire region
represented by its rectangle.  Therefore, you only need to subdivide until
the rectangle is small enough to contain a single 'value'.

Two of the more common uses for quadtrees are:

1) Sparse representation of a 2D image or 'bitmap'.
     Say you have an array of pixels arranged in a bitmap.
     The bitmap data has 'ON' pixels filling in one of the four quadrants
     of the bitmap; the rest are off.  You would need 2 nodes - one
     to divide the bitmap into 4 and another leaf node that is the
     child of the first, containing the 'ON' value.

     If the bitmap had a single pixel on, then you would need several
     non-leaf nodes to subdivide to the point where the rectangle was the
     size of a pixel and then one for the pixel itself.

     A random "blob" of pixels might be encoded with a small tree of
     nodes.  Some leaf nodes might cover a sizeable rectangle, others
     just one pixel.

2) Quick location of the nearest neighbor.
     Because the tree essentially encodes location information, it is not
     very difficult to traverse the tree in various ways to locate a point's
     nearest neighbor.  This can be used for any application where it is
     important to find a near neighbor quickly.
     One example I saw was to "sort" vectors before sending them to a
     pen plotter with the intent of reducing "pen-up" time.  All the vector
     endpoints are placed in the quadtree.  The endpoint closest to the
     current pen position is selected next for drawing.  After drawing, the
     pen is now at the "other" endpoint's position.  The two endpoints
     for the vector are removed and the next nearest enpdoint is selected.

     The search for the nearest can be tuned to find the absolute nearest
     neighbor, or with less work, one that is "nearly" nearest.

How fast are they?  Tough to say.  I imagine that finding the nearest
neighbor is much faster with a quadtree, compared to doing distance
calculations for all the other points.  This needs to be considered in
light of the time and space needed to construct the quadtree.

There are a bunch of papers covering the properties of quadtrees.
Also, octrees are the logical extension of quadtrees into 3D.
There is a lot of material on octrees.

--
Karl Schultz                             [e-mail]
These statements or opinions are not necessarily those of IBM