Algorithmus für Kantenüberschneidung?

Question

Gegebene Polygon P, die ich habe ihre Vertices in der Reihenfolge. und ich habe ein Rechteck R mit 4 Vertices, wie könnte ich das tun:

Wenn eine Kante von P (Linie zwischen benachbarten Eckpunkten) eine Kante von R schneidet, dann gebe TRUE zurück, andernfalls gebe FALSE zurück.

Dank

 *    *  


     *    *  

Answer 1

Sie können schnell feststellen, ob ein Liniensegment ein achsenausgerichtetes Rechteck schneidet. Dann überprüfen Sie einfach jedes Liniensegment in der Kantenliste gegen das Rechteck. Sie können Folgendes tun:

1) Projizieren Sie die Linie auf die X-Achse, was zu einem Intervall L _x führt.
2) Projizieren Sie das Rechteck auf die X-Achse, was zu einem Intervall R _x führt.
3) Wenn L _x und R _x sich nicht schneiden, schneiden sich die Linie und das Rechteck nicht.

[Repeat für die Y-Achse]:

4) Projekt der Linie auf die Y-Achse, die sich in einem Abstand L _y.
5) Projizieren Sie das Rechteck auf die Y-Achse, was zu einem Intervall R _y führt.
6) Wenn L _y und R _y sich nicht schneiden, schneiden sich die Linie und das Rechteck nicht.

7) ...
8) Sie schneiden sich.

Beachten Sie, wenn wir Schritt 7 erreichen, können die Formen nicht durch eine achsgerichtete Linie getrennt werden. Jetzt müssen Sie feststellen, ob die Linie vollständig außerhalb des Rechtecks ​​liegt. Wir können dies feststellen, indem wir überprüfen, ob alle Eckpunkte auf dem Rechteck auf derselben Seite der Linie liegen. Wenn dies der Fall ist, schneiden sich die Linie und das Rechteck nicht.

Die Idee hinter 1-3 und 4-6 kommt von der separating axis theorem; Wenn wir keine Trennachse finden können, müssen sie sich schneiden. Alle diese Fälle müssen getestet werden, bevor wir schließen können, dass sie sich schneiden.

Hier ist der passende Code:

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

Hoffnung, die Sinn macht.

Answer 2

Ich denke, Ihr Problem zu konvexen Polygon Kreuzung entspricht, wobei in diesem Fall this helfen könnte. Siehe auch: How do I determine if two convex polygons intersect?

Answer 3

Ungeprüfte, natürlich, aber in grobem Pseudo-Code:

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

Grundsätzlich, wenn zwei benachbarte P Scheitelpunkte auf entgegengesetzten Seiten eines der R der Kanten sind, zu überprüfen, ob der Schnittpunkt fällt im Bereich .

Answer 4

Gerade FYI, ist geometrictools eine große Ressource für solche Dinge (vor allem der Math Abschnitt)