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:
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:
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: