c++ - 边缘相交算法？

Question

给定多边形 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 背后的想法来自 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;
}

希望这是有道理的。