Algoritmo de intersección de bordes?

Question

Dado Polygon P que tengo sus verticies en orden. y tengo un rectángulo R con 4 verticies ¿cómo podría hacer esto:

Si cualquier borde de P (línea entre vértices adyacentes) interseca un borde de R, entonces devuelve VERDADERO, de lo contrario devuelve FALSO.

Gracias

 *    *  


     *    *  

Answer 1

Lo que desea es una forma rápida de determinar si un segmento de línea interseca un rectángulo alineado con el eje. Luego, simplemente verifique cada segmento de línea en la lista de bordes contra el rectángulo. Puede hacer lo siguiente:

1) Proyecte la línea en el eje X, lo que da como resultado un intervalo L _x.
2) Proyecte el rectángulo en el eje X, lo que da como resultado un intervalo R _x.
3) Si L _x y R _x no se cruzan, la línea y el rectángulo no se cruzan.

[Repita para el eje Y]:

4) Proyecto de la línea sobre el eje Y, lo que resulta en un intervalo L _y.
5) Proyecte el rectángulo en el eje Y, lo que da como resultado un intervalo R _y.
6) Si L _y y R _{y no se cruzan, la línea y el rectángulo no se cruzan.}

7) ...
8) Se cruzan.

Tenga en cuenta que si llegamos al paso 7, las formas no pueden separarse mediante una línea alineada con el eje. Lo que hay que determinar ahora es si la línea está completamente fuera del rectángulo. Podemos determinar esto comprobando que todos los puntos de esquina en el rectángulo estén en el mismo lado de la línea. Si lo son, la línea y el rectángulo no se cruzan.

La idea detrás de 1-3 y 4-6 proviene del separating axis theorem; si no podemos encontrar un eje de separación, deben estar intersecando. Todos estos casos deben ser probados antes de que podamos concluir que se están cruzando.

Aquí está el código coincidente:

#include <iostream> 
#include <utility> 
#include <vector> 

typedef double number; // number type 

struct point 
{ 
    number x; 
    number y; 
}; 

point make_point(number pX, number pY) 
{ 
    point r = {pX, pY}; 
    return r; 
} 

typedef std::pair<number, number> interval; // start, end 
typedef std::pair<point, point> segment; // start, end 
typedef std::pair<point, point> rectangle; // top-left, bottom-right 

namespace classification 
{ 
    enum type 
    { 
     positive = 1, 
     same = 0, 
     negative = -1 
    }; 
} 

classification::type classify_point(const point& pPoint, 
            const segment& pSegment) 
{ 
    // implicit line equation 
    number x = (pSegment.first.y - pSegment.second.y) * pPoint.x + 
       (pSegment.second.x - pSegment.first.x) * pPoint.y + 
       (pSegment.first.x * pSegment.second.y - 
       pSegment.second.x * pSegment.first.y); 

    // careful with floating point types, should use approximation 
    if (x == 0) 
    { 
     return classification::same; 
    } 
    else 
    { 
     return (x > 0) ? classification::positive :classification::negative; 
    } 
} 

bool number_interval(number pX, const interval& pInterval) 
{ 
    if (pInterval.first < pInterval.second) 
    { 
     return pX > pInterval.first && pX < pInterval.second; 
    } 
    else 
    { 
     return pX > pInterval.second && pX < pInterval.first; 
    } 
} 

bool inteveral_interval(const interval& pFirst, const interval& pSecond) 
{ 
    return number_interval(pFirst.first, pSecond) || 
      number_interval(pFirst.second, pSecond) || 
      number_interval(pSecond.first, pFirst) || 
      number_interval(pSecond.second, pFirst); 
} 

bool segment_rectangle(const segment& pSegment, const rectangle& pRectangle) 
{ 
    // project onto x (discard y values) 
    interval segmentX = 
       std::make_pair(pSegment.first.x, pSegment.second.x); 
    interval rectangleX = 
       std::make_pair(pRectangle.first.x, pRectangle.second.x); 

    if (!inteveral_interval(segmentX, rectangleX)) 
     return false; 

    // project onto y (discard x values) 
    interval segmentY = 
       std::make_pair(pSegment.first.y, pSegment.second.y); 
    interval rectangleY = 
       std::make_pair(pRectangle.first.y, pRectangle.second.y); 

    if (!inteveral_interval(segmentY, rectangleY)) 
     return false; 

    // test rectangle location 
    point p0 = make_point(pRectangle.first.x, pRectangle.first.y); 
    point p1 = make_point(pRectangle.second.x, pRectangle.first.y); 
    point p2 = make_point(pRectangle.second.x, pRectangle.second.y); 
    point p3 = make_point(pRectangle.first.x, pRectangle.second.y); 

    classification::type c0 = classify_point(p0, pSegment); 
    classification::type c1 = classify_point(p1, pSegment); 
    classification::type c2 = classify_point(p2, pSegment); 
    classification::type c3 = classify_point(p3, pSegment); 

    // test they all classify the same 
    return !((c0 == c1) && (c1 == c2) && (c2 == c3)); 
} 

int main(void) 
{ 
    rectangle r = std::make_pair(make_point(1, 1), make_point(5, 5)); 
    segment s0 = std::make_pair(make_point(0, 3), make_point(2, -3)); 
    segment s1 = std::make_pair(make_point(0, 0), make_point(3, 0)); 
    segment s2 = std::make_pair(make_point(3, 0), make_point(3, 6)); 
    segment s3 = std::make_pair(make_point(2, 3), make_point(9, 8)); 

    std::cout << std::boolalpha; 
    std::cout << segment_rectangle(s0, r) << std::endl; 
    std::cout << segment_rectangle(s1, r) << std::endl; 
    std::cout << segment_rectangle(s2, r) << std::endl; 
    std::cout << segment_rectangle(s3, r) << std::endl; 
} 

esperanza que tiene sentido.

Answer 2

Creo que su problema es equivalente a la intersección polígono convexo, en cuyo caso this podría ayudar. Consulte también: How do I determine if two convex polygons intersect?

Answer 3

no comprobado, obviamente, pero en pseudocódigo áspera:

// test two points against an edge 
function intersects (side, lower, upper, pt1Perp, pt1Par, pt2Perp, pt2Par) 
{ 
    if ((pt1Perp < side and pt2Perp > side) or (pt1Perp > side and pt2Perp < side) 
    { 
     intersection = (side - pt1Perp) * (pt2Par - pt1Par)/(pt2Perp - pt1Perp); 
     return (intersection >= lower and intersection <= higher); 
    } 
    else 
    { 
     return false; 
    } 
} 

// left, right, bottom, top are the bounds of R 
for pt1, pt2 adjacent in P // don't forget to do last,first 
{ 
    if (intersects (left, bottom, top, pt1.x, pt1.y, pt2.x, pt2.y) 
     or intersects (right, bottom, top, pt1.x, pt1.y, pt2.x, pt2.y) 
     or intersects (top, left, right, pt1.y, pt1.x, pt2.y, pt2.x) 
     or intersects (bottom, left, right, pt1.y, pt1.x, pt2.y, pt2.x)) 
    { 
     return true; 
    } 
} 

Básicamente, si dos vértices P adyacentes están en lados opuestos de uno de los bordes de la R, compruebe si el punto de intersección cae en el rango .

Answer 4

Para su información, geometrictools es un gran recurso para este tipo de cosas (especialmente la sección de Matemáticas)