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

-
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 '08 at 0:34
There are a lot of answers below that are correct in real space but not for the stated integer space. See my answer below. –  cletus Nov 30 '08 at 8:57
How thick is the line? –  Dipstick Nov 30 '08 at 10:27
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 '08 at 9:34
RobS stated more succinctly than I the point I was getting at. –  cletus Dec 3 '08 at 11:22

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)
if abs(crossproduct) > epsilon : return False   # (or != 0 if using integers)

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
``````
-
`-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? –  J.F. Sebastian Nov 30 '08 at 2:01
Yes, silly me. That's the answer of Sridhar Iyer, with a crossproduct instead of slopes. As I said, there is several possible answers. :) –  Cyrille Ka Nov 30 '08 at 4:03
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 '08 at 9:21
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 '08 at 15:48
Yes, the extra parenthesis is just a typo. 4 years have passed before someone said something. :) –  Cyrille Ka Nov 22 '12 at 3:36

Check if the cross product of (b-a) and (c-a) is 0. Ah, wait, you say you want to know if it's on the line segment, not the same line. That's a little more work and I don't have time to answer; I'll delete this partial answer after someone fills in a proper one.

Update: Two more notes: first, Brian Hayes's chapter in Beautiful Code covers the design space for a collinearity-test function -- useful background. Second, [points that have since been answered].

Update 2: I like vincent's approach best now (and I'm embarrassed I didn't see it). But the comparison could still be done in a cleaner way, I think, like this:

``````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
``````

Update 3: Brian Hayes pointed out that you only need to range-check one coordinate, once you know the points are collinear. (Previously my code had "`and`" instead of "`if a.x != b.x`".)

-
Since range checking faster would it be better to range check first then check for collinear if in bounding box. –  Grant M Jan 17 '13 at 14:53

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)
``````
-
This is an elegant solution. –  Paul D. Eden Nov 29 '08 at 23:58
The only problem with this is the numerical stability - taking differences of numbers and so on is apt to lose precision. –  Jonathan Leffler Nov 30 '08 at 0:10
`-epsilon < (distance(a, c) + distance(c, b) - distance(a, b)) < epsilon` –  J.F. Sebastian Nov 30 '08 at 1:04

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)
``````
-
If c.x or c.y are float then the first `==` in `is_between()` could fail (btw it is a crossproduct in disguise). –  J.F. Sebastian Nov 30 '08 at 4:11
add to `is_between()`: `a, b = self.a, self.b` –  J.F. Sebastian Nov 30 '08 at 17:26
oops, the example worked because a and b are in the scope ! –  vincent Nov 30 '08 at 18:05
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. –  Darius Bacon Nov 30 '08 at 19:21
fixed that by another cmp trick, but this code starts to smell ;-) –  vincent Nov 30 '08 at 20:20

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)
-
That doesn't take rounding errors (inexactness of coordinates) into account. –  bart Nov 30 '08 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. –  Darius Bacon Nov 30 '08 at 17:37
@Darius: fixed that typo –  Harley Holcombe Dec 1 '08 at 0:26

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
-
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. –  Darius Bacon Nov 30 '08 at 17:30

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.

-
Bresenham's Line Algorithm solves different problem. –  J.F. Sebastian Nov 30 '08 at 19:44
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 '08 at 10:12
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 '08 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 '08 at 11:17
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 '13 at 13:49

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

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
``````
-
Shouldn't the last condition be more like: ABS(product - lengthca * lengthba) < epsilon? –  Jonathan Leffler Nov 30 '08 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). –  Darius Bacon Nov 30 '08 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. –  Darius Bacon Nov 30 '08 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 '08 at 0:47
@Jonathan: indeed the code is more familiar and elegant using abs. Thanks. –  Federico A. Ramponi Nov 30 '08 at 2:16

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

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)

-

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

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

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

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.

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment/328142", "fetch_time": 1405086960000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2014-23/segments/1404776427481.71/warc/CC-MAIN-20140707234027-00019-ip-10-180-212-248.ec2.internal.warc.gz", "warc_record_offset": 99615498, "warc_record_length": 28016, "token_count": 5949, "char_count": 19115, "score": 3.828125, "int_score": 4, "crawl": "CC-MAIN-2014-23", "snapshot_type": "latest", "language": "en", "language_score": 0.9329211115837097, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00029-of-00064.parquet"}