How to Determine a Point Is Between Two Other Points on a Line Segment

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

Determine if a point is between 2 other points on a line

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.

Test if a point is approximately on a line segment formed by two other points

Here is the final javascript function I am now using.

The first part is using the distance formula as explained in Ashley Tharp's answer, we first test if c is inside a pre-defined distance (tolerance) of a line going through a and b.

The second part is taken from Cyrille Ka' answer from a similar question.

Then, 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.

// a and b are vertices of the segment AB and c is the tested point (here from a mouseclick event (e))
var a={}, b={}, c={};
a.x = 100;
a.y = 100;
b.x = 200;
b.y = 200;
c.x = e.screenX
c.y = e.screeny

console.log(isBetween(a, b, c, 5));

function isBetween(a, b, c, tolerance) {

    //test if the point c is inside a pre-defined distance (tolerance) from the line
    var distance = Math.abs((c.y - b.y)*a.x - (c.x - b.x)*a.y + c.x*b.y - c.y*b.x) / Math.sqrt(Math.pow((c.y-b.y),2) + Math.pow((c.x-b.x),2));
    if (distance > tolerance) { return false; }

    //test if the point c is between a and b
    var dotproduct = (c.x - a.x) * (b.x - a.x) + (c.y - a.y)*(b.y - a.y);
    if (dotproduct < 0) { return false; }

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

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;

Find if point lies on line segment

If the point is on the line then:

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1) = (z - z1) / (z2 - z1)

Calculate all three values, and if they are the same (to some degree of tolerance), your point is on the line.

To test if the point is in the segment, not just on the line, you can check that

x1 < x < x2, assuming x1 < x2, or
y1 < y < y2, assuming y1 < y2, or
z1 < z < z2, assuming z1 < z2

How can I determine if a point is on a line between two other points in 3d in Lua (or other language)?

If you know that the points lie on a single line, you may just calculate a dot product, and if 0 ≤ 〈AB, AP〉 ≤ 〈AB, AB〉, then P is between A and B. But note that if P is not exactly on the line, this method may give strange results. But it should be the fastest.

You may also want to calculate 2 values, distance from P to AB and (orthogonal) projection of AP onto AB. The latter is AP_AB = 〈AP, AB〉 / 〈AB, AB〉 (in AB units, so that if AP and AB are collinear, AP = AB * AP_AB), and the former is ρ(P, AB) = ρ(AP, AB * AP_AB) = |AP - AB * AP_AB|. So, if the ρ(P, AB) is small, you decide that if 0 ≤ AP_AB ≤ 1, then P is between A and B

finding point on a line which is equidistant from 2 other points

TL;DR. The solution is at the bottom.

Alright, so let's say these are our parameters:

x₀ and x₁, that describe the line.
a and b, the two points.

Where

x₀ = [x₀, y₀, z₀]
x₁ = [x₁, y₁, z₁]
a = [x_a, y_a, z_a]
b = [x_b, y_b, z_b]
δ = [δ_x, δ_y, δ_z] = (x₁ - x₀)

Then our description of the line can be seen as a parametric function:

l(λ) = x₀ + λ*(x₁ - x₀)

So we are trying to find a value for λ that satisfies the following equation:

(l(λ) - a)² = (l(λ) - b)²

(Here I'm cheating with notation a bit, so x² = x.x)

So expanding everything we get:

(λx₁ + (1 - λ)x₀ - x_a)² +
(λy₁ + (1 - λ)y₀ - y_a)² +
(λz₁ + (1 - λ)z₀ - z_a)² =
(λx₁ + (1 - λ)x₀ - x_b)² +
(λy₁ + (1 - λ)y₀ - y_b)² +
(λz₁ + (1 - λ)z₀ - z_b)²

Simplifying, we get:

(λδ_x + x₀ - x_a)² +
(λδ_y + y₀ - y_a)² +
(λδ_z + z₀ - z_a)² =
(λδ_x + x₀ - x_b)² +
(λδ_y + y₀ - y_b)² +
(λδ_z + z₀ - z_b)²

Expanding the brackets and cancelling, we get:

-2δ_xx_aλ + (x₀ - x_a)² +
-2δ_yy_aλ + (y₀ - y_a)² +
-2δ_zz_aλ + (z₀ - z_a)² =
-2δ_xx_bλ + (x₀ - x_b)² +
-2δ_yy_bλ + (y₀ - y_b)² +
-2δ_zz_bλ + (z₀ - z_b)²

Which we can simplify further into some nice neat vector operations:

2λδ.(x_b - x_a) =
(x₀ - x_b)² -
(x₀ - x_a)²

Which is pretty simple to rearrange to get a linear equation in λ with one unique solution.