0

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.

Community
  • 1
  • 1
Camille Goudeseune
  • 2,934
  • 2
  • 35
  • 56

2 Answers2

2

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.

halfflat
  • 1,584
  • 8
  • 11
  • This looks pretty good but you need to be careful about whether your inequalities are strict or not. This depends on whether the polygons are considered to be open or closed, and if closed, then also depends on whether a non-empty intersection that has 0 area is counted as an actual intersection or not. – user2566092 Mar 05 '15 at 23:54
  • 1
    The implicit assumption in my answer here was that both polygons were closed (hence the use of closed intervals [x0,x1] and [y0,y1]). Without making a formal proof, I'm pretty sure that the above gives the correct answer in this case, and also deals correctly with the case where edges of Q may be co-incident with edges of P. – halfflat Mar 06 '15 at 00:09
  • My naive solution runs 1 to 4 Liang-Barsky's. This does 2 to 8 "intersect pq with horizontal line" operations, which is indeed fewer comparisons and multiplications as I eyeball it. – Camille Goudeseune Mar 06 '15 at 22:41
0

1) Construct Q's axis-aligned bounding box. Test that it does not intersect R.

2) For every edge E of Q, test that all four vertices of R lie on the outer side of E's supporting line. (Use the implicit equation of the edge, A.x + B.y + c <> 0.)

If and only if either of these tests succeeds, there is no intersection.

Camille Goudeseune
  • 2,934
  • 2
  • 35
  • 56
  • This seems too simple to work. But after some scribbling I can find neither a counterexample nor a convincing proof. Could you please add a hint why this works??? – Camille Goudeseune Mar 06 '15 at 18:05
  • 1
    I don't think this works: consider as a counterexample the rectangle R given by corners (0,0), (1,0), (1,-1) and (0,-1). Let Q be the degenerate quadrilateral with vertices (-3,-2) and (2,3). Q does not intersect R. But: 1) the axis aligned box around Q does intersect R, so the first test fails; 2) the vertices of Q straddle each of the (infinite) lines corresponding to the edges of R, so the second test also fails. – halfflat Mar 06 '15 at 18:56
  • The counterexample generalizes to non-selfintersecting Q, by replacing each vertex of degenerate-Q with a nearby pair of vertices. Then Q's two long edges still fail to have all of R's vertices on one side. – Camille Goudeseune Mar 06 '15 at 19:49
  • 1
    The edited proposed solution is much clearer, but the problem remains: e.g. R given by (0,), (0,-2), (5,-2),(5,0) and Q given by (-3,-1), (-4,0), (0,4), (1,3). Test 1 fails, and test 2 fails (line through (0,4) and (1,3) passes between vertices of R), but Q does not intersect R. – halfflat Mar 06 '15 at 20:58
  • Indeed a counterexample. Thank you, @halfflat. – Camille Goudeseune Mar 06 '15 at 22:09
  • This is a good example, not a counterexample: R is wholly on the outside side of (1,3)-(-3-1), so no intersection. –  Mar 07 '15 at 10:57
  • @CamilleGoudeseune: the trick is to find a separating line or establish that there is none. This is efficiently proven with a finite number of cases. The procedure generalizes to any number of sides of the convex polygon. –  Mar 07 '15 at 11:01
  • @Yves Daoust: is the statement then that Q does not intersect R if and only if Q's axis-aligned bounding box does not intersect R or there exists at least one edge of Q such that all of the vertices of R are on the outside of that edge? – halfflat Mar 07 '15 at 17:56