Algoritmo per l'intersezione dei bordi?

Question

Dato Poligono P che ho i suoi vertici in ordine. e ho un rettangolo R con 4 vertici come potrei fare questo:

Se qualsiasi bordo di P (linea tra vertici adiacenti) interseca un bordo di R, quindi restituisce VERO, altrimenti restituisce FALSE.

Grazie

 *    *  


     *    *  

Answer 1

Quello che vuoi è un modo rapido per determinare se un segmento di linea interseca un rettangolo allineato all'asse. Quindi basta controllare ciascun segmento di linea nella lista dei bordi rispetto al rettangolo. È possibile effettuare quanto segue:

1) Proiettare la linea sull'asse X, determinando un intervallo L _x.
2) Proietta il rettangolo sull'asse X, risultante in un intervallo R _x.
3) Se L _x e R _x non si intersecano, la linea e il rettangolo non si intersecano.

[Ripetere per l'asse Y]:

4) Progetto linea sulla asse Y, risultante in un intervallo L _y.
5) Proietta il rettangolo sull'asse Y, risultante in un intervallo R _y.
6) Se L _y e R _y non si intersecano, la linea e il rettangolo non si intersecano.

7) ...
8) Si intersecano.

Nota: se si raggiunge il punto 7, le forme non possono essere separate da una linea allineata all'asse. La cosa da determinare ora è se la linea è completamente fuori dal rettangolo. Possiamo determinarlo controllando che tutti i punti d'angolo sul rettangolo si trovino sullo stesso lato della linea. Se lo sono, la linea e il rettangolo non si intersecano.

L'idea di base 1-3 e 4-6 deriva da separating axis theorem; se non riusciamo a trovare un asse di separazione, devono intersecare. Tutti i casi questi casi devono essere testati prima di poter concludere che si stanno intersecando.

Ecco il codice corrispondente:

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

speranza che abbia un senso.

Answer 2

Credo che il problema è equivalente a convesso intersezione poligono, nel qual caso this potrebbe aiutare. Vedi anche: How do I determine if two convex polygons intersect?

Answer 3

testato, ovviamente, ma in pseudocodice grezzo:

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

In sostanza, se due vertici P adiacenti sono su lati opposti di uno dei bordi della R, controllare se il punto di intersezione cade nell'intervallo .

Answer 4

Cordiali saluti, geometrictools è una grande risorsa per queste cose (in particolare la sezione Math)