Check a Point lies in a Line segment

[PremalathaP]

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.

[Zachm]

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

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.

[PremalathaP]

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.

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

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?

[Zachm]

I can see one thing that may lead to unwanted results:

         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:

       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.

[PremalathaP]

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:

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.

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

[Zachm]

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

[shail2k4]

Hi

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

         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

         if (std::fabs (x2 - x1) <= tolerance) // Vertical line.
         {
            return (true);
         }

Tell me if i m wrong.

[Zachm]

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:

    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

[shail2k4]

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

((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,

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

[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

[tusharm01]

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.

[razzle]

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.