In pseudocode
For each rectangle:
If the rectangle overlaps the selection area, highlight the rectangle
This is all that is required for a correctly working approach, but there are a number of other things you might need to take into account if this approach performs too slowly. I recommend implementing the simple approach, and once it works correctly you can make gradual improvements if it is not sufficiently smooth and responsive (this may not be necessary unless you have a large number of rectangles or restrictive hardware/software).
Determining whether a rectangle overlaps the selection rectangle
As you point out, using the point in polygon algorithm is impractical for this purpose - each rectangle is made up of an infinite number of points. So we need a completely different approach.
One way to check if a candidate rectangle overlaps the selection rectangle is to check for the following two cases:
- Check if any edge of the candidate rectangle intersects an edge of the selection rectangle.
- Check if either the candidate rectangle or the selection rectangle is completely contained within the other.
If either of these are true, there is some overlap. If neither of these are true, there is no overlap.
The complete containment check is simplified by the fact that the selection rectangle is never rotated - always remaining aligned to the x and y axes:
- To check if a candidate rectangle is completely contained within the selection rectangle, check that all 4 of its corners are between the x boundaries of the selection rectangle, and between the y boundaries of the selection rectangle.
- To check if a candidate rectangle completely contains the selection rectangle, check that it has one corner outside the bounds of the selection rectangle in each of the 4 orthogonal directions (left, right, up, and down). If so, it either contains the selection rectangle completely, or one or more of the edges intersect (but edge intersection was checked for in the previous stage, so we're only checking for complete containment if we already know there is no edge intersection).
Line segment intersection
To check whether any of the edges of a candidate rectangle intersects with any of the edges of the selection rectangle, you can either use a general line segment intersection algorithm and apply it to each pair of candidate edge and selection edge, or you can take advantage of the fact that the selection rectangle is never rotated,as follows:
Parallel case
If the candidate rectangle has edges parallel to the x and y axes (that is, it is rotated by 0, 90, 180 or 270 degrees), check each of its edges:
If the edge is vertical, check if its x position is between the x coordinates of the selection rectangle, and if one of the following holds then there is an intersection:
- The y coordinate of one of its end points is between the y coordinates of the selection rectangle AND the y coordinate of the other end point is not.
- The end points are both outside the y coordinates of the selection rectangle but in opposite directions.
Similarly, if the edge is horizontal, check if its y position is between the y coordinates of the selection rectangle, and if one of the following holds then there is an intersection:
- The x coordinate of one of its end points is between the x coordinates of the selection rectangle AND the x coordinate of the other end point is not.
- The end points are both outside the x coordinates of the selection rectangle but in opposite directions.
Non-parallel case
Check each of the edges of the candidate rectangle as follows:
First find the points of intersection of the infinite line on which the candidate edge lies, with the infinite lines forming the boundaries of the selection rectangle.
If either of the intersections with the y boundaries of the selection rectangle has an x coordinate between the x boundaries of the selection rectangle, then there is an intersection of one of the horizontal line segment edges of the selection rectangle with the candidate infinite line (so potentially with the candidate line segment too).
Similarly, if either of the intersections with the x boundaries of the selection rectangle has a y coordinate between the y boundaries of the selection rectangle, then there is an intersection of one of the vertical line segment edges of the selection rectangle with the candidate infinite line (so potentially with the candidate line segment too).
To then check if there is an intersection with the candidate line segment, check if one of the following is true:
- An intersection with the y boundary of the selection rectangle is between the x boundaries of the selection rectangle AND between the y coordinates of the candidate line segment.
- An intersection with the x boundary of the selection rectangle is between the y boundaries of the selection rectangle AND between the x coordinates of the candidate line segment.
Examples of refinements if speed is unsatisfactory
- Acceleration data structures such as a grid or space partitioning hierarchy so that not every rectangle needs to be checked.
- Only checking the changed parts of the selection (usually one corner of the selection stays fixed while the opposite corner moves).
- Tracking which rectangles are already selected to reduce the checking required each time the selection changes:
- No need to check unselected rectangles if the selection has purely shrunk.
- No need to check already selected rectangles if the selection has purely grown.
- It will only be necessary to check both selected and unselected rectangles if the selection has grown in one direction and shrunk in the other.
