<p>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.</p>

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

<pre><code>direction = normalize(B - A);
length = length(B-A);
</code></pre>

<p>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.</p>

<pre><code>PRelative = P-A;
projection = dot(PRelative, direction);
</code></pre>

<p>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.</p>

<pre><code>projection = clamp(projection, 0.0, length);
</code></pre>

<p>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.</p>

<p>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:</p>

<pre><code>closestPoint = A + projection * direction;
</code></pre>

<p>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.</p>

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

<p>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.</p>

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

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

CC BY-SA 3.0
2016-02-28T21:06:22.633Z
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
CC BY-SA 3.0
2016-02-29T16:15:17.363Z
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
CC BY-SA 3.0
2016-02-29T16:23:50.907Z
You are right, good eye.  Fixed!
Alan Wolfe
CC BY-SA 3.0
2016-02-29T21:10:42.860Z
Dont we have to normalize the vector "PRelative" ?
sajis997
CC BY-SA 3.0
2016-02-29T21:14:21.913Z
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
CC BY-SA 3.0
2016-02-29T22:25:58.587Z
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<float>::epsilon() , I return true, else return false. Is there anything worng with the concept ? I am still getting the wrong answer.
sajis997
CC BY-SA 3.0
2016-02-29T22:27:40.800Z
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
CC BY-SA 3.0
2016-03-01T13:54:24.103Z
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
CC BY-SA 3.0
2016-03-01T14:53:03.910Z
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
CC BY-SA 3.0
2016-02-28T04:47:55.957Z
2016-02-29T16:23:22.420Z
2016-02-29T16:23:22.420Z
Alan Wolfe
<p>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.</p>

<p>Thanks</p>

CC BY-SA 3.0
2016-02-28T04:34:39.430Z
Are you working with integers or floating point numbers?
Alan Wolfe
CC BY-SA 3.0
2016-02-28T11:44:50.393Z
Floating point numbers.
sajis997
CC BY-SA 3.0
2016-02-28T21:04:44.877Z
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.
Alan Wolfe
<vectors>
Test if a point is on a line segment
sajis997
# Test if a point is on a line segment

(Asked by: username_0 on 2016-02-27)

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

**Tags:** vectors

> **Comments:**
> **username_1**: Are you working with integers or floating point numbers?  
> **username_0**: Floating point numbers.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2016-02-28. Score: 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).

> **Comments:**
> **username_1**: 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!  
> **username_0**: 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  
> **username_1**: You are right, good eye.  Fixed!  
> **username_0**: Dont we have to normalize the vector "PRelative" ?  
> **username_1**: 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.  
> **username_0**: 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<float>::epsilon() , I return true, else return false. Is there anything worng with the concept ? I am still getting the wrong answer.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_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 (:  

---

