122

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.

5
  • 4
    I see a LOT of length = sqrt(x) stuff going on in these answers; they might work, but they aren't fast. Consider using length-squared; if you're just comparing squared length values to each other, there's no loss of accuracy, and you save slow calls to sqrt().
    – ojrac
    Nov 30, 2008 at 0:34
  • 1
    Is the point c represented by 2 integers as well? If so then do you want to know if c is exactly along a real straight line between a and b or lies on the raster approximation of the straight line between a and b? This is an important clarification.
    – RobS
    Dec 2, 2008 at 9:34
  • A similar question was asked here: stackoverflow.com/q/31346862/1914034 with a solution when a buffer distance from the line is needed Jul 16, 2015 at 12:09
  • 2
    Warning to future readers: A fair number of answers are incorrect or incomplete. A few edge cases that frequently don't work are horizontal and vertical lines.
    – Stefnotch
    Aug 4, 2019 at 18:57

21 Answers 21

151

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
18
  • 5
    -epsilon < crossproduct < epsilon and min(a.x, b.x) <= c.x <= max(a.x, b.x) and min(a.y, b.y) <= c.y <= max(a.y, b.y) is sufficient, isn't it?
    – jfs
    Nov 30, 2008 at 2:01
  • 9
    The absolute value of the crossproduct is twice the area of the triangle formed by the three points (with the sign indicating the side the third point) so IMHO you should use an epsilon that is proportional to the distance between the two endpoints.
    – bart
    Nov 30, 2008 at 9:21
  • 2
    Can you tell us why wouldn't it work with integers ? I don't see the problem, provided that the epsilon check is replaced by "!= 0".
    – Cyrille Ka
    Dec 1, 2008 at 15:48
  • 2
    Yes, the extra parenthesis is just a typo. 4 years have passed before someone said something. :)
    – Cyrille Ka
    Nov 22, 2012 at 3:36
  • 6
    You should rename a,b,c to make it clearer which are the segment end points and which is the query point. Jul 19, 2013 at 16:37
66

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)
7
  • 9
    The only problem with this is the numerical stability - taking differences of numbers and so on is apt to lose precision. Nov 30, 2008 at 0:10
  • 35
    -epsilon < (distance(a, c) + distance(c, b) - distance(a, b)) < epsilon
    – jfs
    Nov 30, 2008 at 1:04
  • 1
    @jfs what do you mean by that? Whats the check with the epsilon for?
    – nww04
    Aug 30, 2017 at 8:40
  • 3
    @NeonWarge: sqrt() returns a float. == is a wrong thing for floats in most cases. math.isclose() could be used instead. There was no math.isclose() in 2008 and therefore I've provided the explicit inequality with epsilon (abs_tol in math.isclose() speak).
    – jfs
    Aug 30, 2017 at 9:03
  • 1
    @jfs why not abs(distance(a, c) + distance(c, b) - distance(a, b)) < epsilon
    – Marcel
    Oct 5, 2021 at 5:29
40

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

10
  • Since range checking faster would it be better to range check first then check for collinear if in bounding box.
    – Grant M
    Jan 17, 2013 at 14:53
  • 1
    The function is_on(a,b,c) is wrong for the case where a == b != c. In such a case it will return true, even though c does not intersect a line segment from a to b. Oct 20, 2015 at 13:35
  • @SuperFlux, I just tried running that, and got False. Oct 22, 2015 at 1:54
  • 2
    I think this answer is pretty clearly superior to the current accepted answer.
    – Rick
    Jun 8, 2016 at 14:27
  • 1
    collinear(a, b, c) is testing floating point numbers by equality. Shouldnt it use an epsilon/tolerance?
    – jwezorek
    Mar 30, 2020 at 16:36
10

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)
2
  • 1
    That doesn't take rounding errors (inexactness of coordinates) into account.
    – bart
    Nov 30, 2008 at 9:23
  • This is the right idea, I think, but short on detail (how do we check that equation in practice?) and a bit buggy: the last y3 ought to be y2. Nov 30, 2008 at 17:37
