Find If Point Lies on Line Segment

How can you determine a point is between two other points on a line segment?

Check if the cross product of (b-a) and (c-a) is 0, as tells Darius Bacon, tells you if the points a, b and c are aligned.

But, as you want to know if c is between a and b, you also have to check that the dot product of (b-a) and (c-a) is positive and is less than the square of the distance between a and b.

In non-optimized pseudocode:

def isBetween(a, b, c):
    crossproduct = (c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y)

    # compare versus epsilon for floating point values, or != 0 if using integers
    if abs(crossproduct) > epsilon:
        return False

    dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y)
    if dotproduct < 0:
        return False

    squaredlengthba = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
    if dotproduct > squaredlengthba:
        return False

    return True

Find if point lies on line segment

If the point is on the line then:

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 - z1)

Calculate all three values, and if they are the same (to some degree of tolerance), your point is on the line.

To test if the point is in the segment, not just on the line, you can check that

x1 < x < x2, assuming x1 < x2, or
y1 < y < y2, assuming y1 < y2, or
z1 < z < z2, assuming z1 < z2

How to check if a point lies on a line between 2 other points

Assuming that point1 and point2 are different, first you check whether the point lies on the line. For that you simply need a "cross-product" of vectors point1 -> currPoint and point1 -> point2.

dxc = currPoint.x - point1.x;
dyc = currPoint.y - point1.y;

dxl = point2.x - point1.x;
dyl = point2.y - point1.y;

cross = dxc * dyl - dyc * dxl;

Your point lies on the line if and only if cross is equal to zero.

if (cross != 0)
  return false;

Now, as you know that the point does lie on the line, it is time to check whether it lies between the original points. This can be easily done by comparing the x coordinates, if the line is "more horizontal than vertical", or y coordinates otherwise

if (abs(dxl) >= abs(dyl))
  return dxl > 0 ? 
    point1.x <= currPoint.x && currPoint.x <= point2.x :
    point2.x <= currPoint.x && currPoint.x <= point1.x;
else
  return dyl > 0 ? 
    point1.y <= currPoint.y && currPoint.y <= point2.y :
    point2.y <= currPoint.y && currPoint.y <= point1.y;

Note that the above algorithm if entirely integral if the input data is integral, i.e. it requires no floating-point calculations for integer input. Beware of potential overflow when calculating cross though.

P.S. This algorithm is absolutely precise, meaning that it will reject points that lie very close to the line but not precisely on the line. Sometimes this is not what's needed. But that's a different story.

Determine if a point is between 2 other points on a line

Assuming that point1 and point2 are different, first you check whether the point lies on the line. For that you simply need a "cross-product" of vectors point1 -> currPoint and point1 -> point2.

dxc = currPoint.x - point1.x;
dyc = currPoint.y - point1.y;

dxl = point2.x - point1.x;
dyl = point2.y - point1.y;

cross = dxc * dyl - dyc * dxl;

Your point lies on the line if and only if cross is equal to zero.

if (cross != 0)
 return false;

Now, as you know that the point does lie on the line, it is time to check whether it lies between the original points. This can be easily done by comparing the x coordinates, if the line is "more horizontal than vertical", or y coordinates otherwise

if (abs(dxl) >= abs(dyl))
 return dxl > 0 ? 
   point1.x <= currPoint.x && currPoint.x <= point2.x :
   point2.x <= currPoint.x && currPoint.x <= point1.x;
else
 return dyl > 0 ? 
   point1.y <= currPoint.y && currPoint.y <= point2.y :
   point2.y <= currPoint.y && currPoint.y <= point1.y;

Note that the above algorithm if entirely integral if the input data is integral, i.e. it requires no floating-point calculations for integer input. Beware of potential overflow when calculating cross though.

P.S. This algorithm is absolutely precise, meaning that it will reject points that lie very close to the line but not precisely on the line. Sometimes this is not what's needed. But that's a different story.

Detecting if a point is of a line segment

Since my previous answer said how to determine if a point was on the line, and the real question appears to be "how can I tell if the point is near the line segment", I'm adding a new answer.

Here's the trick: first find the distance from your obstacle to each of the two endpoints of your line segment. These two distances don't uniquely determine the location of the obstacle, but they do uniquely determine a triangle with three specific side lengths, and then we can immediately use a bunch of geometry.

I fiddled with the colors a little. Anyway, I mentioned in a comment above that you should use the point-line distance formula to find the distance between the obstacle and the line. But that won't actually work. The reason is that is is the point-line distance. So, for both examples below, the formula will calculate the bold distance H in the picture.

That isn't right!!

So instead, here is the pseudocode for finding the distance from your obstacle to the line segment formed by the laser:

Find the distance from my point to the line segment!

if the angle at (x,y) is obtuse
    return A
else if the angle at (endx,endy) is obtuse
    return B
else
    return H

Here is the math you can use to implement the above pseudocode:

• To see if the angle at (x,y) is obtuse, find whether B^2 > A^2 + C^2. If so, the angle is obtuse.
• To see if the angle at (endx, endy) is obtuse, find whether A^2 > B^2 + C^2. If so, the angle is obtuse.
• To calculate H, use two different methods for finding the area of the triangle -- the usual base*height/2 and Heron's Formula.

This means you should:

set s = (A+B+C)/2
The area of the triangle is C*H/2
The area of the triangle is also sqrt(s*(s-A)*(s-B)*(s-C)) 
So H = 2/C * sqrt(s*(s-A)*(s-B)*(s-C)).

The end result is something like:

if B^2 > A^2 + C^2
    return A
else if A^2 > B^2 + C^2
    return B
else
    s = (A+B+C)/2
    return 2/C * sqrt(s*(s-A)*(s-B)*(s-C))

I think that should give you enough to accomplish what you are actually setting out to do. Good luck, and don't give up!

check if point lies on line segment

Floating-point arithmetic cannot store every number that you want it to. At some point, it has to approximate. Now, I'm guessing, the algorithm you got from Wikipedia is telling you:

y=mx+b

You know m, you know b, now plug in and make sure the equation holds true. Works great for mathematics. (The square root of 2 ) squared is equal to the square root of 4.

But now imagine you do that on a computer. The square root of 4 will come out exactly as 2, because computers are great at holding small integer numbers. However, your right hand side, the square root of 2, is going to be a bit off. You had to cut off some of the digits of it, so when you squared it, it might be 1.999998 or something like that. To accommodate for this, you need to check that y is approx. mx+b, so:

tolerance = .01
x,y
rhs = m*x + b //right hand side
dif = abs(rhs - y)
if dif < tolerance //the point is approximately on the segment

Then you'll have to check the bounding box for it (find max x,y, min x,y)

Of course, these methods aren't perfect (http://xkcd.com/217/) but for most practical applications, they will hold true enough. If you REALLY need exact numbers, I would suggest using Wolfram Alpha (I hear there's some API or something) or just writing your own exact number library.

How to check whether the given points are in the line segment or not?

Well, assuming if a line segment is defined by two points: enpoint and startpoint, this is how you can test if a given point is on this line segment:

boolean     isOnLineSegment(LineSegment seg, Point test) {

return  (   (test.y-seg.startPoint.y)/(test.x-seg.startPoint.x) == (test.y-seg.endPoint.y)/(test.x-seg.endPoint.y);

}

---

Related Topics