-
April 4th, 2007, 01:11 AM
#1
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.
-
April 4th, 2007, 01:52 AM
#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.
-
April 5th, 2007, 12:48 AM
#3
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.
-
April 5th, 2007, 07:49 AM
#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.
-
April 5th, 2007, 11:41 PM
#5
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.
-
February 11th, 2010, 11:42 PM
#6
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.
-
February 12th, 2010, 10:48 AM
#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
-
July 30th, 2010, 02:27 AM
#8
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.
-
July 30th, 2010, 01:59 PM
#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
-
August 2nd, 2010, 01:51 AM
#10
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.
-
August 3rd, 2010, 08:45 AM
#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
-
February 3rd, 2014, 03:05 PM
#12
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.
-
February 4th, 2014, 06:30 AM
#13
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.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|