我有两个点A和B在设备屏幕上加上另一个点C定义一个线段.使用易于编码(优选使用标准数学库)的有效和简短的算法,我如何检查线段AB是否在距离C的距离R
我知道有一种简单的方法可以找到一个点到一条线的最短距离,但是它假设线条是无限长的.我所拥有的是具有两个端点的线段.
我认为在数学SE中发贴,但决定不要因为我不想得到所有这些长数学公式作为答案像https://math.stackexchange.com/questions/2837/how-to-tell-if-a-line-segment-intersects-with-a-circle.我需要的是一种高效可读的计算机算法,而不是正式的数学定理.
p / s：我有以下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;
}
解决方法
当我不得不实现一种方法来确定图形分配的点到间隔的距离时,我发现这个页面非常翔实：
About Lines and Distance of a Point to a Line
特别是,一个点到雷或段的距离应该是你感兴趣的.
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)
}
该方法依赖于点积来确定垂直的基底是否在间隔内,如果不是最终点.
