Check a Point lies in a Line segment
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 13 of 13

Thread: Check a Point lies in a Line segment

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

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

  2. #2
    Join Date
    Oct 2006
    Posts
    616

    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.

  3. #3
    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.

  4. #4
    Join Date
    Oct 2006
    Posts
    616

    Re: Check a Point lies in a Line segment

    I can see one thing that may lead to unwanted results:
    Quote 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.

  5. #5
    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.

  6. #6
    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.

  7. #7
    Join Date
    Oct 2006
    Posts
    616

    Re: Check a Point lies in a Line segment

    Quote Originally Posted by sumanth.st View Post
    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

  8. #8
    Join Date
    Jun 2006
    Posts
    147

    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.

  9. #9
    Join Date
    Oct 2006
    Posts
    616

    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

  10. #10
    Join Date
    Jun 2006
    Posts
    147

    Re: Check a Point lies in a Line segment

    Quote Originally Posted by Zachm View Post
    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.

  11. #11
    Join Date
    Oct 2006
    Posts
    616

    Re: Check a Point lies in a Line segment

    Quote Originally Posted by Zachm View Post
    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

  12. #12
    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.

  13. #13
    Join Date
    Jul 2013
    Posts
    243

    Re: Check a Point lies in a Line segment

    Quote Originally Posted by tusharm01 View Post
    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 12: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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center