What is this?
It's my personal project:
2D Orthogonal Range Tree Visualization.
- The [Input Points and Queries] Canvas: is the canvas
which holds the points that we are working with.
- The [2D Range Tree] Canvas: displays the orthogonal
range tree generataed from the points in the [Input Points and
Queries] Canvas.
How to use it?
1. point inialization:
- You can enter your own points by clicking on the [Input Points and
Queries] Canvas.
- Or you can initialize them randomly by clicking the [Randomized 8
points Points] button. This button can be pressed twice at most (16
points)
2. range inialization:
- You can enter your own range using the four input boxes underneath
the [Input Points and Queries] Canvas.
- Or you can initialize them randomly by clicking the [Randomized
Query] button.
3. range tree creation:
- Once you create your points, you can click the [Build Range Tree]
button
4. search:
- Once you built your range tree, you can click the [Find Points in
Range] button
5. testing:
- Open the console, and use the multitest(#iterations, #points) to
test. It would generates random points and compare the result given
by the range tree with a brute force result.
Input Points and Queries
2D Range Tree
Terminologies
pink nodes:
visited
S:
Split nodes
WR & orange nodes:
Within Range, aka, points that satisfied the constraints
RS & lightgreen nodes:
Report entire Subtree as found points
lightblue nodes:
Where we need to do a search in the assoc structure only, but not
its children