检查线段是否与某一点的距离在一定范围内

Question

检查线段是否与某一点的距离在一定范围内

10

我有两个点A和B，它们在设备屏幕上定义了一个线段，还有另一个点C。请使用高效且简短易懂的算法（最好使用标准数学库），如何检查线段AB是否与点C的距离小于R？

我知道有一种简单的方法可以找到点到直线的最短距离，但是它假设直线是无限长的。我手头的是有两个端点的线段。

我曾考虑在Math SE中发布此问题，但决定不这样做，因为我不想得到所有那些像https://math.stackexchange.com/questions/2837/how-to-tell-if-a-line-segment-intersects-with-a-circle中那样的长数学公式作为答案。我需要的是一个高效而易读的计算机算法，而不是一个正式的数学定理。

附：我有以下Objective-C方法骨架需要实现：

typedef struct {
  CGPoint a;
  CGPoint b;
} CGLineSegment;

+ (BOOL)isLineSegment:(CGLineSegment)line withinRadius:(CGFloat)radius fromPoint:(CGPoint)point {

}

解决方法：

感谢veredesmarald的回答（我已经接受），我已经实现了该方法，以下作为其他人的参考：

+ (BOOL)isLineSegment:(CGLineSegment)line withinRadius:(CGFloat)radius fromPoint:(CGPoint)point {
    CGPoint v = CGPointMake(line.b.x - line.a.x, line.b.y - line.a.y);
    CGPoint w = CGPointMake(point.x - line.a.x, point.y - line.a.y);
    CGFloat c1 = dotProduct(w, v);
    CGFloat c2 = dotProduct(v, v);
    CGFloat d;
    if (c1 <= 0) {
        d = distance(point, line.a);
    }
    else if (c2 <= c1) {
        d = distance(point, line.b);
    }
    else {
        CGFloat b = c1 / c2;
        CGPoint Pb = CGPointMake(line.a.x + b * v.x, line.a.y + b * v.y);
        d = distance(point, Pb);
    }
    return d <= radius;
}

CGFloat distance(const CGPoint p1, const CGPoint p2) {
    return sqrt(pow(p2.x - p1.x, 2) + pow(p2.y - p1.y, 2));
}

CGFloat dotProduct(const CGPoint p1, const CGPoint p2) {
    return p1.x * p2.x + p1.y * p2.y;
}

- Lukman

在将其转换为代码之前，您必须具备（并最好理解！）所涉及的数学知识。 - Bart Kiers

@Bart Kiers 是的，那是真的，但我正在寻找数学，而不是公式，这正如我在问题中强调的那样。我对简单到中级几何数学没有问题。 - Lukman

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- verdesmarald · Accepted Answer

当我需要实现一个用于计算图形作业中从点到区间的距离的方法时，我发现这个页面非常有启发性：关于线和点到线的距离特别是其中的点到射线或线段的距离部分可能对您有兴趣。

以下是文章中的伪代码（其中·表示点积，d()表示两点之间的距离）：

distance( Point P, Segment P0:P1 )
{
      v = P1 - P0
      w = P - P0
      if ( (c1 = w·v) <= 0 )
            return d(P, P0)
      if ( (c2 = v·v) <= c1 )
            return d(P, P1)
      b = c1 / c2
      Pb = P0 + bv
      return d(P, Pb)
}

该方法依赖于点积来确定垂线的底部是否在区间内，如果不在，则确定哪个端点更接近。