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.


Asked by: Catherine333 | Posted: 05-10-2021






Answer 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

Answered by: Blake934 | Posted: 06-11-2021



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

Answered by: Anna619 | Posted: 06-11-2021



Answer 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.

(This is coded for exact arithmetic with integers or rationals; if you pass in floating-point numbers instead, there will be problems with round-off errors. I'm not even sure what's a good way to define betweenness of 2-d points in float coordinates.)

Answered by: Carina808 | Posted: 06-11-2021



Answer 4

Here's another approach:

  • Lets assume the two points be A (x1,y1) and B (x2,y2)
  • The equation of the line passing through those points is (x-x1)/(y-y1)=(x2-x1)/(y2-y1) .. (just making equating the slopes)

Point C (x3,y3) will lie between A & B if:

  • x3,y3 satisfies the above equation.
  • x3 lies between x1 & x2 and y3 lies between y1 & y2 (trivial check)

Answered by: Wilson487 | Posted: 06-11-2021



Answer 5

The length of the segment is not important, thus using a square root is not required and should be avoided since we could lose some precision.

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

class Segment:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def is_between(self, c):
        # Check if slope of a to c is the same as a to b ;
        # that is, when moving from a.x to c.x, c.y must be proportionally
        # increased than it takes to get from a.x to b.x .

        # Then, c.x must be between a.x and b.x, and c.y must be between a.y and b.y.
        # => c is after a and before b, or the opposite
        # that is, the absolute value of cmp(a, b) + cmp(b, c) is either 0 ( 1 + -1 )
        #    or 1 ( c == a or c == b)

        a, b = self.a, self.b             

        return ((b.x - a.x) * (c.y - a.y) == (c.x - a.x) * (b.y - a.y) and 
                abs(cmp(a.x, c.x) + cmp(b.x, c.x)) <= 1 and
                abs(cmp(a.y, c.y) + cmp(b.y, c.y)) <= 1)

Some random example of usage :

a = Point(0,0)
b = Point(50,100)
c = Point(25,50)
d = Point(0,8)

print Segment(a,b).is_between(c)
print Segment(a,b).is_between(d)

Answered by: Alina559 | Posted: 06-11-2021



Answer 6

You can use the wedge and dot product:

def dot(v,w): return v.x*w.x + v.y*w.y
def wedge(v,w): return v.x*w.y - v.y*w.x

def is_between(a,b,c):
   v = a - b
   w = b - c
   return wedge(v,w) == 0 and dot(v,w) > 0

Answered by: Agata907 | Posted: 06-11-2021



Answer 7

Using a more geometric approach, calculate the following distances:

ab = sqrt((a.x-b.x)**2 + (a.y-b.y)**2)
ac = sqrt((a.x-c.x)**2 + (a.y-c.y)**2)
bc = sqrt((b.x-c.x)**2 + (b.y-c.y)**2)

and test whether ac+bc equals ab:

is_on_segment = abs(ac + bc - ab) < EPSILON

That's because there are three possibilities:

  • The 3 points form a triangle => ac+bc > ab
  • They are collinear and c is outside the ab segment => ac+bc > ab
  • They are collinear and c is inside the ab segment => ac+bc = ab

Answered by: Carlos807 | Posted: 06-11-2021



Answer 8

Here's a different way to go about it, with code given in C++. Given two points, l1 and l2 it's trivial to express the line segment between them as

l1 + A(l2 - l1)

where 0 <= A <= 1. This is known as the vector representation of a line if you're interested any more beyond just using it for this problem. We can split out the x and y components of this, giving:

x = l1.x + A(l2.x - l1.x)
y = l1.y + A(l2.y - l1.y)

Take a point (x, y) and substitute its x and y components into these two expressions to solve for A. The point is on the line if the solutions for A in both expressions are equal and 0 <= A <= 1. Because solving for A requires division, there's special cases that need handling to stop division by zero when the line segment is horizontal or vertical. The final solution is as follows:

// Vec2 is a simple x/y struct - it could very well be named Point for this use

