How can you determine a point is between two other

Question

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.

Answer 1

Here's how I did it at school. I forgot why it is not a good idea.

EDIT:

@Darius Bacon: cites a "Beautiful Code" book which contains an explanation why the belowed code is not a good idea.

#!/usr/bin/env python
from __future__ import division

epsilon = 1e-6

class Point:
    def __init__(self, x, y):
        self.x, self.y = x, y

class LineSegment:
    """
    >>> ls = LineSegment(Point(0,0), Point(2,4))
    >>> Point(1, 2) in ls
    True
    >>> Point(.5, 1) in ls
    True
    >>> Point(.5, 1.1) in ls
    False
    >>> Point(-1, -2) in ls
    False
    >>> Point(.1, 0.20000001) in ls
    True
    >>> Point(.1, 0.2001) in ls
    False
    >>> ls = LineSegment(Point(1, 1), Point(3, 5))
    >>> Point(2, 3) in ls
    True
    >>> Point(1.5, 2) in ls
    True
    >>> Point(0, -1) in ls
    False
    >>> ls = LineSegment(Point(1, 2), Point(1, 10))
    >>> Point(1, 6) in ls
    True
    >>> Point(1, 1) in ls
    False
    >>> Point(2, 6) in ls 
    False
    >>> ls = LineSegment(Point(-1, 10), Point(5, 10))
    >>> Point(3, 10) in ls
    True
    >>> Point(6, 10) in ls
    False
    >>> Point(5, 10) in ls
    True
    >>> Point(3, 11) in ls
    False
    """
    def __init__(self, a, b):
        if a.x > b.x:
            a, b = b, a
        (self.x0, self.y0, self.x1, self.y1) = (a.x, a.y, b.x, b.y)
        self.slope = (self.y1 - self.y0) / (self.x1 - self.x0) if self.x1 != self.x0 else None

    def __contains__(self, c):
        return (self.x0 <= c.x <= self.x1 and
                min(self.y0, self.y1) <= c.y <= max(self.y0, self.y1) and
                (not self.slope or -epsilon < (c.y - self.y(c.x)) < epsilon))

    def y(self, x):        
        return self.slope * (x - self.x0) + self.y0

if __name__ == '__main__':
    import  doctest
    doctest.testmod()

Answer 2

Any point on the line segment (a, b) (where a and b are vectors) can be expressed as a linear combination of the two vectors a and b:

In other words, if c lies on the line segment (a, b):

c = ma + (1 - m)b, where 0 <= m <= 1

Solving for m, we get:

m = (c.x - b.x)/(a.x - b.x) = (c.y - b.y)/(a.y - b.y)

So, our test becomes (in Python):

def is_on(a, b, c):
    """Is c on the line segment ab?"""

    def _is_zero( val ):
        return -epsilon < val < epsilon

    x1 = a.x - b.x
    x2 = c.x - b.x
    y1 = a.y - b.y
    y2 = c.y - b.y

    if _is_zero(x1) and _is_zero(y1):
        # a and b are the same point:
        # so check that c is the same as a and b
        return _is_zero(x2) and _is_zero(y2)

    if _is_zero(x1):
        # a and b are on same vertical line
        m2 = y2 * 1.0 / y1
        return _is_zero(x2) and 0 <= m2 <= 1
    elif _is_zero(y1):
        # a and b are on same horizontal line
        m1 = x2 * 1.0 / x1
        return _is_zero(y2) and 0 <= m1 <= 1
    else:
        m1 = x2 * 1.0 / x1
        if m1 < 0 or m1 > 1:
            return False
        m2 = y2 * 1.0 / y1
        return _is_zero(m2 - m1)

Answer 3

Here is some Java code that worked for me:

boolean liesOnSegment(Coordinate a, Coordinate b, Coordinate  c) {

    double dotProduct = (c.x - a.x) * (c.x - b.x) + (c.y - a.y) * (c.y - b.y);
    if (dotProduct < 0) return true;
    return false;
}

Answer 4

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.

Answer 5

how about just ensuring that the slope is the same and the point is between the others?

given points (x1, y1) and (x2, y2) ( with x2 > x1) and candidate point (a,b)

if (b-y1) / (a-x1) = (y2-y2) / (x2-x1) And x1 < a < x2

Then (a,b) must be on line between (x1,y1) and (x2, y2)

Answer 6

Here is my solution with C# in Unity.

private bool _isPointOnLine( Vector2 ptLineStart, Vector2 ptLineEnd, Vector2 ptPoint )
{
    bool bRes = false;
    if((Mathf.Approximately(ptPoint.x, ptLineStart.x) || Mathf.Approximately(ptPoint.x, ptLineEnd.x)))
    {
        if(ptPoint.y > ptLineStart.y && ptPoint.y < ptLineEnd.y)
        {
            bRes = true;
        }
    }
    else if((Mathf.Approximately(ptPoint.y, ptLineStart.y) || Mathf.Approximately(ptPoint.y, ptLineEnd.y)))
    {
        if(ptPoint.x > ptLineStart.x && ptPoint.x < ptLineEnd.x)
        {
            bRes = true;
        }
    }
    return bRes;
}