CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Check a Point lies in a Line segment

1. Member Join Date
Jan 2006
Location
Bangalore, India
Posts
209

## Check a Point lies in a Line segment

Gurus,

Can you please guide me to find the logic or algoirthm to check whether a Point P(x, y) lies in a Line constructed by two Points A(x, y) & B(x, y)?

Thanks in advance.  Reply With Quote

2. ## Re: Check a Point lies in a Line segment

A line's formula is y = a*x + b. To find if a point is on the line that goes from point A to point B do this:
1. Find the line equation
2. Put the point coordinates inside the equation and see if it fits
(Note: due to float precision, a threshold value must be set and checked against according to the wanted precision).
Code:
```const float EPSILON = 0.001f;

bool IsPointOnLine(Point linePointA, Point linePointB, Point point)
{
float a = (linePointB.y - linePointA.y) / (linePointB.x - linePointB.x);
float b = linePointA.y - a * linePointA.x;
if ( fabs(point.y - (a*point.x+b)) < EPSILON)
{
return true;
}

return false;
}```
To see if the point is on the segment that goes from A to B, check also that the point coordinates are inside the bounding box created by points A and B.
Last edited by Zachm; April 4th, 2007 at 01:55 AM.  Reply With Quote

3. Member Join Date
Jan 2006
Location
Bangalore, India
Posts
209

## Re: Check a Point lies in a Line segment

Hi

Thank you for your reply.

Your code works fine for my case. i did some small additional condition statements in that code you have mentioned.

Code:
```// First checking if (x, y) is in the range of the line segment's end points.
if (is_between (x, x1, x2, tolerance) && is_between (y, y1, y2, tolerance))
{
if ((x2 - x1) == 0.0f) // Vertical line.
{
return (true);
}

const float M = (y2 - y1) / (x2 - x1); // Slope
const float C = -(M * x1) + y1; // Y intercept

// Checking if (x, y) is on the line passing through the end points.
return (std::fabs (y - (M * x + C)) <= tolerance);
}```
it works fine for line segment.

The same logic i used in a loop to find whether a point exist in a polyline segment. but it is not working for some points.

here is the code i've used for polyline check:

Code:
```for (FDT::Vertex_count_type i = 0u;
i < (m_polyline_geometry.vertex_count - 1u); ++ i)
{
const float & x1 = m_polyline_geometry.vertex_ptr [i].x;
const float & y1 = m_polyline_geometry.vertex_ptr [i].y;
const float & x2 = m_polyline_geometry.vertex_ptr [i + 1u].x;
const float & y2 = m_polyline_geometry.vertex_ptr [i + 1u].y;

// First checking if (x, y) is in the range of the line segment's end points.
if (is_between (x, x1, x2, tolerance) && is_between (y, y1, y2, tolerance))
{
if ((x2 - x1) == 0.0f) // Vertical line.
{
return (true);
}

const float M = (y2 - y1) / (x2 - x1); // Slope
const float C = -(M * x1) + y1; // Y intercept

// Checking if (x, y) is on the line passing through the end points.
return (std::fabs (y - (M * x + C)) <= tolerance);
}
}

return (false);```
can you tell me where is the problem?
Last edited by PremalathaP; April 5th, 2007 at 12:53 AM.  Reply With Quote

4. ## Re: Check a Point lies in a Line segment

I can see one thing that may lead to unwanted results: Originally Posted by PremalathaP
Code:
```         if ((x2 - x1) == 0.0f) // Vertical line.
{
return (true);
}```
This float comparison may fail due to float rounding errors. You should NEVER use the == operator on floats !!!

Do this instead:
Code:
```       if ((x2 - x1) <= tolerance) // Vertical line.
{
return (true);
}```
There could also be something wrong with the is_between function - you didn't post it so I can't tell .
Can you post a set of points for which it didn't work ? It would make the job of finding out what's wrong a lot easier. Post the input as well as the bad output.  Reply With Quote

5. Member Join Date
Jan 2006
Location
Bangalore, India
Posts
209

## Re: Check a Point lies in a Line segment

Hi thank you so much for your help.

After changing the condition check for vertical line, it is working fine.

here is the is_between function code:

Code:
```bool is_between (float x, float bound1, float bound2, float tolerance) const
{
// Handles cases when 'bound1' is greater than 'bound2' and when
// 'bound2' is greater than 'bound1'.
return (((x >= (bound1 - tolerance)) && (x <= (bound2 + tolerance))) ||
((x >= (bound2 - tolerance)) && (x <= (bound1 + tolerance))));
}```
Regards,
Premalatha.  Reply With Quote

6. Junior Member Join Date
Feb 2010
Posts
1

## Re: Check a Point lies in a Line segment

hi premalatha,
function was really useful for me. could you please tell me like what value you have used for tolarance ??

I had use case where u tried using your fucntion it worked well but failed for few cases.  Reply With Quote

7. ## Re: Check a Point lies in a Line segment Originally Posted by sumanth.st hi premalatha,
function was really useful for me. could you please tell me like what value you have used for tolarance ??

