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

Let's say you have a two dimensional plane with 2 points (called a and b) on it represented by an x integer and a y integer for each point.

How can you determine if another point c is on the line segment defined by a and b?

I use python most, but examples in any language would be helpful.

Solution 1:

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

Solution 2:

Here's how I'd do it:

def distance(a,b):
    return sqrt((a.x - b.x)**2 + (a.y - b.y)**2)

def is_between(a,c,b):
    return distance(a,c) + distance(c,b) == distance(a,b)

Solution 3:

Check if the cross product of b-a and c-a is0: that means all the points are collinear. If they are, check if c's coordinates are between a's and b's. Use either the x or the y coordinates, as long as a and b are separate on that axis (or they're the same on both).

def is_on(a, b, c):
    "Return true iff point c intersects the line segment from a to b."
    # (or the degenerate case that all 3 points are coincident)
    return (collinear(a, b, c)
            and (within(a.x, c.x, b.x) if a.x != b.x else 
                 within(a.y, c.y, b.y)))

def collinear(a, b, c):
    "Return true iff a, b, and c all lie on the same line."
    return (b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y)

def within(p, q, r):
    "Return true iff q is between p and r (inclusive)."
    return p <= q <= r or r <= q <= p

This answer used to be a mess of three updates. The worthwhile info from them: Brian Hayes's chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background. Vincent's answer helped to improve this one. And it was Hayes who suggested testing only one of the x or the y coordinates; originally the code had and in place of if a.x != b.x else.