# PMR QuadTree Demo

#### PMR Quadtree

This is a representation for a collection of line segments which is
built incrementally and thus the shape of the structure depends on the
order in which the line segments are inserted. Each block through which
a line segment passes is decomposed once and only once into four equal
area blocks if the insertion of the line segment causes the block to contain
more than *b* line segments (or pieces thereof). *b* is termed
the splitting threshold and is different from a bucket capacity as a block
may in fact have more than *b* line segments.
For more
details, see pages 374-377 of Samet,
*Foundations of Multidimensional and Metric Data Structures*
or, see
pages 264-275 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)