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)