How to check if a coordinate (latitude and longitude) is in between two other coordinates in PHP?

Question

Let's say I have two coordinates a and b that both consist of a latitude and a longitude. How can I check if a third coordinate c is in between coordinate a and b using PHP? With other words: When I connect a and b with a line, how can I tell if coordinate c is exactly on that line?

I already found an answer solving this for simple X and Y coordinates using the cross product and dot product with Python, see here: https://stackoverflow.com/a/328122

But it seems like it's more complicated using coordinates with a lot of decimal places in PHP like its the case with latitudes and longitudes due to the limited precision for floating point numbers in PHP.

So here is a basic example that does not work for the above solution:

// Copied from the Python solution
public function isBetweenPoints($aLat, $aLng, $bLat, $bLng, $cLat, $cLng) {

    $crossProduct = ($cLat - $aLat) * ($bLng - $aLng) - ($cLng - $aLng) * ($bLat - $aLat);
    if (abs($crossProduct) < PHP_FLOAT_EPSILON) {
        return false;
    }

    $dotProduct = ($cLng - $aLng) * ($bLng - $aLng) + ($cLat - $aLat)*($bLat - $aLat);
    if ($dotProduct < 0) {
        return false;
    }

    $squaredLength = ($bLng - $aLng)*($bLng - $aLng) + ($bLat - $aLat)*($bLat - $aLat);

    return !($dotProduct > $squaredLength);
}

$aLat = 48.14723956724038;
$aLng = 11.514418017613934;
$bLat = 48.14722882951992;
$bLng = 11.51386548255687;
$cLat = 48.147645056105120;
$cLng = 11.514326333999636;

// Returns true, even if the point c is not between a and b
isBetweenPoints($aLat, $aLng, $bLat, $bLng, $cLat, $cLng);

To better understand that isBetweenPoints in the above example should return false, here is a corresponding image on which $latLngA and $latLngB is represented by the green line at the bottom and $latLngC by the marker at the top:

You only want the pseudofunction from the reference in php? isBetween(a, b, c): crossproduct = ($c.y - a.y) * (b.x - a.x) - (c.x - a.x) * (b.y - a.y) — Alexander Dobernig, Jan 07 '21 at 13:17
is LatLng really a class? there is no class definition in the code example? — Alexander Dobernig, Jan 07 '21 at 13:18
@AlexanderDobernig Sorry, `LatLng` was a class of my code that would be too complicated to share in the example. I simplified the example to make it more clear. And yes, in fact I only want the function of the reference in PHP. But I think it's more complicated in PHP due to the limited precision for floating point numbers. :/ — Ferdinand Frank, Jan 07 '21 at 14:36
I thing your concern regarding the precision is not relevant if you really want to stay in real world land like the google maps picture illustrates. Because the precision is 1.1E-16 so if 1 would be 111km (1 degree longitude) the precision would be enough for **0,000000012321 MILLIMETRES** And your GPS will be precise to about 10 metres = 10000 mm ## so a precision of 5 digits would be sufficient. so you have another 11!! left ;-P ### Think about this in your code! asking for Epsilon will not provide a useful result - if you want to tell the user if he is "ON TRACK" — Alexander Dobernig, Jan 07 '21 at 15:13

Alexander Dobernig · Accepted Answer · 2021-01-07T16:09:39.777

I think only your first condition was wrong it must be > not <

According to the reference python if it is LARGER THAN epsilon then its false.

   <?// Copied from the Python solution
 function isBetweenPoints($aLat, $aLng, $bLat, $bLng, $cLat, $cLng) {

    $crossProduct = ($cLat - $aLat) * ($bLng - $aLng) - ($cLng - $aLng) * ($bLat - $aLat);
       echo "cross_product: ". $crossProduct; //debug 
       if (abs($crossProduct) > PHP_FLOAT_EPSILON) {   // i would rethink epsilon as you will never get TRUE ;-) 
       return false;
    }

    $dotProduct = ($cLng - $aLng) * ($bLng - $aLng) + ($cLat - $aLat)*($bLat - $aLat);
    echo "<br>dotProduct: ". $dotProduct; //debug
    if ($dotProduct < 0) {
        return false;
    }

    $squaredLength = ($bLng - $aLng)*($bLng - $aLng) + ($bLat - $aLat)*($bLat - $aLat);
    echo "<br>SquaredLength: " . $squaredLength; //debug
    return !($dotProduct > $squaredLength);
}

