Check is a point (x,y) is between two points drawn on a straight line

Question

I have drawn a line between two points A(x,y)---B(x,y) Now I have a third point C(x,y). I want to know that if C lies on the line which is drawn between A and B. I want to do it in java language. I have found couple of answers similar to this. But, all have some problems and no one is perfect.

Fuscous

You could try creating a Line2D object that represents A & B and use it's contains method – Lederhosen

y=mx+b. Find the equation of the line containing A and B, and then see if C(x,y) satisfies the equation? – Serous

this is what I have tried, but what to do when x2 and x1 are same float ratio = (y2 - y1) / (x2 - x1); Then: width = x2 - x1; for(int i = 0; i < width; i++) { float x = x1 + i; float y = y1 + (ratio * i); points.add(new Point(x,y)); } – Fuscous

@Serous can you please explain a bit more, i am not good with math. How to do it ? – Fuscous

mathsisfun.com/algebra/line-equation-2points.html or the answer from @SeniorJD. – Serous

user2061477, any solution that uses (only) gradients will fail spectacularly for vertical lines as the gradient approaches infinity. The answer from @MrROY will bypass those problems. – Youngling

Please have a look at this (older) [SO thread][1] [1]: #328607 – Lanai

contains will always return false for line2D – Salpiglossis

Answer 1

if (distance(A, C) + distance(B, C) == distance(A, B))
    return true; // C is on the line.
return false;    // C is not on the line.

or just:

return distance(A, C) + distance(B, C) == distance(A, B);

The way this works is rather simple. If C lies on the AB line, you'll get the following scenario:

A-C------B

and, regardless of where it lies on that line, dist(AC) + dist(CB) == dist(AB). For any other case, you have a triangle of some description and 'dist(AC) + dist(CB) > dist(AB)':

A-----B
 \   /
  \ /
   C

In fact, this even works if C lies on the extrapolated line:

C---A-------B

provided that the distances are kept unsigned. The distance dist(AB) can be calculated as:

  ___________________________
 /           2              2
V (A.x - B.x)  + (A.y - B.y)

Keep in mind the inherent limitations (limited precision) of floating point operations. It's possible that you may need to opt for a "close enough" test (say, less than one part per million error) to ensure correct functioning of the equality.

Tavis

The "(" taken after if expected – Pierro

This assumes the line is equi-distant from A and B. i.e. it passes between the middle of A and B, not through it. – Labiate

@Peter, if you mean the point (C) is equidistant, no. The equality will hold if the point lies anywhere on the line. If it's not on the line then you would have a discrepancy in distances (forming a triangle). – Youngling

This solution may be better for handling error. e.g. if the difference in distance is less than a pixel, C may appear on the line A-B. – Labiate

How does this work for the extrapolated line? In the example given, it is clear that d(A,C) + d(B,C) != d(A,B). If you could get the signed distance(something like a vector), you could check this, but the formula given explicitly doesn't work for that example. – Sipple

This solution has a mathematical error in it. I tested the following: C(5, 15), A(5, 12), and B(5, 25). Your solution of distance(C, A) + distance(C, B) == distance(A, B) returned false instead of true. If you could please explain why this does not work, I would appreciate it. – Ablution

@Ablution There's something wrong with your calculations because distance(C, A) = 3, distance(C, B) = 10 and distance(A, B) = 13. – Lithophyte

An optimisation in this specific case where you don't re-use the distance value is is to not do the sqrt. – Jamshedpur

@DamianDixon That's not correct here, since you are adding the results of two square roots. (Sqrt(A) + Sqrt(B))^2 != (A + B). It's fine if you are comparing two distances directly, but not this way. – Goosestep

distance(A, C) + distance(B, C) == distance(A, B) won't be true most of the times,though itis supposed to be, as Math.sqrt results in decimals – Linolinocut

This is great if you are using real numbers. However, for floating point arithmetic this is unlikely to produce the right answer. If you add an epsilon value to the check to compensate for that, the error unintuitively becomes an ellipse around the line, rather an actual distance from the line itself. – Runofthemine

Answer 2

ATTENTION! Math-only!

