Package
Components of the History Graph, a Directed Acyclical Graph (DAG) that
stores trapezoids in nodes. This DAG is navigated during point location
queries to find the trapezoid that contains the query point. The root
corresponds to the bounding box (modelled as a trapezoid) of the line
segments.
Queries
The query point q is given by its coordinates
If the current node is a leaf, then we are done
Otherwise, one of the descendants of the current trapezoid is a trapezoid
that contains q
Since there are at most 4 descendants, we can find it in O(1) time
Go down to this descendant and repeat the process
-
Class Summary
| Class |
Description |
| Leaf |
Leafs model trapezoids at the lowest level of the History Graph.
|
| Node |
Represents an abstract tree node with parents, left child, and right child.
|
| XNode |
An X node stores a segment end point.
|
| YNode |
A y-node stores a segment.
|