More flexible query options (equals, contains, within, intersects, overlaps, touches)

[lukas-shawford]

The current query method has hardcoded behavior with respect to what counts as a "match" when querying by either a Point or a Rect, particularly with respect to borders.

From the current README:

When querying by point, note that points that lie on the border (rather than the interior) of a bounding rectangle are considered to intersect the rectangle.

And:

When querying by rectangle, note that the rectangles must have a non-zero intersection area. Rectangles that intersect at the border but whose interiors do not overlap will not match the query.

Whether this is the desired behavior depends on the use case. Ideally it should be made configurable (with a sensible default).

The current thought is to add an optional op parameter, which specifies the operation type using an enum. For example:

entries = t.query(Rect(2, 1, 5, 5), op=Query.CONTAINS)

The above would return entries whose bounding rectangles are contained entirely within the query rectangle Rect(2, 1, 5, 5).

Care would need to be taken to ensure that the operation is only applied to the leaf entries, and not the bounding rectangles of intermediate nodes. The query rectangle may fully contain a leaf entry, but only partially intersect with the bounding rectangle of its container node.

The full list of supported operations, and what they mean for various combinations of point vs rectangle queries, and point vs rectangle entries (where the rects may be degenerate, see #6) will need to be researched further. But as a starting point, here are some examples of what might be supported:

• Equals: An entry matches only if its bounding location (point or rectangle) exactly matches the query location (point or rectangle).
• Contains: An entry matches only if its bounding location (point or rectangle) lies entirely within the interior of the query location (in this case, only rectangle makes sense - a point does not have an interior, and will never return a result).
• Within: Inverse of "contains". An entry matches if the query location (point or rectangles) lies entirely within the interior of the entry. Only entries with a non-degenerate bounding rectangle will be returned.
• Overlaps: An entry will match if it has non-zero intersection area. Unlike intersects, adjacent rectangles that touch along the border, but have no intersection area will not match using an overlap query.
  • TBD: What does "overlap" mean for degenerate rectangles and points?
• Touches: An entry will only match if the intersection is along the outside border, but will not match if the rectangles have overlapping interiors.
  • TBD: What does "touches" mean for degenerate rectangles and points?
• Intersects: An entry will match if it either overlaps OR touches. This is the most inclusive operation, and will be used as the default if the operation type is not explicitly passed in.

Some diagrams to illustrate the difference between "overlaps" and "touches" for rectangular queries (Q) and rectangular entries (E):

Again, more thought will need to be given to what these operations mean when either the query or the entry is a point, or a degenerate rectangle (line segment - note that a rectangle that collapses to a point will be treated as a point for purposes of executing the query).

[lukas-shawford]

Created a wiki page to track the design of this feature:

https://github.com/sergkr/rtreelib/wiki/Query-Design

There are a lot of possible combinations to consider, and I will see if maybe PostGIS, ArcGIS, or another spatial database system provides a good model to follow.