An R-tree indexes rectangles and other objects through their minimum bounding boxes. Its pruning decision depends on one operation: determining whether a stored box overlaps the query box.
Design an RTreeBoundingBoxQuery class:
RTreeBoundingBoxQuery() creates a stateless query helper.int[] overlapping(int[][] rects, int[] query) returns the indices of all stored rectangles that overlap query.
Every rectangle is [minX, minY, maxX, maxY]. Two boxes overlap when their closed intervals intersect on both axes:
Touching at an edge or corner counts as overlap. Return indices in ascending input order, do not mutate the inputs, and treat each call independently.
Example 1:
Input:
Output:
Explanation: Rectangles 0 and 2 intersect the query on both axes. Rectangle 1 is completely above and to the right.
Example 2:
Input:
Output:
Explanation: Rectangle 0 contains the query. Rectangle 1 touches its upper-right corner at (2,2), so it also overlaps.
Constraints
0 <= rects.length <= 10^5rects[i].length == 4 and query.length == 4rects[i][0] <= rects[i][2] and rects[i][1] <= rects[i][3]query[0] <= query[2] and query[1] <= query[3]- All coordinates are integers in
[-10^9, 10^9]. - At most
100 calls are made to overlapping.
Query R-Tree Bounding Boxesmedium