You can try this formula. Put your A(x1, y1) and B(x2, y2) coordinates to formula, then you'll get something like

y = k*x + b; // k and b - numbers

Then, any point which will satisfy this equation, will lie on your line. To check that C(x, y) is between A(x1, y1) and B(x2, y2), check this: (x1<x<x2 && y1<y<y2) || (x1>x>x2 && y1>y>y2).

Example

A(2,3) B(6,5)

The equation of line:

(y - 3)/(5 - 3) = (x - 2)/(6 - 2)
(y - 3)/2 = (x - 2)/4
4*(y - 3) = 2*(x - 2)
4y - 12 = 2x - 4
4y = 2x + 8
y = 1/2 * x + 2; // equation of line. k = 1/2, b = 2;

Let's check if C(4,4) lies on this line.

2<4<6 & 3<4<5 // C between A and B

Now put C coordinates to equation:

4 = 1/2 * 4 + 2
4 = 2 + 2 // equal, C is on line AB

PS: as @paxdiablo wrote, you need to check if line is horizontal or vertical before calculating. Just check

y1 == y2 || x1 == x2

Pierro

what is the purpose of y = k*x + b; // k and b - numbers what is the value of k and b ? – Fuscous

It depends on A and B coordinates. – Pierro

Don't try this at home if your lines can be horizontal or vertical :-) – Youngling

@Youngling it works for horizontal and vertical lines as well ;) – Pierro

Really? What is the k value for the line from (1,0) to (1,2) :-) Or just plug those two coords into your method: (x-1)/(1-1) is going to cause you (and Java) much grief and gnashing of teeth. It's not a bad answer but you need to detect and adjust for infinite gradients first. – Youngling

+∞. But remember that for horizontal and vertical lines there is no more linear dependence. There is no dependence at all :) It is easy to check before calculating. – Pierro

This worked perfect for me. Very simple because of the mathematical explanation. The algorithm is then very simple. Works for all styles of a line. Even when C is not within A & B then it works! – Tertia

Do we have any faster solution if we have to search the point in say 25-30 lines? – Swab

I believe if you do (x1 - x2)(y - y1) == (y1 - y2)(x - x1), you do not need to do a horizontal or vertical check prior. Obviously the checks are to avoid divide by zero, but this does not suffer from that. – Ablution

However, bounds checking is necessary for horizontal and vertical lines. – Ablution

Building on the solution by czifro with bound check it should be (x1 - x2) * (y - y1) == (y1 - y2) * (x - x1) && x >= Math.min(x1, x2) && x <= Math.max(x1, x2) && y >= Math.min(y1, y2) && y <= Math.max(y1, y2) – Geneva

this is my implementation of this solution in C, already including the handling of the horizontal/vertical lines and the degenerate case -> gist.github.com/felipeek/93c873395506868e50ea6f2323eb3399 – Jubilee

Answer 3

If you just want to check whether the point C is on the infinite line passing through the points A and B (rather than check whether C is on the line segment from A to B, i.e. C is also between them), the simplest implementation is:

// Are a, b and c on the same line?
public static boolean inLine(Point a, Point b, Point c) {
   return (a.x - c.x)*(c.y - b.y) == (c.x - b.x)*(a.y - c.y);
}

This is morally equivalent to checking that gradient(A, C) == gradient(C, B), but rearranged to use multiplication instead of division to avoid divide-by-zero when one of the gradients is vertical (also, it gives exact results if using integers).

It is equivalent to checking that the cross product of (A - C) and (C - B) is equal to 0. The property of three points being on the same line is known as collinearity.

Note: there is a different test to see if C appears on the line between A and B if you draw it on a screen. Maths assumes that A, B, C are infinitely small points.

Labiate

This has the same problem as SeniorJD's answer. The gradient for a vertical line is infinite (or, more correctly, undefined but tends towards infinity). – Youngling

@Youngling Not dividing by 0 any more but I am not this solves the whole problem. – Labiate

For vertical lines or horizontal lines, this test (by itself) will return true if the point has the same x value for vertical lines, or y value for horizontal lines, regardless of whether or not the point is in between the end points of the line. – Stevie

