# PM3 QuadTree Demo

#### PM3 Quadtree

This is a representation for a collection of line segments where
the decomposition condition only depends on the vertices. The
underlying space is decomposed into four equal area blocks as long as
a block contains more than one vertex.
For more
details, see pages 365-369 and 807-808 of Samet,
*Foundations of Multidimensional and Metric Data Structures*
or, see pages
261-264 of Samet,
*Design and Analysis of Spatial Data Structures*.

#### Instructions

**Insert** mode:

- click and drag to specify the line to insert
- press CTRL when defining either end point of any line to snap to nearest
already existing point

**Delete** mode:

- click to delete the nearest line

**Search** mode:

- Click and drag to define a rectangle. Lines inside this rectangle will be returned based on the
*Search mode*:
*Inside window* - the entire line (i.e., both of its endpoints) are
in the query window in order to return the line
*Crosses window* - the entire line passes through the query window
(i.e., both of its endpoints lie outside the window)
*Intersects window once* - the line crosses just one of the
boundaries of the window (i.e., only one of the endpoints of the line lies
inside the window)