邊緣相交算法？

Question

給定多邊形P，我有它的verticies按順序。我有一個矩形R有4個頂點我怎麼能這樣做：

如果P（相鄰頂點之間的線）的任何邊緣與R的邊緣相交，則返回TRUE，否則返回FALSE。

感謝

 *    *  


     *    *  

Answer 1

想要的是快速確定線段是否與軸對齊的矩形相交的方法。然後，只需在矩形中檢查邊線列表中的每個線段即可。您可以執行以下操作：

1）將線投影到X軸上，產生間隔L _x。
2）將矩形投影到X軸上，產生間隔R _x。 3）如果L _x和R _x不相交，則直線和矩形不相交。

[重複針對Y軸]：

4）項目行到Y軸，導致間隔L _ÿ。
5）將矩形投影到Y軸上，產生間隔R _和。
6）如果L _和和R _和不相交，則直線和矩形不相交。

7）...
8）它們相交。

注意，如果我們到達第7步，形狀不能被軸對齊的線分開。現在要確定的是如果線完全在矩形之外。我們可以通過檢查矩形上的所有角點在線的同一側來確定這一點。如果是，則線條和矩形不相交。

1-3和4-6背後的想法來自separating axis theorem;如果我們找不到分離軸，它們必須相交。 全部這些情況必須經過測試，然後才能斷定它們相交。

這裏的匹配代碼：

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

希望是有道理的。

Answer 2

我覺得你的問題是相當於凸多邊形交集，在這種情況下this可能的幫助。也參見：How do I determine if two convex polygons intersect?

Answer 3

未測試，很明顯，但在粗糙的僞代碼：

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

基本上，如果兩個相鄰的P頂點是在R的邊緣中的一個的相對側上，檢查是否交點落在範圍。

Answer 4

僅供參考，geometrictools是這樣的事情一個很好的資源（尤其是數學部分）