Editing Quadtree (section)

===Polygonal map (PM) quadtree===
The polygonal map quadtree (or PM Quadtree) is a variation of quadtree which is used to store collections of polygons that may be degenerate (meaning that they have isolated vertices or edges).<ref>[[Hanan Samet]] and Robert Webber. "Storing a Collection of Polygons Using
Quadtrees". ''ACM Transactions on Graphics'' July 1985: 182-222. ''InfoLAB''. Web. 23 March 2012</ref>
<ref>{{Cite journal|last1=Nelson|first1=R. C.|last2=Samet|first2=H.|year=1986|title=A consistent hierarchical representation for vector data|journal=ACM SIGGRAPH Computer Graphics|volume=20 | issue = 4 |pages=197–206|doi=10.1145/15886.15908|doi-access=free}}</ref> A big difference between PM quadtrees and edge quadtrees is that the cell under consideration is not subdivided if the segments meet at a vertex in the cell.

There are three main classes of PM Quadtrees, which vary depending on what information they store within each black node. PM3 quadtrees can store any amount of non-intersecting edges and at most one point. PM2 quadtrees are the same as PM3 quadtrees except that all edges must share the same end point. Finally PM1 quadtrees are similar to PM2, but black nodes can contain a point and its edges or just a set of edges that share a point, but you cannot have a point and a set of edges that do not contain the point.