5

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

sajis997
  • 1,279
  • 1
  • 10
  • 15

1 Answers1

5

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

Alan Wolfe
  • 7,801
  • 3
  • 30
  • 76
  • 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! – Alan Wolfe Feb 28 '16 at 21:06
  • 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 – sajis997 Feb 29 '16 at 16:15
  • You are right, good eye. Fixed! – Alan Wolfe Feb 29 '16 at 16:23
  • Dont we have to normalize the vector "PRelative" ? – sajis997 Feb 29 '16 at 21:10
  • No, you don't and shouldn't! The length of PRelative is what is projected onto the direction vector (direction must be normalized though). Are you having problems getting it working still? If easily done you might try visualizing the various steps of finding the closest point on the line to see where it's breaking down. – Alan Wolfe Feb 29 '16 at 21:14
  • I am defining the vector between closestPoint and P and then getting the length of the vector . If the length of the vector is less than equal to std::numerical_limit::epsilon() , I return true, else return false. Is there anything worng with the concept ? I am still getting the wrong answer. – sajis997 Feb 29 '16 at 22:25
  • i would make the epsilon larger than that. The error that creeps in from floating point calculations is likely much larger than the smallest possible difference between two floating point numbers. I'd try a larger than needed number to start out, and then shrink it down to the smallest value that feels right. – Alan Wolfe Feb 29 '16 at 22:27
  • It works!, Some of the issues are not clear though. When to or not to normalize vectors. Since the normalization of a vector does not change its direction other than clamping its value between zero and one, it would be nice if some one elaborate more over this issue of when to normalize. – sajis997 Mar 01 '16 at 13:54
  • 1
    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 (: – Alan Wolfe Mar 01 '16 at 14:53