$aLat = 1;
$aLng = 1;

$bLat = 3;
$bLng = 3;

$cLat = 2;
$cLng = 2;

//will give true

if (isBetweenPoints($aLat, $aLng, $bLat, $bLng, $cLat, $cLng) ==TRUE)
{echo "<br>Point IS between the other points<p>";}
else
{echo "<br>Point IS NOT between the other points<p>";}
  

$aLat = 1;
$aLng = 1;

$bLat = 3;
$bLng = 3;

$cLat = 2;
$cLng = 2.1;

//will give false

echo"<br>";

if (isBetweenPoints($aLat, $aLng, $bLat, $bLng, $cLat, $cLng) ==TRUE)
{echo "<br>POINT IS between the other points";}
else
{echo "<br>POINT IS NOT between the other points";}

?>

Oh, I absolutely missed that! I set the epsilon to `0.00000001` and now all my tests pass. Thank you very much! — Ferdinand Frank, Jan 07 '21 at 16:03
I have changed the code to be more intuitive with very simple number examples - to show that it works ### pls check your epsilon with real live values of the allowed tolerance.. — Alexander Dobernig, Jan 07 '21 at 16:11

apokryfos · Answer 2 · 2021-01-07T16:52:01.343

This problem boils down to given two points (which uniquely define a line) how to determine if a third one is on the same line which is (a) determine if the points are colinear and (b) determine if point c has x and y coordinates between the x and y coordinates of the other two points.

Two points define the line:

(y - y₁) = ^{(y₂ - y₁)}⁄_(x₂-x₁)(x-x₁)

A point is co-linear with the two points if the equation holds when you substitute this point's x and y so for example lets assume each point is an object with properties x and y:

function pointOnLineSegment($point1, $point2, $point3) {
   return abs(($point3->y-$point1->y) - (($point2->y - $point1->y)/($point2->x - $point1->x)*($point3->x - $point1->x))) < 0.001 
        && $point3->x > $point1->x 
        && $point3->x < $point2->x 
        && $point3->y > $point1->y
        && $point3->y < $point2->y; 

}

In your case, x and y could be longitude and latitude (or the reverse it really doesn't matter).

I use 0.001 here but the choice really depends on the precision you have PHP_EPSILON is definitely too low to rely on.

Now of course this only works on flat geometries so on a map the projection needs to correctly project points on the same geodesic (the Mercator projection does this I think)

Thanks for your solution, but it didn't really work as the function also returns `true` when a point within the "bound" of `$point1` and `$point2` is specified. As an example assume `$point1 (y=5, x=5); $point2 (y=10, x=10); $point3 (y=7, x=8)`. Point 3 is not on the line between point 1 and 2, but in their "bound". The function still returns true. — Ferdinand Frank, Jan 07 '21 at 16:06
@FerdinandFrank It's working for me [here](http://sandbox.onlinephpfunctions.com/code/cdd16c59f62d529fbd5f32f636cfcc5d01584f5b). it's not correct to say it only works with the bound as the colinear check happens at the very first line of the function — apokryfos, Jan 07 '21 at 16:15
Sorry, you got me wrong here. It does work when a point is on the line. But additionally it also returns true when the point is just in bounds. When you flip the `y` and `x` coordinates, you can see it: http://sandbox.onlinephpfunctions.com/code/b61eb8f4a46c34a36766f6a99c8cd4369f5e890e — Ferdinand Frank, Jan 07 '21 at 16:43

How to check if a coordinate (latitude and longitude) is in between two other coordinates in PHP?

2 Answers2