1

我正在尝试找到一种算法，该算法针对查找（无限）线和线段之间是否存在交叉点进行了优化。

在 SO 和其他网站上，我看到了许多线段 - 线段相交和线 - 线相交算法，但找到了一个“更简单？” 一条无限线（从一个方向的一点）和一条线段的版本非常难。

我目前有类似（线段 - 线段交点）：

bool lineSegmentsIntersect(float pX, float pY, float p2X, float p2Y, float qX, float qY, float q2X, float q2Y)
{
    // p and p2 define the first line segment
    Point2D p(pX, pY);
    Point2D p2(p2X, p2Y);

    // q and q2 define the second line segment
    Point2D q(qX, qY);
    Point2D q2(q2X, q2Y);

    Point2D r = p2 - p;
    Point2D s = q2 - q;

    float uNumerator = (q-p)*r;
    float denominator = r*s;

    if (uNumerator == 0 && denominator == 0) {
        // co-linear, so do they overlap?
        return ((q.x - p.x < 0) != (q.x - p2.x < 0) != (q2.x - p.x < 0) != (q2.x - p2.x < 0)) ||
            ((q.y - p.y < 0) != (q.y - p2.y < 0) != (q2.y - p.y < 0) != (q2.y - p2.y < 0));
    }

    if (denominator == 0) {
        // lines are parallel
        return false;
    }

    float u = uNumerator / denominator;
    float t = ((q-p)*s) / denominator;

    return (t >= 0) && (t <= 1) && (u >= 0) && (u <= 1);

}

其中 * 运算符定义为：

float Point2D::operator*(const Point2D &rhs)
{
    return x*rhs.y - y*rhs.x;
}

虽然我正在寻找更简单/更快的东西。我正在尝试检查一个点是否在一个封闭的形状内（该形状由一些点和它们之间的（线性插值）直线定义。）

从这一点开始，我向预定义的方向射出一条射线。

最好是 [1, 0] 或 [0, 1] （这可以用作给定的常数），如果这使我认为可能的数学更容易。

然后我检查光线是否与每个线段相交，如果是奇数，则它在形状内。

我在想的一些事情：

如果我们决定总是向上射出一条射线，那么如果线段的两个点都低于我们已经知道它不相交的点。

4

1 回答 1

1

参见 Hormann 和 Agathos，“任意多边形的多边形点问题”，计算几何 20 (2001) 131–144。用于有效实现缠绕算法。

于 2013-09-20T07:10:52.827 回答