103
edits
Changes
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.