Hit Testing / Rectangle Overlap on Canvas

Problem Given a set of shapes on a canvas, each with a bounding box and a z-order (stacking order), answer hit-testing queries: for a point, return the topmost shape under it; for a selection rectangle, return the shapes it selects. Respect z-order.

Input / Output

• Input: shapes with geometry and z-order; a query that is either a point or a rectangle.
• Output: the topmost hit shape (point query) or the set of selected shapes (rectangle query).

Constraints

• Many shapes — performance matters; a full scan per query may be too slow at scale.

Example

• A point over overlapping shapes returns the one drawn last (highest z); a drag rectangle returns every shape inside/intersecting it.