I'm trying to find if a rectangle intersects a concave polygon. Does this algorithm accomplish that?

Question

I'm trying to find if a rectangle intersects a concave polygon. I found this algorithm:

double determinant(Vector2D vec1, Vector2D vec2){
    return vec1.x*vec2.y-vec1.y*vec2.x;
}

//one edge is a-b, the other is c-d
Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){
    double det=determinant(b-a,c-d);
    double t=determinant(c-a,c-d)/det;
    double u=determinant(b-a,c-a)/det;
    if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION;
    return a*(1-t)+t*b;
}

If I perform this 4 times (Top to Right, Top to bottom left, top to bottom right, bottom to right) * (all edges of my polygon) would this effectively and accurately tell me if the rectangle has part of or all the concave polygon inside? If not what would be missing?

Thanks

Answer 1

The code attempts to find the intersection point of two segments - AB and CD.

There are many different ways to explain how it is doing it, depending on how you interpret these operations.

Let's say point A has coordinates (xa, ya), B - (xb, yb) and so on. Let's say

dxAB = xb - xa
dyAB = yb - ya
dxCD = xd - xc
dyCD = yd - yc

The the following system of two linear equations

| dxAB dxCD |   | t |   | xc-xa |
|           | * |   | = |       |
| dyAB dyCD |   | u |   | yc-ya |

if solved for t and u, will give you the proportional position of the intersection point on line AB (value t) and on line CD (value u). These values will lie in range of [0, 1] if the point belongs to the corresponding segment and outside of that range if the point lies outside the segment (on the line containing the segment).

In order to solve this system of linear equations we can use the well-known Cramer's rule. For that we will need the determinant of

| dxAB dxCD |
|           |
| dyAB dyCD |

which is exactly determinant(b - a, c - d) from your code. (Actually, what I have here is determinant(b - a, d - c), but it is not really important for the purposes of this explanation. The code you posted for some reason swaps C and D, see P.S. note below).

And we will also need determinant of

| xc-xa dxCD |
|            |
| yc-ya dyCD |

which is exactly determinant(c-a,c-d) from your code, and determinant of

| dxAB xc-xa |
|            |
| dyAB yc-ya |

which is exactly determinant(b-a,c-a).

Dividing these determinants in accordance with the Cramer's rule will give us the values of t and u, which is exactly what is done in the code you posted.

The code then proceeds to test the values of t and u to check if the segments actually intersect, i.e. whether both t and u belong to [0, 1] range. And if they do, it calculates the actual intersection point by evaluating a*t+b*(1-t) (equivalently, it could evaluate c*u+d*(1-u)). (Again, see the P.S. note below).

P.S. In the original code the points D and C are "swapped" in a sense that the code does c - d, where I do d - c in my explanation. But this makes no difference for the general idea of the algorithm, as long as one's careful with signs.

This swap of C and D point is also the reason for a*(1-t)+t*b expression is used when evaluating the intersection point. Normally, as in my explanation, one'd expect to see something like a*t+b*(1-t) there. (I have my doubts about this though. I would expect to see a*t+b*(1-t) there even in your version. Could be a bug.)

P.P.S. The author if the code forgot to check for det == 0 (or very close to 0), which will happen in case when the segments are parallel.

Answer 2

I think the following should work:

(1) for each e1 in rectangle_edges, e2 in polygon_edges
    (1.1) if edgeIntersection(e1,e2) != NO_INTERSECTION
        (1.1.1) return true
(2) if (max_polygon_x < max_rectangle_x) and (min_polygon_x > min_rectangle_x) and (max_polygon_y < max_rectangle_y) and (min_polygon_y > min_rectangle_y)
    (2.1) return true
(2) return false

Edit: Added check for whether the polygon is inside the rectangle.