PM1, PM2, PM3 and PMR QuadTree Demo

PM1 Quadtree

Recursively decompose the underlying space into four equal area blocks as long as a block contains more than one line segment unless the line segments are all incident at the same vertex which is also in the same block. Each block is maximal and contains at most one vertex. For more details, see pages 240-257 of Samet, Foundations of Multidimensional and Metric Data Structures or, see pages 240-257 of Samet, Design and Analysis of Spatial Data Structures.

PM2 Quadtree

Recursively decompose the underlying space into four equal area blocks as long as a block contains more than one line segment unless the line segments are all incident at the same vertex regardless of its location (i.e., it need not be in the same block). For more details, see pages 257-261 of Samet, Design and Analysis of Spatial Data Structures.

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 261-264 of Samet, Design and Analysis of Spatial Data Structures.

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 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)