bool isBetween(double a, double b, double c) {
    // return if c is between a and b
    double larger = (a >= b) ? a : b;
    double smaller = (a != larger) ? a : b;

    return c <= larger && c >= smaller;
}

bool pointOnLine(Vec2<double> p, Vec2<double> l1, Vec2<double> l2) {
    if(l2.x - l1.x == 0) return isBetween(l1.y, l2.y, p.y); // vertical line
    if(l2.y - l1.y == 0) return isBetween(l1.x, l2.x, p.x); // horizontal line

    double Ax = (p.x - l1.x) / (l2.x - l1.x);
    double Ay = (p.y - l1.y) / (l2.y - l1.y);

    // We want Ax == Ay, so check if the difference is very small (floating
    // point comparison is fun!)

    return fabs(Ax - Ay) < 0.000001 && Ax >= 0.0 && Ax <= 1.0;
}

Answered by: Fenton654 | Posted: 06-11-2021



Answer 9

The scalar product between (c-a) and (b-a) must be equal to the product of their lengths (this means that the vectors (c-a) and (b-a) are aligned and with the same direction). Moreover, the length of (c-a) must be less than or equal to that of (b-a). Pseudocode:

# epsilon = small constant

def isBetween(a, b, c):
    lengthca2  = (c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y)
    lengthba2  = (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)
    if lengthca2 > lengthba2: return False
    dotproduct = (c.x - a.x)*(b.x - a.x) + (c.y - a.y)*(b.y - a.y)
    if dotproduct < 0.0: return False
    if abs(dotproduct*dotproduct - lengthca2*lengthba2) > epsilon: return False 
    return True

Answered by: Eric184 | Posted: 06-11-2021



Answer 10

I needed this for javascript for use in an html5 canvas for detecting if the users cursor was over or near a certain line. So I modified the answer given by Darius Bacon into coffeescript:

is_on = (a,b,c) ->
    # "Return true if 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 withincheck(a,b,c))

withincheck = (a,b,c) ->
    if a[0] != b[0]
        within(a[0],c[0],b[0]) 
    else 
        within(a[1],c[1],b[1])

collinear = (a,b,c) ->
    # "Return true if a, b, and c all lie on the same line."
    ((b[0]-a[0])*(c[1]-a[1]) < (c[0]-a[0])*(b[1]-a[1]) + 1000) and ((b[0]-a[0])*(c[1]-a[1]) > (c[0]-a[0])*(b[1]-a[1]) - 1000)

within = (p,q,r) ->
    # "Return true if q is between p and r (inclusive)."
    p <= q <= r or r <= q <= p

Answered by: Audrey302 | Posted: 06-11-2021



Answer 11

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

Answered by: Lily604 | Posted: 06-11-2021



Answer 12

Ok, lots of mentions of linear algebra (cross product of vectors) and this works in a real (ie continuous or floating point) space but the question specifically stated that the two points were expressed as integers and thus a cross product is not the correct solution although it can give an approximate solution.

The correct solution is to use Bresenham's Line Algorithm between the two points and to see if the third point is one of the points on the line. If the points are sufficiently distant that calculating the algorithm is non-performant (and it'd have to be really large for that to be the case) I'm sure you could dig around and find optimisations.

Answered by: Alissa713 | Posted: 06-11-2021



Answer 13

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)

Answered by: Lenny879 | Posted: 06-11-2021



Answer 14

c# From http://www.faqs.org/faqs/graphics/algorithms-faq/ -> Subject 1.02: How do I find the distance from a point to a line?

Boolean Contains(PointF from, PointF to, PointF pt, double epsilon)
        {

            double segmentLengthSqr = (to.X - from.X) * (to.X - from.X) + (to.Y - from.Y) * (to.Y - from.Y);
            double r = ((pt.X - from.X) * (to.X - from.X) + (pt.Y - from.Y) * (to.Y - from.Y)) / segmentLengthSqr;
            if(r<0 || r>1) return false;
            double sl = ((from.Y - pt.Y) * (to.X - from.X) - (from.X - pt.X) * (to.Y - from.Y)) / System.Math.Sqrt(segmentLengthSqr);
            return -epsilon <= sl && sl <= epsilon;
        }

