开发者

Checking a line segment is within a distance from a point

I have two points A and B that define a line segment on a device screen plus another point C. Using efficient and short algorithm that is easy to code (preferably using standard math library), how do I check if the line segment AB is within a distance R from C?

I know there is a simple way to find the shortest distance from a point to a line, but it assume the line is infinitely long. What I have is a line segment with two endpoints.

I considered posting this in Mat开发者_高级运维h SE but decided not to since I don't want to get all those long math formula as the answer like in https://math.stackexchange.com/questions/2837/how-to-tell-if-a-line-segment-intersects-with-a-circle . What I need is an efficient and readable computer algorithm, not a formal math theorem.

p/s: I have the following Objective-C method skeleton that needs to be implemented:

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

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

}

EDIT WITH SOLUTION:

thanks to answer from veredesmarald (which I already accepted) I've implemented the method, put here as reference for other people:

+ (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;
}


When I had to implement a method to determine the distance from a point to an interval for a graphics assignment, I found this page very informative: About Lines and Distance of a Point to a Line

In particular, the section Distance of a Point to a Ray or Segment should be of interest to you.

Pseudocode from the article (where · is dot product and d() is distance between two points):

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)
}

This method relies on the dot product to determine if the base of the perpendicular is within the interval, and if not which end point is closer.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