使用 C++ 检查线段是否包含点的最快方法是什么？

Question

我知道已经有很多关于如何检查线段是否包含点的问题，但我的问题具体是关于哪种方法对于性能关键型应用程序最有可能最有效。

环顾各种SO答案，似乎有三种通用方法：

使用距离：

float distance(Vector2 a, Vector2 b)
{
    return std::sqrtf(std::powf((a.x - b.x), 2.f) + std::powf((a.y - b.y), 2.f));
}

bool containsPoint(Vector2 lineP, Vector2 lineQ, Vector2 point)
{
    return distance(lineP, point) + distance(point,lineQ) == distance(lineP, lineQ);
}

这个我很快就注销了，因为三个平方根运算并不快。

计算线段的斜率，然后检查该点是否在边界内：

bool containsPoint(Vector2 lineP, Vector2 lineQ, Vector2 point)
{
    float slope = (lineP.y - lineQ.y) / (lineP.x - lineQ.x);
    float c = lineP.y - lineP.x * slope;
    
    float minX = std::min(lineP.x, lineQ.x);
    float maxX = (minX == lineP.x) ? lineQ.x : lineP.x;
    
    return point.x * slope + c == point.y && point.x >= minX && point.x <= maxX;  
}

这是我在编写此类函数时想到的第一个方法，但我不确定它在性能方面是否是最有效的。

使用叉积和点积：

bool containsPoint(Vector2 lineP, Vector2 lineQ, Vector2 point)
{
    float crossproduct = (point.y - lineP.y) * (lineQ.x - lineP.x) - (point.x - lineP.x) * (lineQ.y - lineP.y)

    if (fabs(crossproduct) > std::numeric_limits<float>::epsilon())
    {
        return false;
    }
    float dotproduct = (point.x - lineP.x) * (lineQ.x - lineP.x) + (point.y - lineP.y)*(lineQ.y - lineP.y)
    if (dotproduct < 0.f)
    {
        return false;
    }

    float squaredlengthba = (lineQ.x - lineP.x)*(lineQ.x - lineP.x) + (lineQ.y - lineP.y)*(lineQ.y - lineP.y)
    if (dotproduct > squaredlengthba)
    {
        return false;
    }

    return true;
}

这个看起来比线斜率解更长，但不同之处在于它不使用除法，而且我听说除法比乘法慢 10 倍。那么也许这是更好的解决方案？

或者还有其他更快的方法吗？

Answer 1

从数学和编程的角度来看，这个问题都很有趣。您可以将这种情况视为直角三角形问题：

然后您可以将除法转换为乘法并提高计算速度。

此外，如果程序必须测试大量的 2D 点，其中大多数点可能不会落在线上，则丢弃策略可能会有所帮助。在这种情况下，您可以检查各个维度距离 abs(px-ax) + abs(px-bx) > abs(ax-bx) || abs(py-ay) + abs(py-by) > abs(ay-by) -> 然后返回 false，否则运行上述方法。场景可能如下所示：

检查将丢弃 Q 点，但 P & R 仍需要测试。

代码可以如下所示：

bool containsPoint(Vector2 lineP, Vector2 lineQ, Vector2 point)
{
    if((abs(point.x - lineP.x) + abs(point.x - lineQ.x)) > abs(lineP.x - lineQ.x) || (abs(point.y - lineP.y) + abs(point.y - lineQ.y)) > abs(lineP.y - lineQ.y))
        return false;
    
    float x = abs(lineP.x - lineQ.x);
    float y = abs(lineP.y - lineQ.y);
    float x1 = abs(lineP.x - point.x);
    float y1 = abs(lineP.y - point.y);

    return if x*y1 == x1*y;  
}

但是如果你想进一步优化它，你可以避免变量声明和赋值：

bool containsPoint(Vector2 lineP, Vector2 lineQ, Vector2 point)
{
    if((abs(point.x - lineP.x) + abs(point.x - lineQ.x)) > abs(lineP.x - lineQ.x) || (abs(point.y - lineP.y) + abs(point.y - lineQ.y)) > abs(lineP.y - lineQ.y))
        return false;

    return if abs(lineP.x - lineQ.x)*abs(lineP.y - point.y) == abs(lineP.x - point.x)*abs(lineP.y - lineQ.y);  
}