Planar Point Location

Randomized Incremental Method Applet

Instructions

The applet below demonstrates two aspects of randomized incremental algorithm the construction of the trapezoid map, and querying in a trapezoid map. The interface is very simple, it consists of two display areas, and four buttons. The upper display area displays a representation of the current trapezoid map, while the lower display area displays the search structure used in searching within the trapezoid map.

The applet basically runs in one of two modes, one for interactively building a planar subdivision and generating a trapezoid map (Build Mode), and the second for interactively performing queries on an existing trapezoid map (Query Mode). How the program responds is dependent on the current mode.

Build Mode

Build mode allows the user to insert a set of lines (into the upper display area) by clicking and dragging. Lines cannot intersect, so while drawing the lines appear green if they are valid, and turn red if they are invalid due to an intersection. Any invalid line will not be maintained. A user can enter build mode by clicking the "New Segments" or "Add Segments" buttons. Selecting "New Segments" will delete any existing segments in the display and allow the user to start adding new segments. "Add Segments" will allow the user to add segments to an existing arrangement of lines. At any point during the arrangement building process the user can test a trapezoidal map that will be build for this arrangement by selecting the "Step" button. The first time "Step" is selected a bounding rectangle (trapezoid) will be created for the arrangement of lines, subsequently clicking "Step" will randomly add the the segments from the arrangement into the current trapezoid map, until all segments are added. The user can return to adding segments, or start building the map again by clicking the "Add Segments" button.

Query Mode

Query mode allows the user to examine how the trapezoid map and its associated query structure work to perform planar point queries. The user enters Query Mode by selecting the "Query" button. Once in query mode a existing trapezoid map (which cannot be editted) will appear in the upper display and its associated search structure will appear in the lower display. Clicking anywhere in the upper display will set a new query point, which is displayed on screen.

Clicking the "Step" button will start the query with the current query point. The first step will be to go to the root of the search structure, and each subsequent click on "Step" will move the search closer to the trapezoid containing the search point. At each step in the search the search node is highlighted in the search structure and its associated feature in the trapezoid map is also highlighted. Once the trapezoid containing the point is found it too is highlighted. If at any point during the search the user selects a different query point (by clicking in the upper display area) then the query restarts, and searches for the new point.