边缘相交算法？

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是这样的事情一个很好的资源（尤其是数学部分）