I had use case where u tried using your fucntion it worked well but failed for few cases.
First of all, if you want a private answer, enable private messaging in your user profile at Code Guru.
The tolerance to use is dependent on how accurate you want the test to be, and the scale your data points reside on.
Sometimes, testing different tolerance values can prove useful.

Maybe you are experiencing some other problem that makes your code not
work on some cases. If you post it then people can have a look point you at possible coding errors.

It might also be useful to post specific data and tolerance you used for which your code didn't work as expected.

Regards,
Zachm  Reply With Quote

8. Member Join Date
Jun 2006
Posts
148

## Re: Check a Point lies in a Line segment

Hi

Nice peace of code, though i am not sound at geometry but i think the following condition may return unwanted results.

Code:
```         if ((x2 - x1) <= tolerance) // Vertical line.
{
return (true);
}```
Instead it should use Absolute values of (x2-x1), other wise in case when the line is not vertical it may return true. [ if x2 < x1]

The condition should be like
Code:
```         if (std::fabs (x2 - x1) <= tolerance) // Vertical line.
{
return (true);
}```
Tell me if i m wrong.  Reply With Quote

9. ## Re: Check a Point lies in a Line segment

In general, of course you are right I made an assumption that x2 must be >= x1.
This assumption could be made because of the following check which is done just before:
Code:
`    if (is_between (x, x1, x2, tolerance) && is_between (y, y1, y2, tolerance))`
I assumed (and later was proved correct) that the is_between function checks that x >= x1 (-tolerance) and that x <= x2 (+tolerance). This implies that x2 must be greater than x1, so x2-x1 is a positive number.

Regards,
Zachm  Reply With Quote

10. Member Join Date
Jun 2006
Posts
148

## Re: Check a Point lies in a Line segment Originally Posted by Zachm I assumed (and later was proved correct) that the is_between function checks that x >= x1 (-tolerance) and that x <= x2 (+tolerance). This implies that x2 must be greater than x1, so x2-x1 is a positive number.
Still i m confused with the condition used in the function "is_between"

Oring (||) has been used in the function and hence if x lies between x1 and x2 it will return true, whether x2>x1 or not.

Considering the first part of the condition in is_between

Code:
`((x >= (bound1 - tolerance)) && (x <= (bound2 + tolerance)))`
Here we can say x lies between x1 and x2 and x2-x1 is positive number.

but the second part,
Code:
`((x >= (bound2 - tolerance)) && (x <= (bound1 + tolerance)))`
Here also we can say that x lies between x1 and x2 but cant confirm that x2-x1 will be positive number.  Reply With Quote

11. ## Re: Check a Point lies in a Line segment Originally Posted by Zachm I assumed (and later was proved correct) that the is_between function checks that x >= x1 (-tolerance) and that x <= x2 (+tolerance). This implies that x2 must be greater than x1, so x2-x1 is a positive number.

Regards,
Zachm
Ok, so maybe I wasn't proved to be correct in the end You are correct again. The above code may return unwanted results due to the specific implementation of the is_between function and it is solved by using fabs as you suggested.
It seems you have 100% understanding of the code above and a keen eye to see that bug in the code, so you don't have to feel confused so much Regards,
Zachm  Reply With Quote

12. Junior Member Join Date
Feb 2014
Posts
1

## Re: Check a Point lies in a Line segment

I realize this is an old discussion but reading it helped me realize that the quickest check of whether a point (x0, y0) is on the line segment defined by two other points (x1, y1) and (x2, y2) would be to check the two slopes . Basically, the pseudo code
return ((isequal(x1,x0) || isequal(x2,x0)) ? isequal(x1,x2) : isequal((y0-y1)/(x0-x1), (y0-y2)/(x0-x2)))

where isequal is a function that includes a tolerance check, i.e.,

function isequal(x,y){return(abs(x-y)<=epsilon)}

the point (x0, y0) can be anywhere in 2D space. The above removes any requirement such as x1 < x0 < x2.  Reply With Quote

13. Member +  Join Date
Jul 2013
Posts
576

## Re: Check a Point lies in a Line segment Originally Posted by tusharm01 return ((isequal(x1,x0) || isequal(x2,x0)) ? isequal(x1,x2) : isequal((y0-y1)/(x0-x1), (y0-y2)/(x0-x2)))
This part,

(isequal(x1,x0) || isequal(x2,x0)) ? isequal(x1,x2)

states that the point is on the segment if x0 = x1 = x2. But is this true? Don't you need to also check y0 in relation to y1 and y2 to be sure?

In this part,

isequal((y0-y1)/(x0-x1), (y0-y2)/(x0-x2))

you're comparing whether two slopes are equal. But what happens if the point is very close to an endpoint? Then the slopes may differ a lot for points that are in fact very close to the segment.

Say for example one segment endpoint is at (0,0) and the other at (1,0). And say the point is at (epsilon, epsilon) which is close enought to be on the segment. Then the first slope becomes 1 and the second approximately 0. The check will return false which is wrong.

So unfortunately your approach doesn't work well.
Last edited by razzle; February 22nd, 2014 at 01:57 AM.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)