9

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)
4
  • 1
    If c.x or c.y are float then the first == in is_between() could fail (btw it is a crossproduct in disguise).
    – jfs
    Nov 30, 2008 at 4:11
  • add to is_between(): a, b = self.a, self.b
    – jfs
    Nov 30, 2008 at 17:26
  • It looks like that will return true if all three points are the same (which is all right, imho) but false if exactly two of the points are the same -- a pretty inconsistent way to define betweenness. I posted an alternative in my answer. Nov 30, 2008 at 19:21
  • fixed that by another cmp trick, but this code starts to smell ;-)
    – vincent
    Nov 30, 2008 at 20:20
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
2
  • (It's just called cross product.)
    – user202729
    Jun 19, 2022 at 11:17
  • 1
    Cross product is in 3d. Wedge product is what it's called in general dimensions.
    – Jules
    Jun 20, 2022 at 11:28
5

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
1
  • As Jonathan Leffler mentions in another comment, this has numerical issues that other approaches like the cross-product avoid. The chapter I link to in my answer explains. Nov 30, 2008 at 17:30
5

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

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
10
  • Shouldn't the last condition be more like: ABS(product - lengthca * lengthba) < epsilon? Nov 30, 2008 at 0:12
  • Shouldn't you be comparing squared lengths instead? Square roots are to be avoided. Also, if this is unavoidable due to overflow, you can use math.hypot instead of math.sqrt (with the appropriate change of arguments). Nov 30, 2008 at 0:41
  • I wonder about that epsilon, too. Can you explain it? Of course, if we must deal with floats, we must be careful about comparisons, but it's not clear to me why an epsilon makes this particular comparison more accurate. Nov 30, 2008 at 0:42
  • I concur. There is several good answer to this question, and this one is fine. But this code needs to be amended to not use sqrt, and the last comparison fixed.
    – Cyrille Ka
    Nov 30, 2008 at 0:47
  • @Jonathan: indeed the code is more familiar and elegant using abs. Thanks. Nov 30, 2008 at 2:16
3

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

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.

5
  • It solves how to draw a line through a two-dimensional integer space between two arbitrary points and its mathematically correct. If the third point is one of the points on that line then it is, by definition, between those two points.
    – cletus
    Dec 1, 2008 at 10:12
  • 1
    No, Bresenham's Line Algorithm solves how to create an approximation of a line segment in a two-dimensional integer space. I don't see from the original poster's message that it was a question about rasterization.
    – Cyrille Ka
    Dec 1, 2008 at 15:54
  • "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." (emphasis added by me).
    – cletus
    Dec 3, 2008 at 11:17
  • 2
    I think Bresenham's Line Algorithm gives closet integer points to a line, that can then be used to draw the line. They may not be on the line. For example if for (0,0) to (11,13) the algorithm will give a number pixels to draw but there are no integer points except the end points, because 11 and 13 are coprime.
    – Grant M
    Jan 15, 2013 at 13:49
  • 1
    How can a solution that is correct for real space ( ℝ×ℝ) not be correct for integer space (ℕ×ℕ), as ℕ∈ℝ. Or do you mean: "is not optimal for…" instead of 'is not correct ?
    – Ideogram
    Jan 9, 2019 at 6:47
1

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

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;
        }
1
  • The correct way to avoid precision problems in most other approaches. Also significantly more efficient that most other approraches. Apr 5, 2017 at 4:20
1

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.

1

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

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);
}
2
  • 1
    dotProduct can only tell about alignement. Your code is incomplete !!! With a(0,0), b(4,0), c(1,1) you have dotproduct = (1-0)*(1-4) +(1-0)*(1-0) = -3+1=-3
    – user43968
    Jun 2, 2018 at 16:03
  • @user43968 you're right. Forgot that i was working with vectors back then. The answer from Cyrille Ka is the right (full) one!
    – golwig
    Dec 17, 2020 at 16:47
1

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.

0

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)

4
  • How about crazy floating point precision problems when some of the coordinates are close or identical? Apr 5, 2017 at 4:18
  • Computers don't do floating points well. In a computer there's no such thing as infinitely continuously adjustable values. So if you are using Floating points, you have to establish define and use some small epsilon value as a determinant, and any two points closer than that epsilon should be considered the same point. Determine the point that IS on the same line and the same distance from the end points. If your candidate point is within your epsilon of that calculated point, then call it identical. Apr 5, 2017 at 12:04
  • My point was that this answer is unusable because of precision problems when you actually implement it in code. So nobody should use it. A lovely answer on a math test. But a compete failure in a comp-sci course. I came here looking for the dot-product method (which is correct); so I thought I'd take a few moments to flag the many answers in this thread that are incorrect so others that are familiar with the correct solution won't be tempted to use them. Apr 13, 2017 at 17:01
  • You are correct about the issues that arise due to computers inability to represent every possible real number on a line. You are incorrect that any solution (including dot product method) can be immune to these issues. Any solution can suffer from these problems. Unless you make some allowances for acceptable epsilon, a point that is exactly on the line (but whose coordinates are not representable in ieee floating point binary representation), will fail the dot product test as well, since the computer will represent the point's coordinates inaccurately by some amount. Apr 13, 2017 at 18:04
0

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;
}
1
  • It looks like this code would just works with vertical and horizontal line segments. What if ptLineStart is (0,0), ptLineEnd is (2,2) and ptPoint is (1, 1)?
    – vac
    Feb 10, 2018 at 21:17
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.