Computer Graphics Stack Exchange is a question and answer site for computer graphics researchers and programmers. It only takes a minute to sign up.
Sign up to join this community
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
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).