I am trying to find if a rectangle intersects a concave polygon. Does this algorithm do this?

Question

I am 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 ab, the other is cd Vector2D edgeIntersection(Vector2D a, Vector2D b, Vector2D c, Vector2D d){ double det=determinant(ba,cd); double t=determinant(ca,cd)/det; double u=determinant(ba,ca)/det; if ((t<0)||(u<0)||(t>1)||(u>1))return NO_INTERSECTION; return a*(1-t)+t*b; } 

If I do this 4 times (top to bottom, top to bottom, top to bottom, right to bottom right) * (all edges of my polygon), it will effectively and accurately tell me if the rectangle has a part or the entire concave polygon inside? If not for what would be gone?

thanks

Answer 1

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

There are many ways to explain how this is done, depending on how you interpret these operations.

Let's say point A has coordinates (xa, ya), B has (xb, yb), etc. Let them talk

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

The following system of two linear equations

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

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

To solve this system of linear equations, we can use the well-known Cramer rule. For this we need a qualifier

 | dxAB dxCD | | | | dyAB dyCD | 

which exactly matches the determinant(b - a, c - d) from your code. (Actually, I have determinant(b - a, d - c) , but this is not very important for the purpose of this explanation. For the code that you swap for C and D for some reason, see the PS note below).

And we will need a determinant

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

which is exactly determinant(ca,cd) from your code and qualifier

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

which is exactly equal to determinant(ba,ca) .

Separation of these determinants in accordance with the Cramer rule will give us the values ​​of t and u , which is what is done in the code you published.

The code then checks the values ​​of t and u to check if the segments really intersect, i.e. whether t and u correspond to the range [0, 1] . And if they do, he calculates the actual intersection point by estimating a*t+b*(1-t) (equivalently, he could estimate c*u+d*(1-u) ). (Again, see Note PS below).

PS In the source code, points D and C are "replaced" in the sense that the code has c - d , where I have d - c in my explanation. But this does not matter for the general idea of ​​the algorithm, if only be careful with the attributes.

This exchange of points C and D is also the reason for the expression a*(1-t)+t*b , used in evaluating the intersection point. Usually, as in my explanation, you expected to see something like a*t+b*(1-t) . (I doubt it, but I expected to see a*t+b*(1-t) even in your version. There may be a mistake.)

PPS The author, if the code forgot to check det == 0 (or very close to 0), which will happen in the case of parallel segments.

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 if the polygon is inside the rectangle.

Answer 3

As far as I can tell from a quick glance, he is trying to determine if 2 line segments intersect, and if so, what are the coordinates of the intersection point.

No, it’s not enough to determine if your rectangle and polygon intersect, because you will still miss the case when either the polygon is completely inside the rectangle, or vice versa.