Intersect quadrilateral with axis-aligned rectangle?

Question

How can one efficiently test if an axis-aligned rectangle R intersects a nice quadrilateral Q?

• Nice means: Q is convex (not a chevron) and non-selfintersecting (not a bowtie, not degenerate).
• Just 2D.
• Just yes/no. I don't need the actual region of intersection.
• Edit: Q and R may be open or closed, whatever's convenient.

Obviously one could test, for each edge of Q, whether it intersects R. That reduces the problem to How to test if a line segment intersects an axis-aligned rectange in 2D?.

But just like R's axis-alignedness is exploited by Liang-Barsky to be faster than Cohen-Sutherland, Q's properties might be exploited to get something faster than running Liang-Barsky multiple times.

Thus, the polygon-rectangle intersection algorithms Sutherland–Hodgman, Vatti, and Greiner-Hormann, all of which let Q be nonconvex, are unlikely to be optimal.

Area of rectangle-rectangle intersection looks promising, even though it doesn't exploit R's axis-alignedness.

Answer 1

Be careful not to neglect the case where Q entirely covers R, or vice versa, as the edge test then would give a false negative.

One approach, conceptually:

• Regard R as the intersection of two axis-aligned infinite bands, a vertical band [x0,x1] and a horizontal band [y0,y1].
• Let xmin and xmax represent the extent of the intersection of Q with the horizontal band [y0,y1]; if [xmin,xmax] ∩ [x0,x1] is non-empty, then Q intersects R.

In terms of implementation:

1. Initialise xmin := +inf; xmax := -inf

2. For each edge pq of Q, p=(px,py) q=(qx,qy), with py ≥ qy:

   a. If qy > y1 or y0 > py, ignore this edge, and examine the next one.

   b. If py > y1, let (x,y1) be the intersection of pq with the horizontal line y = y1; otherwise let x be px.

   c. Update xmin = min(xmin,x); xmax = max(xmax,x).

   d. If y0 > qy, let (x,y0) be the intersection of pq with the horizontal line y = y0; otherwise let x be qx.

   e. Update xmin = min(xmin,x); xmax = max(xmax,x).

3. Q intersects R if xmin < x1 and xmax > x0.