Find Point in polygon PHP

Question

i have a typical question with the Geometric datatype of mysql, polygon.

I have the polygon data, in the form of an array of latitudes and longitudes, ex:

[["x":37.628134,  "y":-77.458334],
["x":37.629867,   "y":-77.449021],
["x":37.62324,    "y":-77.445416],
["x":37.622424,   "y":-77.457819]]

And i have a point (Vertex) with coordinates of latitude and longitude, ex:

$location = new vertex($_GET["longitude"], $_GET["latitude"]);

Now i want to find whether this vertex (point) is inside the polygon. How can i do this in php ?

Answer 1

If your polygons are self-closing, that is to say that it's final vertex is the line between it's last point and it's first point then you need to add a variable and a condition to your loop to deal with the final vertex. You also need to pass the number of vertices as being equal to the number of points.

Here is the accepted answer modified to deal with self-closing polygons:

$vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424);    // x-coordinates of the vertices of the polygon
$vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon
$points_polygon = count($vertices_x);  // number vertices = number of points in a self-closing polygon
$longitude_x = $_GET["longitude"];  // x-coordinate of the point to test
$latitude_y = $_GET["latitude"];    // y-coordinate of the point to test

if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
  echo "Is in polygon!";
}
else echo "Is not in polygon";


function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)
{
  $i = $j = $c = $point = 0;
  for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
    $point = $i;
    if( $point == $points_polygon )
      $point = 0;
    if ( (($vertices_y[$point]  >  $latitude_y != ($vertices_y[$j] > $latitude_y)) &&
     ($longitude_x < ($vertices_x[$j] - $vertices_x[$point]) * ($latitude_y - $vertices_y[$point]) / ($vertices_y[$j] - $vertices_y[$point]) + $vertices_x[$point]) ) )
       $c = !$c;
  }
  return $c;
}

Thank you! I found this page and it's accepted answer very helpful and I am proud to offer this variation.

Answer 2

The popular answer above contains typos. Elsewhere, this code has been cleaned up. The corrected code is as follows:

<?php
/**
  From: http://www.daniweb.com/web-development/php/threads/366489
  Also see http://en.wikipedia.org/wiki/Point_in_polygon
*/
$vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon
$vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon
$points_polygon = count($vertices_x); // number vertices
$longitude_x = $_GET["longitude"]; // x-coordinate of the point to test
$latitude_y = $_GET["latitude"]; // y-coordinate of the point to test
//// For testing.  This point lies inside the test polygon.
// $longitude_x = 37.62850;
// $latitude_y = -77.4499;

if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
  echo "Is in polygon!";
}
else echo "Is not in polygon";


function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)
{
  $i = $j = $c = 0;
  for ($i = 0, $j = $points_polygon-1 ; $i < $points_polygon; $j = $i++) {
    if ( (($vertices_y[$i] > $latitude_y != ($vertices_y[$j] > $latitude_y)) &&
    ($longitude_x < ($vertices_x[$j] - $vertices_x[$i]) * ($latitude_y - $vertices_y[$i]) / ($vertices_y[$j] - $vertices_y[$i]) + $vertices_x[$i]) ) ) 
        $c = !$c;
  }
  return $c;
}
?>

Answer 3

Here's a possible algorithm.

1. Define a new coordinate system with your point of interest at the center.
2. In your new coordinate system, convert all of your polygon vertices into polar coordinates.
3. Traverse the polygon, keeping track of the net change in angle, ∆θ. Always use the smallest possible value for each change in angle.
4. If, once you've traversed the polygon, your total ∆θ is 0, then you're outside the polygon. On the other hand, if it's is ±2π, then you're inside.
5. If, by chance ∆θ>2π or ∆θ<-2π, that means you have a polygon that doubles back on itself.

Writing the code is left as an exercise. :)

Answer 4

This is a function i converted from another language into PHP:

$vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424);    // x-coordinates of the vertices of the polygon
$vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon
$points_polygon = count($vertices_x) - 1;  // number vertices - zero-based array
$longitude_x = $_GET["longitude"];  // x-coordinate of the point to test
$latitude_y = $_GET["latitude"];    // y-coordinate of the point to test

if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
  echo "Is in polygon!";
}
else echo "Is not in polygon";


function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)
{
  $i = $j = $c = 0;
  for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
    if ( (($vertices_y[$i]  >  $latitude_y != ($vertices_y[$j] > $latitude_y)) &&
     ($longitude_x < ($vertices_x[$j] - $vertices_x[$i]) * ($latitude_y - $vertices_y[$i]) / ($vertices_y[$j] - $vertices_y[$i]) + $vertices_x[$i]) ) )
       $c = !$c;
  }
  return $c;
}

Additional: For more functions i advise you to use the polygon.php class available here. Create the Class using your vertices and call the function isInside with your testpoint as input to have another function solving your problem.