Check Is a Point (X,Y) Is Between Two Points Drawn on a Straight Line

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

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

How to check if a point lies on a line between 2 other points

Assuming that point1 and point2 are different, first you check whether the point lies on the line. For that you simply need a "cross-product" of vectors point1 -> currPoint and point1 -> point2.

dxc = currPoint.x - point1.x;
dyc = currPoint.y - point1.y;

dxl = point2.x - point1.x;
dyl = point2.y - point1.y;

cross = dxc * dyl - dyc * dxl;

Your point lies on the line if and only if cross is equal to zero.

if (cross != 0)
  return false;

Now, as you know that the point does lie on the line, it is time to check whether it lies between the original points. This can be easily done by comparing the x coordinates, if the line is "more horizontal than vertical", or y coordinates otherwise

if (abs(dxl) >= abs(dyl))
  return dxl > 0 ? 
    point1.x <= currPoint.x && currPoint.x <= point2.x :
    point2.x <= currPoint.x && currPoint.x <= point1.x;
else
  return dyl > 0 ? 
    point1.y <= currPoint.y && currPoint.y <= point2.y :
    point2.y <= currPoint.y && currPoint.y <= point1.y;

Note that the above algorithm if entirely integral if the input data is integral, i.e. it requires no floating-point calculations for integer input. Beware of potential overflow when calculating cross though.

P.S. This algorithm is absolutely precise, meaning that it will reject points that lie very close to the line but not precisely on the line. Sometimes this is not what's needed. But that's a different story.

How to check if a point is between two other points, but not limited to be aligned on a straight line?

Assuming we're on a plane and not a sphere, even though you mentioned lattitude/longitude...

A is "between" B and C if angle ∠ABC and angle ∠ACB are both less than or equal to ninety degrees.

Handily, we don't even need trigonometry to detect this; an angle ∠PQR is greater than ninety degrees iff PQ^2 + QR^2 < QR^2.

def lies_between(A,B,C):
    a = distance(B,C)
    b = distance(C,A)
    c = distance(A,B)
    return a**2 + b**2 >= c**2 and a**2 + c**2 >= b**2

def distance(A,B):
    return math.sqrt((A.x - B.x)**2 + (A.y - B.y)**2)

(Where ** is the exponentiation operator.)

Function to check a point is on a straight line

Your mathematics seems to be correct with the problem being one of interpretation.

First of all, you could streamline the math a bit:

x1,y1 = p1
x2,y2 = p2
m = (y2-y1)/(x2-x1)

def f(x): return y1 + m*(x-x1) 

def test(x,y,tol = 10):
    return abs(y-f(x)) <= tol

And then just use test(x,y) or test(*pol).

The problem is that in canvas coordinates, increasing y actually moves you down the canvas. In your sample data -- the line is drawn correctly in the sense that the line segment connecting the canvas points (313, 215) and (92,44) is a decreasing line.

Perhaps you want to plot points as (x,300-y) rather than (x,y).

How to tell whether a point is to the right or left side of a line

Use the sign of the determinant of vectors (AB,AM), where M(X,Y) is the query point:

position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))

It is 0 on the line, and +1 on one side, -1 on the other side.

straight line between two points

Edit: I originally misunderstood the question, it seems.

As far as validating the path: I think it would be easier just to have a function that determines whether a point is valid than calculating all of the values beforehand. Something like:

function getValidatorForPoints(x1, y1, x2, y2) {
    var slope = (y2 - y1) / (x2 - x1);
    return function (x, y) {
        return (y - y1) == slope * (x - x1);
    }
}

Then, given two points, you could do this:

var isValid = getValidatorForPoints(x1, y1, x2, y2);
var x = getX(), y = getY();// getX and getY get the user's new point.
if (isValid(x, y)) {
    // Draw
}

This approach also gives you some flexibility—you could always modify the function to be less precise to accommodate people who don't quite draw a straight line but are tolerably close.

Precision:
As mentioned in my comment, you can change the way the function behaves to make it less exacting. I think a good way to do this is as follows:

Right now, we are using the formula (y - y1) == slope * (x - x1). This is the same as (slope * (x - x1)) - (y - y1) == 0. We can change the zero to some positive number to make it accept points "near" the valid line as so:

Math.abs((slope * (x - x1)) - (y - y1)) <= n

Here n changes how close the point has to be to the line in order to count.

I'm pretty sure this works as advertised and helps account for people's drawing the line a little crooked, but somebody should double check my math.

Shortest distance between a point and a line segment

Eli, the code you've settled on is incorrect. A point near the line on which the segment lies but far off one end of the segment would be incorrectly judged near the segment. Update: The incorrect answer mentioned is no longer the accepted one.

Here's some correct code, in C++. It presumes a class 2D-vector class vec2 {float x,y;}, essentially, with operators to add, subract, scale, etc, and a distance and dot product function (i.e. x1 x2 + y1 y2).

float minimum_distance(vec2 v, vec2 w, vec2 p) {
  // Return minimum distance between line segment vw and point p
  const float l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
  if (l2 == 0.0) return distance(p, v);   // v == w case
  // Consider the line extending the segment, parameterized as v + t (w - v).
  // We find projection of point p onto the line. 
  // It falls where t = [(p-v) . (w-v)] / |w-v|^2
  // We clamp t from [0,1] to handle points outside the segment vw.
  const float t = max(0, min(1, dot(p - v, w - v) / l2));
  const vec2 projection = v + t * (w - v);  // Projection falls on the segment
  return distance(p, projection);
}

EDIT: I needed a Javascript implementation, so here it is, with no dependencies (or comments, but it's a direct port of the above). Points are represented as objects with x and y attributes.

function sqr(x) { return x * x }
function dist2(v, w) { return sqr(v.x - w.x) + sqr(v.y - w.y) }
function distToSegmentSquared(p, v, w) {
  var l2 = dist2(v, w);
  if (l2 == 0) return dist2(p, v);
  var t = ((p.x - v.x) * (w.x - v.x) + (p.y - v.y) * (w.y - v.y)) / l2;
  t = Math.max(0, Math.min(1, t));
  return dist2(p, { x: v.x + t * (w.x - v.x),
                    y: v.y + t * (w.y - v.y) });
}
function distToSegment(p, v, w) { return Math.sqrt(distToSegmentSquared(p, v, w)); }

EDIT 2: I needed a Java version, but more important, I needed it in 3d instead of 2d.

float dist_to_segment_squared(float px, float py, float pz, float lx1, float ly1, float lz1, float lx2, float ly2, float lz2) {
  float line_dist = dist_sq(lx1, ly1, lz1, lx2, ly2, lz2);
  if (line_dist == 0) return dist_sq(px, py, pz, lx1, ly1, lz1);
  float t = ((px - lx1) * (lx2 - lx1) + (py - ly1) * (ly2 - ly1) + (pz - lz1) * (lz2 - lz1)) / line_dist;
  t = constrain(t, 0, 1);
  return dist_sq(px, py, pz, lx1 + t * (lx2 - lx1), ly1 + t * (ly2 - ly1), lz1 + t * (lz2 - lz1));
}

Here, in the function parameters, <px,py,pz> is the point in question and the line segment has the endpoints <lx1,ly1,lz1> and <lx2,ly2,lz2>. The function dist_sq (which is assumed to exist) finds the square of the distance between two points.

---

Related Topics