Answered by: Julia413 | Posted: 06-11-2021



Answer 15

An answer in C# using a Vector2D class

public static bool IsOnSegment(this Segment2D @this, Point2D c, double tolerance)
{
     var distanceSquared = tolerance*tolerance;
     // Start of segment to test point vector
     var v = new Vector2D( @this.P0, c ).To3D();
     // Segment vector
     var s = new Vector2D( @this.P0, @this.P1 ).To3D();
     // Dot product of s
     var ss = s*s;
     // k is the scalar we multiply s by to get the projection of c onto s
     // where we assume s is an infinte line
     var k = v*s/ss;
     // Convert our tolerance to the units of the scalar quanity k
     var kd = tolerance / Math.Sqrt( ss );
     // Check that the projection is within the bounds
     if (k <= -kd || k >= (1+kd))
     {
        return false;
     }
     // Find the projection point
     var p = k*s;
     // Find the vector between test point and it's projection
     var vp = (v - p);
     // Check the distance is within tolerance.
     return vp * vp < distanceSquared;
}

Note that

s * s

is the dot product of the segment vector via operator overloading in C#

The key is taking advantage of the projection of the point onto the infinite line and observing that the scalar quantity of the projection tells us trivially if the projection is on the segment or not. We can adjust the bounds of the scalar quantity to use a fuzzy tolerance.

If the projection is within bounds we just test if the distance from the point to the projection is within bounds.

The benefit over the cross product approach is that the tolerance has a meaningful value.

Answered by: Haris668 | Posted: 06-11-2021



Answer 16

C# version of Jules' answer:

public static double CalcDistanceBetween2Points(double x1, double y1, double x2, double y2)
{
    return Math.Sqrt(Math.Pow (x1-x2, 2) + Math.Pow (y1-y2, 2));
}

public static bool PointLinesOnLine (double x, double y, double x1, double y1, double x2, double y2, double allowedDistanceDifference)
{
    double dist1 = CalcDistanceBetween2Points(x, y, x1, y1);
    double dist2 = CalcDistanceBetween2Points(x, y, x2, y2);
    double dist3 = CalcDistanceBetween2Points(x1, y1, x2, y2);
    return Math.Abs(dist3 - (dist1 + dist2)) <= allowedDistanceDifference;
}

Answered by: Byron99 | Posted: 06-11-2021



Answer 17

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);
    return (dotProduct < 0);
}

Answered by: Maria821 | Posted: 06-11-2021



Answer 18

You could also use the very convenient scikit-spatial library.

For instance, you could create a Line object defined by the two points a and b:

>>> point_a = [0, 0]
>>> point_b = [1, 0]

>>> line = Line.from_points(point_a, point_b)

then you can use the side_point method of the Line class to check whether point c lies on line or not.

>>> line.side_point([0.5, 0])
0

If the output is 0, then point c lies on line.

Answered by: Emily746 | Posted: 06-11-2021



Answer 19

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)

Answered by: Elise121 | Posted: 06-11-2021



Answer 20

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

Answered by: Edgar815 | Posted: 06-11-2021



Answer 21

You can do it by solving the line equation for that line segment with the point coordinates you will know whether that point is on the line and then checking the bounds of the segment to know whether it is inside or outside of it. You can apply some threshold because well it is somewhere in space mostl likely defined by a floating point value and you must not hit the exact one. Example in php

function getLineDefinition($p1=array(0,0), $p2=array(0,0)){
    
    $k = ($p1[1]-$p2[1])/($p1[0]-$p2[0]);
    $q = $p1[1]-$k*$p1[0];
    
    return array($k, $q);
    
}

