5
$\begingroup$

I have a line segment defined by two end points. And I have another randomly chosen third point and I want to find out if the third point is on the line segment or not. By "On the line segment", I mean that exactly on the line segment, not intersecting the line segment and end up on the other side of the line segment. I hope I explained the issue. Some mathematical explanation along with algorithm to it is earnestly requested.

Thanks

Improve this question
$\endgroup$
3
  • $\begingroup$ Are you working with integers or floating point numbers? $\endgroup$
    – Alan Wolfe
    Feb 28, 2016 at 4:34
  • $\begingroup$ Floating point numbers. $\endgroup$
    – sajis997
    Feb 28, 2016 at 11:44
  • $\begingroup$ ah ok, assumed so. The answer I gave is appropriate for your usage case then. If using integer coordinates there would be a way to get an EXACT answer without thresholding, but with floating point it's basically unavoidable. $\endgroup$
    – Alan Wolfe
    Feb 28, 2016 at 21:04

1 Answer 1

Reset to default
5
$\begingroup$

Let's say you have your two points that define the line segment: $A$ and $B$, and a point $P$ that you are testing to see if it is on the line segment.

Firstly, you get a normalized vector from $A$ to $B$, as well as the distance from $A$ to $B$.

direction = normalize(B - A);
length = length(B-A);

Next, you use dot product to project the point $P$ onto the line segment defined by $A$ and $B$, by first getting the vector from $A$ to $P$ and then dot producting that against the direction vector.

PRelative = P-A;
projection = dot(PRelative, direction);

This projection value represents how far down the line segment from $A$ to $B$ that the closest point to $P$ is. It may be a negative distance, or it might be farther from $A$ than $B$ is, so you next clamp this value to the line segment.

projection = clamp(projection, 0.0, length);

Note that in your case, instead of clamping, you could just detect when the projection was out of bounds and return false at this point as well.

Continuing on, you now have the distance from $A$ to $B$ that the closest point to $P$ is, as the value in $projection$. You calculate that actual point:

closestPoint = A + projection * direction;

If $closestPoint$ == $P$, you know that $P$ lies on the line segment defined by $A$ and $B$ because the closest point on that line segment is the point $P$ itself.

However, in practice, you might run into some numerical precision problems due to having limited accuracy in computer calculations.

To get around this, instead of checking if $closestPoint$ and $P$ are the same, you should probably instead consider them the same if the distance between them is smaller than some threshold value. This way, if precision issues come up, you'll still get the answers you want in the cases you want them.

Too large of a threshold value, and you will get points being considered on the line that you really wouldn't consider on the line (if this happens, make your threshold smaller).

Too small of a threshold value, and some points that you would consider being on the line will not register as being on the line (if this happens, make your threshold larger).

Improve this answer
$\endgroup$
9
  • $\begingroup$ The above explanation is focused on clarity, but there are some other optimizations you can do if you need it to be even faster. For instance, instead of using a distance threshold, you can use a squared distance threshold, to avoid a square root. You could also avoid the normalization step, and clamp between 0 and 1 instead of from 0 to length. The above explanation should be plenty fast for most needs though! $\endgroup$
    – Alan Wolfe
    Feb 28, 2016 at 21:06
  • $\begingroup$ You are suggesting a dot product between a point and vector. Should it not be between two vectors. In that case, we have to derive vector from point. We can do it by generating a vector between the point and the start point of the line segment $\endgroup$
    – sajis997
    Feb 29, 2016 at 16:15
  • $\begingroup$ You are right, good eye. Fixed! $\endgroup$
    – Alan Wolfe
    Feb 29, 2016 at 16:23
  • $\begingroup$ Dont we have to normalize the vector "PRelative" ? $\endgroup$
    – sajis997
    Feb 29, 2016 at 21:10
  • 1
    $\begingroup$ You might consider asking some new questions about that, perhaps even on the math stack exchange sites. You might also give dot product / vector projection a Google and read up on that a little bit, there is some great info on the net on that stuff. Congratulations though, I'm really glad to hear you got it working (: $\endgroup$
    – Alan Wolfe
    Mar 1, 2016 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.