Overlap Search Query

The overlap query finds all objects overlapping a particular spatial feature. For example, these query features can be lines, rectangles, polygons, paths or sectors.

The overlap query algorithm is implemented by a simple tree traversal that visits the blocks of the representation in a top-down manner checking at each stage if the block b overlaps the query object. If there is no overlap, then exit. Otherwise, check if b is not at the lowest level of the hierarchy (i.e., b is a nonleaf node), in which case the algorithm is applied recursively to the immediate descendants of b . If b is at the lowest level of the hierarchy, then check if the objects contained in b satisfy the query restrictions, and, if so, report them.

In order to be able to visualize the behavior of the overlap query algorithm, at any instance of time we distinguish between the following entities by using different colors in a consistent way for all of the data structures:

1. Blocks that remain to be processed (i.e., they partially overlap the query range) denoted by light blue.
2. Objects that have not yet been processed but whose smallest enclosing block has been found to be in the query range denoted by green.
3. Objects that have not yet been processed in the sense that their smallest containing block has not been tested with respect to being in the query range or has been found to be outside the query range denoted by red.
4. Objects that have been processed and that have been found to be in the query range denoted by blue.
5. Objects that have been explicitly processed and that have been found to be outside the query range denoted by violet.
6. Blocks that have been processed denoted by gray (although some of the objects that they contain remain to be processed).
7. Blocks that have not been processed as they are outside the query range denoted by white.
8. The next item to be processed (could be a block or an object) denoted by yellow.
9. The query range denoted by orange.

When both the data objects have extent (e.g., lines, rectangles, etc.) and the query object define a query area (e.g., a rectangle), we need to be a bit more precise as to what is retrieved by the overlap query. The issue is whether the retrieved object o must be contained in its entirety in the query window w, whether o must enclose w, or whether o need only have a nonempty intersection with w (i.e., a partial overlap). For line segments, for example, we have the following three options:

1. The entire line (i.e., both of its endpoints) are in the query window.
2. The entire line passes through the query window (i.e., both of its endpoints lie outside the window).
3. At least some part of the line crosses the boundary of the window.

The applets enable the user to specify which of these variants of the window query is to be used. The interpretation for rectangle objects is similar where the options correspond to:

1. The entire rectangle is in the query window.
2. The entire rectangle contains the query window.
3. At least some part of the rectangle intersects (i.e., crosses) the boundary of the window.