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;
}
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.
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.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With