Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 Math 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;
}
like image 730
Lukman Avatar asked May 20 '11 07:05

Lukman


People also ask

How do you find the distance from a point to a line segment?

The distance from (x0, y0) to this line is measured along a vertical line segment of length |y0 − (− c/b)| = |by0 + c|/|b| in accordance with the formula. Similarly, for vertical lines (b = 0) the distance between the same point and the line is |ax0 + c|/|a|, as measured along a horizontal line segment.

How do you check if a point is on a line segment?

The cross product of A B → and A C → equal to 0 means that the vectors are colinear or that the points and or and coincide. If the cross product is not equal to zero, the point doesn't belongs on the segment.

How do you determine a line segment?

If you mark two points A and B on it and pick this segment separately, it becomes a line segment. This line segment has two endpoints A and B whose length is fixed. The length of this line segment is the distance between its endpoints A and B. So, a line segment is a piece or part of a line having two endpoints.


1 Answers

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.

like image 119
verdesmarald Avatar answered Oct 04 '22 00:10

verdesmarald