Difference between revisions of "PM Quadtree"

From CMSC 420
(→‎PM3 Quadtree: added pic directly)
 
(6 intermediate revisions by 4 users not shown)
Line 2: Line 2:
  
 
== PM1 Quadtree ==
 
== PM1 Quadtree ==
[[Image:Pm1_example.png|PM1 Quadtree example]]
+
[[Image:Pm1_example3.png|PM1 Quadtree example]]
  
 
A PM1 Quadtree follows the following rules:
 
A PM1 Quadtree follows the following rules:
Line 11: Line 11:
  
 
== PM2 Quadtree ==
 
== PM2 Quadtree ==
 +
[[Image:Pm2_example3.png|PM2 Quadtree example]]
 +
 
A PM2 Quadtree follows the following rules:
 
A PM2 Quadtree follows the following rules:
 
# 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.
# 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 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.
 
# 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 ==
[[Image:Pm3_example.png|PM3 Quadtree example]]
+
[[Image:Pm3_example3.png|PM3 Quadtree example]]
  
 
A PM3 Quadtree follows the following rules:
 
A PM3 Quadtree follows the following rules:

Latest revision as of 14:36, 3 October 2014

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]

PM1 Quadtree example

A PM1 Quadtree follows the following rules:

  1. At most, one vertex can lie in a region represented by a quadtree leaf node.
  2. If a quadtree leaf node's region contains a vertex, then it can contain no q-edge that does not include that vertex.
  3. If a quadtree leaf node's region contains no vertices, then it can contain, at most, one q-edge.
  4. Each region's quadtree leaf node is maximal.

PM2 Quadtree[edit]

PM2 Quadtree example

A PM2 Quadtree follows the following rules:

  1. At most, one vertex can lie in a region represented by a quadtree leaf node.
  2. If a quadtree leaf node's region contains a vertex, then it can contain no q-edge that does not include that vertex.
  3. 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.
  4. Each region's quadtree leaf node is maximal.

PM3 Quadtree[edit]

PM3 Quadtree example

A PM3 Quadtree follows the following rules:

  1. At most, one vertex can lie in a region represented by a quadtree leaf node.
  2. Each region's quadtree leaf node is maximal.

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.