how would this work for horizontal lines on say the x axis – Expediential

Have to check that C.x in A.x..B.x and C.y in A.y..B.y. Otherwise you will match collinear points which are not between A and B – Earthbound

Answer 4

The above answers are unnecessarily complicated. The simplest is as follows.

1. if (x-x1)/(x2-x1) = (y-y1)/(y2-y1) = alpha (a constant), then the point C(x,y) will lie on the line between pts 1 & 2.

2. If alpha < 0.0, then C is exterior to point 1.

3. If alpha > 1.0, then C is exterior to point 2.
4. Finally if alpha = [0,1.0], then C is interior to 1 & 2.

Hope this answer helps.

Simulated

I don't understand the concept of exterior of a point. – Poston

In this context, exterior means the point lies on the infinite line that passes point 1 and 2, but not on the line segment between the same two points. – Runofthemine

It deosn't make sense in math nor does it in programming. I guess there is a typo. the first "=" should be minus or something like that – Requiem

Answer 5

I think all the methods here have a pitfall, in that they are not dealing with rounding errors as rigorously as they could. Basically the methods described will tell you if your point is close enough to the line using some straightforward algorithm and that it will be more or less precise.

Why precision is important? Because it's the very problem presented by op. For a computer program there is no such thing as a point on a line, there is only point within an epsilon of a line and what that epsilon is needs to be documented.

Let's illustrate the problem. Using the distance comparison algorithm:

Let's say a segment goes from (0, 0) to (0, 2000), we are using floats in our application (which have around 7 decimal places of precision) and we test whether a point on (1E-6, 1000) is on the line or not.

The distance from either end of the segment to the point is 1000.0000000005 or 1000 + 5E-10, and, thus, the difference with the addition of the distance to and from the point is around 1E-9. But none of those values can be stored on a float with enough precission and the method will return true.

If we use a more precise method like calculating the distance to the closest point in the line, it returns a value that a float has enough precision to store and we could return false depending on the acceptable epsilon.

I used floats in the example but the same applies to any floating point type such as double.

One solution is to use BigDecimal and whichever method you want if incurring in performance and memory hit is not an issue.

A more precise method than comparing distances for floating points, and, more importantly, consistently precise, although at a higher computational cost, is calculating the distance to the closest point in the line.

Shortest distance between a point and a line segment

It looks like I'm splitting hairs but I had to deal with this problem before. It's an issue when chaining geometric operations. If you don't control what kind of precission loss you are dealing with, eventually you will run into difficult bugs that will force you to reason rigorously about the code in order to fix them.

Beastly

Answer 6

An easy way to do that I believe would be the check the angle formed by the 3 points. If the angle ACB is 180 degrees (or close to it,depending on how accurate you want to be) then the point C is between A and B.

Loring

Answer 7

I think this might help

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

That solution uses only integers given you only provide integers which removes some pitfalls as well

Reticulum

Answer 8

Here is my C# solution. I believe the Java equivalent will be almost identical.

Notes:

1. Method will only return true if the point is within the bounds of the line (it does not assume an infinite line).

2. It will handle vertical or horizontal lines.

