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)