PHP point-in-polygon algorithm

The point-in-polygon algorithm allows you to programmatically check if a particular point is inside a polygon or outside of it. A common way to tackle the problem is to count how many times a line drawn from the point (in any direction) intersects with the polygon boundary. If the line and the polygon intersect an even number of times (or not at all), then the point is outside. If they intersect an odd number of times, the point is inside. It is true even for complex forms that have a lot of coordinates and thus create a very precise boundary.

Let’s see a sample image before we get to the code.

Here, the lines drawn from point 1 intersect twice or not at all, because it is outside.

Point 2 is inside and thus the lines drawn from it intersect once or three times.

Even in special cases, such as point 3, we see that this method works: the line intersects twice and the point is therefore outside.

I use this approach in the PHP code below, which returns one of these 4 possible values:

  • inside if the point is inside the polygon.
  • outside if, you guessed it, the point is outside of the polygon.
  • vertex if the point sits exactly on a vertex AND $pointOnVertex = true (line 2)
  • boundary if the point sits on the boundary. If $pointOnVertex = false, then boundary is also returned if the point is on a vertex.
<?php
/*
Description: The point-in-polygon algorithm allows you to check if a point is
inside a polygon or outside of it.
Author: Michaël Niessen (2009)
Website: http://AssemblySys.com

If you find this script useful, you can show your
appreciation by getting Michaël a cup of coffee ;)
https://ko-fi.com/assemblysys

As long as this notice (including author name and details) is included and
UNALTERED, this code can be used and distributed freely.
*/

class pointLocation {
    var $pointOnVertex = true; // Check if the point sits exactly on one of the vertices?

    function pointLocation() {
    }

    function pointInPolygon($point, $polygon, $pointOnVertex = true) {
        $this->pointOnVertex = $pointOnVertex;

        // Transform string coordinates into arrays with x and y values
        $point = $this->pointStringToCoordinates($point);
        $vertices = array(); 
        foreach ($polygon as $vertex) {
            $vertices[] = $this->pointStringToCoordinates($vertex); 
        }

        // Check if the point sits exactly on a vertex
        if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {
            return "vertex";
        }

        // Check if the point is inside the polygon or on the boundary
        $intersections = 0; 
        $vertices_count = count($vertices);

        for ($i=1; $i < $vertices_count; $i++) {
            $vertex1 = $vertices[$i-1]; 
            $vertex2 = $vertices[$i];
            if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) { // Check if point is on an horizontal polygon boundary
                return "boundary";
            }
            if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) { 
                $xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x']; 
                if ($xinters == $point['x']) { // Check if point is on the polygon boundary (other than horizontal)
                    return "boundary";
                }
                if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
                    $intersections++; 
                }
            } 
        } 
        // If the number of edges we passed through is odd, then it's in the polygon. 
        if ($intersections % 2 != 0) {
            return "inside";
        } else {
            return "outside";
        }
    }

    function pointOnVertex($point, $vertices) {
        foreach($vertices as $vertex) {
            if ($point == $vertex) {
                return true;
            }
        }

    }

    function pointStringToCoordinates($pointString) {
        $coordinates = explode(" ", $pointString);
        return array("x" => $coordinates[0], "y" => $coordinates[1]);
    }

}
?>

Using the point-in-polygon PHP code

Set the point(s) value(s) and an array containing your polygon vertices (in the form “Xcoordinate Ycoordinate”), then call the pointInPolygon function. The first and last polygon coordinates must be identical, to “close the loop”.

As you can see in the following example, it is easy to check multiple points at once. The code also works with negative coordinates, for the polygon as well as for the points to check.

<?php
$pointLocation = new pointLocation();
$points = array("50 70","70 40","-20 30","100 10","-10 -10","40 -20","110 -20");
$polygon = array("-50 30","50 70","100 50","80 10","110 -10","110 -30","-20 -50","-30 -40","10 -10","-10 10","-30 -20","-50 30");
// The last point's coordinates must be the same as the first one's, to "close the loop"
foreach($points as $key => $point) {
    echo "point " . ($key+1) . " ($point): " . $pointLocation->pointInPolygon($point, $polygon) . "<br>";
}
?>

This will output:

point 1 (50 70): vertex
point 2 (70 40): inside
point 3 (-20 30): inside
point 4 (100 10): outside
point 5 (-10 -10): outside
point 6 (40 -20): inside
point 7 (110 -20): boundary

6 thoughts on “PHP point-in-polygon algorithm

  1. Paco

    Hi ! Neat ! Thanks for that … I will certainly get you a coffee after my testing ! 😉

    I will test it, but I just wanted to make sure your Point-in-Polygon class was programmed with float (decimals) numbers in mind.
    (ie. GPS coordinates on a map)

    Reply
    1. Michael Post author

      Thanks Paco!
      Yes, no problem with decimals, as I wrote it initially for precise GPS coordinates. [This was mentioned in comments on our previous website, but we are starting again with a clean slate 😉 ]
      Feel free to let me know if you have any questions and I’ll do my best to help you,
      Michael


      If you find this content useful, you can buy me a cup of coffee ;)
      https://ko-fi.com/assemblysys

      Reply
  2. Fernando

    Thanks a lot. You save my life at its moment.
    The algorithm is the best. I will try improvement it, if it is possible. And I will contact you If I achieve.

    Again, thank you. Have a good day.

    Reply
  3. Denny Chasteen

    Michael,

    This script has helped me a lot! So far it has been perfect and matches 100% with the function results from turf.js. The difference being, that now I can do the logic on the servers side with PHP rather than on the client side with JavaScript. Awesome!!! Very helpful.

    I think the first coordinate set in a WKT or GEOJSON string is the outer or main polygon. And any subsequent coordinate sets are all the holes? That being the case, I think I just have to go through all the hole coordinate sets and if a point is inside any one of the holes, then it is not inside the
    polygon.

    Thanks.
    Denny

    Reply
    1. Michael Post author

      Thank you very much for your kind comment! I’m very happy to know it helps you.
      That’s right, with a hole you have to run the script for both the outer polygon and hole. If it’s inside the outer polygon, but not the hole, it’s inside the filled part. If the script returns inside for both, then it’s inside the hole.
      In that case, you could of course run the script for the hole first. If it’s inside the hole, no need to run it again for the rest of the polygon.
      Finally, thank you so much for your donation! Very much appreciated 🙂


      If you find this content useful, you can buy me a cup of coffee ;)
      https://ko-fi.com/assemblysys

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.