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

Question

How would I write this function? Any examples appreciated

function isPointBetweenPoints(currPoint, point1, point2):Boolean {

    var currX = currPoint.x;
    var currY = currPoint.y;

    var p1X = point1.x;
    var p1y = point1.y;

    var p2X = point2.x;
    var p2y = point2.y;

    //here I'm stuck
}

Answer 1

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.

Answer 2

   Distance(point1, currPoint)
 + Distance(currPoint, point2)
== Distance(point1, point2)

But be careful if you have floating point values, things are different for them...

When concerned about the computational cost of computing "the square roots", don't:
Just compare "the squares".

Answer 3

This is independent of Javascript. Try the following algorithm, with points p1=point1 and p2=point2, and your third point being p3=currPoint:

v1 = p2 - p1
v2 = p3 - p1
v3 = p3 - p2
if (dot(v2,v1)>0 and dot(v3,v1)<0) return between
else return not between

If you want to be sure it's on the line segment between p1 and p2 as well:

v1 = normalize(p2 - p1)
v2 = normalize(p3 - p1)
v3 = p3 - p2
if (fabs(dot(v2,v1)-1.0)<EPS and dot(v3,v1)<0) return between
else return not between

Answer 4

You want to check whether the slope from point1 to currPoint is the same as the slope from currPoint to point2, so:

m1 = (currY - p1Y) / (currX - p1X);
m2 = (p2Y - currY) / (p2X - currX);

You also want to check whether currPoint is inside the box created by the other two, so:

return (m1 == m2) && (p1Y <= currY && currY <= p2Y) && (p1X <= currX && currX <= p2X);

Edit: This is not a very good method; look at maxim1000's solution for a much more correct way.

Answer 5

I'll use Triangle approach:

First, I'll check the Area, if the Area is close to 0, then the Point lies on the Line.

But think about the case where the length of AC is so great, then the Area increases far from 0, but visually, we still see that B is on AC: that when we need to check the height of the triangle.

To do this, we need to remember the formula we learn from first grade: Area = Base * Height / 2

Here is the code:

    bool Is3PointOn1Line(IList<Vector2> arrVert, int idx1, int idx2, int idx3)
    {
        //check if the area of the ABC triangle is 0:
        float fArea = arrVert[idx1].x * (arrVert[idx2].y - arrVert[idx3].y) +
            arrVert[idx2].x * (arrVert[idx3].y - arrVert[idx1].y) +
            arrVert[idx3].x * (arrVert[idx1].y - arrVert[idx2].y);
        fArea = Mathf.Abs(fArea);
        if (fArea < SS.EPSILON)
        {
            //Area is zero then it's the line
            return true;
        }
        else
        {
            //Check the height, in case the triangle has long base
            float fBase = Vector2.Distance(arrVert[idx1], arrVert[idx3]);
            float height = 2.0f * fArea / fBase;
            return height < SS.EPSILON;
        }
    }

Usage:

Vector2[] arrVert = new Vector2[3];

arrVert[0] = //...
arrVert[1] = //...
arrVert[2] = //...

if(Is3PointOn1Line(arrVert, 0, 1, 2))
{
    //Ta-da, they're on same line
}

PS: SS.EPSILON = 0.01f and I use some function of Unity (for ex: Vector2.Distance), but you got the idea.

Answer 6

Ready for what seems to be infinitely simpler than some of these other solutions?

You pass it three points (three objects with an x and y property). Points 1 and 2 define your line, and point 3 is the point you are testing.

function pointOnLine(pt1, pt2, pt3) {
    const dx = (pt3.x - pt1.x) / (pt2.x - pt1.x);
    const dy = (pt3.y - pt1.y) / (pt2.y - pt1.y);
    const onLine = dx === dy

    // Check on or within x and y bounds
    const betweenX = 0 <= dx && dx <= 1;
    const betweenY = 0 <= dy && dy <= 1;

    return onLine && betweenX && betweenY;
}

console.log('pointOnLine({x: 0, y: 0}, {x: 1, y: 1}, {x: 2, y: 2})');
console.log(pointOnLine({ x: 0, y: 0 }, { x: 1, y: 1 }, { x: 2, y: 2 }));

console.log('pointOnLine({x: 0, y: 0}, {x: 1, y: 1}, {x: 0.5, y: 0.5})');
console.log(pointOnLine({ x: 0, y: 0 }, { x: 1, y: 1 }, { x: 0.5, y: 0.5 }));

Edit: Simplified further according to RBarryYoung's observation.

Answer 7

This approach is similar to Steve's approach, just shorter and improved to use as little memory and process power as possible. But first the mathematical idea:

Let a, b be the ends of the line, ab the difference between them and p the point to check. Then p is exactly then on the line, if

a + i * ab = p

with i being a number in the interval [0;1] representing the index on the line. We can write that as two separate equations (for 2D):

a.x + i * ab.x = p.x
a.y + i * ab.y = p.y
⇔
i = (p.x - a.x) / ab.x
i = (p.y - a.y) / ab.y

Which gives us to requirements for p to be on the line from a to b:

(p.x - a.x) / ab.x = (p.y - a.y) / ab.y
and
0 ≤ i ≤ 1

In code:

function onLine(a, b, p) {
    var i1 = (p.x - a.x) / (b.x - a.x), i2 = (p.y - a.y) / (b.y - a.y);
    return i1 == i2 && i1 <= 0 && i1 >= 1;
}

Technically you could even inline i2 but that makes it even harder to read.

Answer 8

  private static boolean pointInLine(int2 lineBegin, int2 lineEnd, int2 point)
  { boolean result = false;
    
    int2 b = int2(min(lineBegin.x, lineEnd.x), min(lineBegin.y, lineEnd.y));
    int2 e = int2(max(lineBegin.x, lineEnd.x), max(lineBegin.y, lineEnd.y));
    if (point.x >= b.x && point.x <= e.x &&
        point.y >= b.y && point.y <= e.y)
    { int2 normal = lineEnd.sub(lineBegin).perp();
      int2 d0     = lineBegin.sub(point);
      if (d0.dot(normal) == 0x0)
      { result = true;
      }
    }
    return result;
  }

This works for any slope, even if lineBegin == lineEnd == point.

• First, create two points b and e, which ensures b <= e. (This is two support lines that have a negative slope) Check if point lands on the box (inclusive) created by those two points.
• Then, get the normal of the line, which is a vector perpendicular to it. You can do this by negating the x and transposing, x,y --> y, -x.
• Then you can simply create a vector that points to the line from the point or to the point from the line, it doesn't matter and doesn't have to be from the center of the line. Once you do that check if the vector is perpendicular to the normal by getting the dot product of the normal and the point vector.

It also makes it a bit easier on you if you've got some sort of math lib or at least a struct with x,y components. But you can do this with scalar components aswell. But getting the dot product and the normal are very simple calculations.

Here's the dot product: .dot(int2 v) = (x * v.x + y * v.y)

Here's the perpendicular: .perp() = new int2(y, -x)

.sub() .add() Do what you'd expect and params are in the same order.