3. It calculates the distance of the point being checked from the line so allows a tolerance to be passed to the method.

    /// <summary>
    /// Check if Point C is on the line AB
    /// </summary>
    public static bool IsOnLine(Point A, Point B, Point C, double tolerance)
    {
        double minX = Math.Min(A.X, B.X) - tolerance;
        double maxX = Math.Max(A.X, B.X) + tolerance;
        double minY = Math.Min(A.Y, B.Y) - tolerance;
        double maxY = Math.Max(A.Y, B.Y) + tolerance;
   
        //Check C is within the bounds of the line
        if (C.X >= maxX || C.X <= minX || C.Y <= minY || C.Y >= maxY)
        {
            return false;
        }
   
        // Check for when AB is vertical
        if (A.X == B.X)
        {
            if (Math.Abs(A.X - C.X) >= tolerance)
            {
                return false;
            }
            return true;
        }
   
        // Check for when AB is horizontal
        if (A.Y == B.Y)
        {
            if (Math.Abs(A.Y - C.Y) >= tolerance)
            {
                return false;
            }
            return true;
        }
   
   
        // Check istance of the point form the line
        double distFromLine = Math.Abs(((B.X - A.X)*(A.Y - C.Y))-((A.X - C.X)*(B.Y - A.Y))) / Math.Sqrt((B.X - A.X) * (B.X - A.X) + (B.Y - A.Y) * (B.Y - A.Y));
   
        if (distFromLine >= tolerance)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
   

Flews

Does this work for diagonal lines too? – Topeka

Answer 9

if ( (ymid - y1) * (x2-x1) == (xmid - x1) * (y2-y1) )  **is true, Z lies on line AB**

Start Point : A (x1, y1),
End Point : B (x2, y2),
Point That is on Line AB or Not : Z (xmid, ymid)

I just condensed everyone's answers and this formula works the best for me.

1. It avoids division by zero
2. No distance calculation required
3. Simple to implement

Edit: In case you are dealing with floats, which you most probably are, use this:

   if( (ymid - y1) * (x2-x1) - (xmid - x1) * (y2-y1) < DELTA )

where the tolerance DELTA is a value close to zero. I usually set it to 0.05

Heirdom

Answer 10

def DistBetwPoints(p1, p2):
    return math.sqrt( (p2[0] - p1[0])**2 + (p2[1] - p1[1])**2 )

# "Check if point C is between line endpoints A and B"
def PointBetwPoints(A, B, C):
    dist_line_endp = DistBetwPoints(A,B)
    if DistBetwPoints(A,C)>dist_line_endp:       return 1
    elif DistBetwPoints(B,C)>dist_line_endp:     return 1
    else:                                        return 0

Detoxify

Answer 11

Here is a JavaScript function I made. 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.

You will receive an object back with some useful info:

• on_projected_line - If pt3 lies anywhere on the line including outside the points.
• on_line - If pt3 lies on the line and between or on pt1 and pt2.
• x_between - If pt3 is between or on the x bounds.
• y_between - If pt3 is between or on the y bounds.
• between - If x_between and y_between are both true.

/**
 * @description Check if pt3 is on line defined by pt1 and pt2.
 * @param {Object} pt1 The first point defining the line.
 * @param {float} pt1.x
 * @param {float} pt1.y
 * @param {Object} pt2 The second point defining the line.
 * @param {float} pt2.x
 * @param {float} pt2.y
 * @param {Object} pt3 The point to test.
 * @param {float} pt3.x
 * @param {float} pt3.y
 */
function pointOnLine(pt1, pt2, pt3) {
    const result = {
        on_projected_line: true,
        on_line: false,
        between_both: false,
        between_x: false,
        between_y: false,
    };

    // Determine if on line interior or exterior
    const x = (pt3.x - pt1.x) / (pt2.x - pt1.x);
    const y = (pt3.y - pt1.y) / (pt2.y - pt1.y);

    // Check if on line equation
    result.on_projected_line = x === y;

    // Check within x bounds
    if (
        (pt1.x <= pt3.x && pt3.x <= pt2.x) ||
        (pt2.x <= pt3.x && pt3.x <= pt1.x)
    ) {
        result.between_x = true;
    }

    // Check within y bounds
    if (
        (pt1.y <= pt3.y && pt3.y <= pt2.y) ||
        (pt2.y <= pt3.y && pt3.y <= pt1.y)
    ) {
        result.between_y = true;
    }

    result.between_both = result.between_x && result.between_y;
    result.on_line = result.on_projected_line && result.between_both;
    return result;
}

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

Michalemichalski

Answer 12

One good library is available for this by turfjs.

var pt = turf.point([0, 0]);
var line = turf.lineString([[-1, -1],[1, 1],[1.5, 2.2]]);
var isPointOnLine = turf.booleanPointOnLine(pt, line);

If you want to reduce the accuracy use epsilon option

turf.booleanPointOnLine([c1, c2], turf.lineString([[x1, y1], [x2, y2]]), {epsilon: 10}))

Hope this is helpful

https://turfjs.org/docs/#booleanPointOnLine

Testimony