Difference between revisions of "PM Quadtree"
From CMSC 420
Ben Zoller (talk | contribs) (new pm quadtree page) |
Ben Zoller (talk | contribs) (added links to example imags since i can't upload images here :() |
||
| Line 7: | Line 7: | ||
# If a quadtree leaf node's region contains no vertices, then it can contain, at most, one q-edge. | # If a quadtree leaf node's region contains no vertices, then it can contain, at most, one q-edge. | ||
# Each region's quadtree leaf node is maximal. | # Each region's quadtree leaf node is maximal. | ||
| + | |||
| + | [http://wam.umd.edu/~bzoller/cmsc420/pm1_example.png Here] is an example. | ||
== PM2 Quadtree == | == PM2 Quadtree == | ||
| Line 14: | Line 16: | ||
# If a quadtree leaf node's region contains no vertices, then it can contain only q-edges that meet at a common vertex exterior to the region. | # If a quadtree leaf node's region contains no vertices, then it can contain only q-edges that meet at a common vertex exterior to the region. | ||
# Each region's quadtree leaf node is maximal. | # Each region's quadtree leaf node is maximal. | ||
| + | |||
| + | [http://wam.umd.edu/~bzoller/cmsc420/pm2_example.png Here] is an example. | ||
== PM3 Quadtree == | == PM3 Quadtree == | ||
| Line 19: | Line 23: | ||
# At most, one vertex can lie in a region represented by a quadtree leaf node. | # At most, one vertex can lie in a region represented by a quadtree leaf node. | ||
# Each region's quadtree leaf node is maximal. | # Each region's quadtree leaf node is maximal. | ||
| + | |||
| + | [http://wam.umd.edu/~bzoller/cmsc420/pm3_example.png Here] is an example. | ||
== Applications == | == Applications == | ||
PM Quadtrees are useful in determining the region in which a point lies, the determination of the boundaries of all regions lying within a given distance of a point, and overlaying two maps. | PM Quadtrees are useful in determining the region in which a point lies, the determination of the boundaries of all regions lying within a given distance of a point, and overlaying two maps. | ||
Revision as of 05:34, 22 March 2007
A PM (Polygonal Map) Quadtree describes a collection of quadtrees that can store points and edges. A q-edge refers to a subset of an edge formed by the partitions of the PM Quadtree.
PM1 Quadtree[edit]
A PM1 Quadtree follows the following rules:
- At most, one vertex can lie in a region represented by a quadtree leaf node.
- If a quadtree leaf node's region contains a vertex, then it can contain no q-edge that does not include that vertex.
- If a quadtree leaf node's region contains no vertices, then it can contain, at most, one q-edge.
- Each region's quadtree leaf node is maximal.
Here is an example.
PM2 Quadtree[edit]
A PM2 Quadtree follows the following rules:
- At most, one vertex can lie in a region represented by a quadtree leaf node.
- If a quadtree leaf node's region contains a vertex, then it can contain no q-edge that does not include that vertex.
- If a quadtree leaf node's region contains no vertices, then it can contain only q-edges that meet at a common vertex exterior to the region.
- Each region's quadtree leaf node is maximal.
Here is an example.
PM3 Quadtree[edit]
A PM3 Quadtree follows the following rules:
- At most, one vertex can lie in a region represented by a quadtree leaf node.
- Each region's quadtree leaf node is maximal.
Here is an example.
Applications[edit]
PM Quadtrees are useful in determining the region in which a point lies, the determination of the boundaries of all regions lying within a given distance of a point, and overlaying two maps.
