边缘交叉算法？

Question

给定Polygon P,我有它的顶点顺序.我有一个带有4个顶点的矩形R我怎么能这样做:

如果P的任何边(相邻顶点之间的线)与R的边相交,则返回TRUE,否则返回FALSE.

谢谢

      *             *    


      *             *    

Answer 1

您想要的是一种快速确定线段是否与轴对齐矩形相交的方法。然后只需对照矩形检查边缘列表中的每条线段即可。您可以执行以下操作：

1) 将直线投影到 X 轴上，得到一个区间 L _x。
2) 将矩形投影到 X 轴上，得到一个区间 R _x。
3) 如果L _x和R _x不相交，则直线和矩形不相交。

[Y 轴重复]：

4) 将直线投影到 Y 轴上，得到一个区间 L _y。
5) 将矩形投影到 Y 轴上，得到一个区间 R _y。
6) 如果L _y和R _y不相交，则直线和矩形不相交。

7) ...
8) 它们相交。

请注意，如果我们到达步骤 7，形状就不能被轴对齐线分开。现在要确定的是该线是否完全在矩形之外。我们可以通过检查矩形上的所有角点是否在线的同一侧来确定这一点。如果是，则直线和矩形不相交。

1-3和4-6背后的想法来自分离轴定理；如果我们找不到分离轴，那么它们一定是相交的。所有这些情况都必须经过测试才能得出结论它们是交叉的。

这是匹配的代码：

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

希望这是有道理的。