# Bucket PM QuadTree Demo

#### Bucket PM Quadtree

Recursively decompose the underlying space into four equal area blocks
as long as the number of line segments in the block is more than the
bucket capacity.
For more details, see pages 374-377 of Samet,
*Foundations of Multidimensional and Metric 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)