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

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)

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

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)

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 = xself.y = yclass Segment:def __init__(self, a, b):self.a = aself.b = bdef 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 andabs(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)

You can use the wedge and dot product:

def dot(v,w): return v.x*w.x + v.y*w.ydef wedge(v,w): return v.x*w.y - v.y*w.xdef is_between(a,b,c):v = a - bw = b - creturn wedge(v,w) == 0 and dot(v,w) > 0

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

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 usebool isBetween(double a, double b, double c) {// return if c is between a and bdouble 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 lineif(l2.y - l1.y == 0) return isBetween(l1.x, l2.x, p.x); // horizontal linedouble 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;}

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 constantdef 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 Falsedotproduct = (c.x - a.x)*(b.x - a.x) + (c.y - a.y)*(b.y - a.y)if dotproduct < 0.0: return Falseif abs(dotproduct*dotproduct - lengthca2*lengthba2) > epsilon: return False return True

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

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 pythonfrom __future__ import divisionepsilon = 1e-6class Point:def __init__(self, x, y):self.x, self.y = x, yclass LineSegment:""">>> ls = LineSegment(Point(0,0), Point(2,4))>>> Point(1, 2) in lsTrue>>> Point(.5, 1) in lsTrue>>> Point(.5, 1.1) in lsFalse>>> Point(-1, -2) in lsFalse>>> Point(.1, 0.20000001) in lsTrue>>> Point(.1, 0.2001) in lsFalse>>> ls = LineSegment(Point(1, 1), Point(3, 5))>>> Point(2, 3) in lsTrue>>> Point(1.5, 2) in lsTrue>>> Point(0, -1) in lsFalse>>> ls = LineSegment(Point(1, 2), Point(1, 10))>>> Point(1, 6) in lsTrue>>> Point(1, 1) in lsFalse>>> Point(2, 6) in ls False>>> ls = LineSegment(Point(-1, 10), Point(5, 10))>>> Point(3, 10) in lsTrue>>> Point(6, 10) in lsFalse>>> Point(5, 10) in lsTrue>>> Point(3, 11) in lsFalse"""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 Nonedef __contains__(self, c):return (self.x0 <= c.x <= self.x1 andmin(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.y0if __name__ == '__main__':import doctestdoctest.testmod()

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.

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 < epsilonx1 = a.x - b.xx2 = c.x - b.xy1 = a.y - b.yy2 = c.y - b.yif _is_zero(x1) and _is_zero(y1):# a and b are the same point:# so check that c is the same as a and breturn _is_zero(x2) and _is_zero(y2)if _is_zero(x1):# a and b are on same vertical linem2 = y2 * 1.0 / y1return _is_zero(x2) and 0 <= m2 <= 1elif _is_zero(y1):# a and b are on same horizontal linem1 = x2 * 1.0 / x1return _is_zero(y2) and 0 <= m1 <= 1else:m1 = x2 * 1.0 / x1if m1 < 0 or m1 > 1:return Falsem2 = y2 * 1.0 / y1return _is_zero(m2 - m1)

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

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 vectorvar v = new Vector2D( @this.P0, c ).To3D();// Segment vectorvar s = new Vector2D( @this.P0, @this.P1 ).To3D();// Dot product of svar 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 linevar k = v*s/ss;// Convert our tolerance to the units of the scalar quanity kvar kd = tolerance / Math.Sqrt( ss );// Check that the projection is within the boundsif (k <= -kd || k >= (1+kd)){return false;}// Find the projection pointvar p = k*s;// Find the vector between test point and it's projectionvar 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.

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

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

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.

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)

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

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 boundsif($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;}