function isPointOnLineSegment($line=array(array(0,0),array(0,0)), $pt=array(0,0)){
    
    // GET THE LINE DEFINITION y = k.x + q AS array(k, q) 
    $def = getLineDefinition($line[0], $line[1]);
    
    // use the line definition to find y for the x of your point
    $y = $def[0]*$pt[0]+$def[1];

    $yMin = min($line[0][1], $line[1][1]);
    $yMax = max($line[0][1], $line[1][1]);

    // exclude y values that are outside this segments bounds
    if($y>$yMax || $y<$yMin) return false;
    
    // calculate the difference of your points y value from the reference value calculated from lines definition 
    // in ideal cases this would equal 0 but we are dealing with floating point values so we need some threshold value not to lose results
    // this is up to you to fine tune
    $diff = abs($pt[1]-$y);
    
    $thr = 0.000001;
    
    return $diff<=$thr;
    
}

Answered by: Adrian653 | Posted: 06-11-2021



Similar questions

python - determine if a line segment is within a polygon

I am trying to find out if a given line segment consisting of two or more points is inside a polygon here is a drawing to help capture the idea: picture to help visualize the problem All I found on the internet was a code that accepted a line passing through a polygon (could be only inside or just passing through a polygon) not exclusively i...


python - OS X: Determine Trash location for a given path

Simply moving the file to ~/.Trash/ will not work, as if the file os on an external drive, it will move the file to the main system drive.. Also, there are other conditions, like files on external drives get moved to /Volumes/.Trash/501/ (or whatever the current user's ID is) Given a file or folder path, what is the correct way to determine the trash folder? I imagine the language ...


python - How to determine if a directory is on same partition

Say I have an input file, and a target directory. How do I determine if the input file is on the same hard-drive (or partition) as the target directory? What I want to do is the copy a file if it's on a different, but move it if it's the same. For example: target_directory = "/Volumes/externalDrive/something/" input_foldername, input_filename = os.path.split(input_file) if same_partition(input_folde...


python - How do I determine if an email is Base64 encoded?

I am having difficulty determining if the body of a text email message is base64 encoded. if it is then use this line of code; making use of jython 2.2.1 dirty=base64.decodebytes(dirty) else continue as normal. This is the code I have atm. What line of code will allow me to extract this from the email: "Content-Transfer-Encoding: base64" import email, ...


python - How do I determine all of my IP addresses when I have multiple NICs?

I have multiple Network Interface Cards on my computer, each with its own IP address. When I use gethostbyname(gethostname()) from Python's (built-in) socket module, it will only return one of them. How do I get the others?


macos - How to determine number of files on a drive with Python?

I have been trying to figure out how to retrieve (quickly) the number of files on a given HFS+ drive with python. I have been playing with os.statvfs and such, but can't quite get anything (that seems helpful to me). Any ideas? Edit: Let me be a bit more specific. =] I am writing a timemachine-like wrapper around rsync for various reasons, and would like a very fast estimate...


Determine if a function is available in a Python module

I am working on some Python socket code that's using the socket.fromfd() function. However, this method is not available on all platforms, so I am writing some fallback code in the case that the method is not defined. What's the best way to determine if a method is defined at runtime? Is the...


How do I determine if an object has an attribute in Python?

How do I determine if an object has some attribute? For example: &gt;&gt;&gt; a = SomeClass() &gt;&gt;&gt; a.property Traceback (most recent call last): File &quot;&lt;stdin&gt;&quot;, line 1, in &lt;module&gt; AttributeError: SomeClass instance has no attribute 'property' How do I tell if a has the attribute property before using it?


code analysis - Tool to determine what lowest version of Python required?

Is there something similar to Pylint, that will look at a Python script (or run it), and determine which version of Python each line (or function) requires? For example, theoretical usage: $ magic_tool &lt;EOF with something: pass EOF 1: 'with' statement requires Python 2.6 or greater $ magic_tool &lt;EOF class Something: @classmethod def blah(cls): pass EOF 2: classmethod requi...


python - How can I determine the monitor refresh rate?

Is there a cross platform way to get the monitor's refresh rate in python (2.6)? I'm using Pygame and PyOpenGL, if that helps. I don't need to change the refresh rate, I just need to know what it is.


How to determine whether java is installed on a system through python?

Using Python, I want to know whether Java is installed.






Still can't find your answer? Check out these communities...



PySlackers | Full Stack Python | NHS Python | Pythonist Cafe | Hacker Earth | Discord Python



top