Estoy tratando de encontrar si un rectángulo interseca un polígono cóncavo. ¿Este algoritmo logra eso?

Question

Estoy tratando de encontrar si un rectángulo interseca un polígono cóncavo. He encontrado este algoritmo:

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; 
} 

Si realizo esto 4 veces (de arriba a derecha, de arriba a abajo a la izquierda, de arriba a abajo a la derecha, abajo a la derecha) * (todos los bordes de mi polígono) haría esto de manera efectiva y precisa dime si el rectángulo tiene parte o todo el polígono cóncavo adentro? Si no, ¿qué estaría faltando?

Gracias

Answer 1

El código intenta encontrar el punto de intersección de dos segmentos: AB y CD.

Hay muchas maneras diferentes de explicar cómo lo está haciendo, dependiendo de cómo interprete estas operaciones.

Digamos que el punto A tiene coordenadas (xa, ya), B - (xb, yb) y así sucesivamente. Digamos

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

El siguiente sistema de dos ecuaciones lineales

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

si resuelve para t y u, le dará la posición proporcional del punto de intersección de la línea AB (valor t) y en línea CD (valor u). Estos valores estarán en el rango de [0, 1] si el punto pertenece al segmento correspondiente y está fuera de ese rango si el punto se encuentra fuera del segmento (en la línea que contiene el segmento).

Para resolver este sistema de ecuaciones lineales podemos usar el conocido Cramer's rule. Para que vamos a necesitar el determinante de

| dxAB dxCD | 
|   | 
| dyAB dyCD | 

que es exactamente determinant(b - a, c - d) desde el código. (En realidad, lo que tengo aquí es determinant(b - a, d - c), pero no es realmente importante para los propósitos de esta explicación. El código que usted publicó por alguna razón intercambia C y D, vea la nota P.S. a continuación).

Y también necesitaremos determinante de

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

que es exactamente determinant(c-a,c-d) de su código y determinante de

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

que es exactamente determinant(b-a,c-a).

Dividir estos determinantes de acuerdo con la regla de Cramer nos dará los valores de t y u, que es exactamente lo que se hace en el código que ha publicado.

El código entonces procede a probar los valores de t y u para comprobar si los segmentos realmente se cruzan, es decir, si tanto t y u pertenecen a [0, 1] gama. Y si lo hacen, calcula el punto de intersección real evaluando a*t+b*(1-t) (de manera equivalente, podría evaluar c*u+d*(1-u)). (Nuevamente, vea la nota P.S. a continuación).

P.S. En el código original, los puntos D y C se "intercambian" en un sentido que el código hace c - d, donde hago d - c en mi explicación. Pero esto no hace ninguna diferencia para la idea general del algoritmo, siempre que uno tenga cuidado con los signos.

Este intercambio de puntos C y D es también la razón por la que a*(1-t)+t*b se usa la expresión al evaluar el punto de intersección. Normalmente, como en mi explicación, uno esperaría ver algo como a*t+b*(1-t) allí. (Tengo mis dudas sobre esto sin embargo. Esperaría ver allí a*t+b*(1-t) incluso en su versión. Podría ser un error.)

P.P.S. El autor si el código olvidó verificar det == 0 (o muy cerca de 0), lo que sucederá en el caso de que los segmentos sean paralelos.

Answer 2

creo que el siguiente debería funcionar:

(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 

Editar: Añadido comprobar si el polígono está dentro del rectángulo.

Answer 3

Por lo que puedo decir después de un vistazo rápido, trata de determinar si dos segmentos de línea se cruzan, y si lo hacen, cuáles son las coordenadas del punto de intersección.

No, no es lo suficientemente bueno como para determinar si su rectángulo y su polígono se cruzan, porque aún se perderá el caso donde el polígono está completamente dentro del rectángulo, o al revés.