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 ?

I dont know whether it is convex or concave, basically iam forming a polygon with a set of vertices, that represent the latitudes and longitudes of a particular geographic place. And i want to find whether a geometric point (vertex) is inside a polygon. — shasi kanth, Feb 21 '11 at 10:55
There's an excellent explanation of how to do this in the answer to http://stackoverflow.com/questions/217578/point-in-polygon-aka-hit-test with code that could easily be ported to PHP — Mark Baker, Feb 21 '11 at 11:06

score 58 · Accepted Answer · edited Aug 24 '12 at 18:10

58

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.

edited Aug 24 '12 at 18:10

Community

1
1

answered Feb 21 '11 at 11:09

Thariama

50,002
13
138
166

4

+1 - And visit http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html for an explanation of how it works – Mark Baker Feb 21 '11 at 11:17
Thanks these links helped me out. – shasi kanth Feb 21 '11 at 11:20
7

Also found another working example here: http://www.assemblysys.com/dataServices/php_pointinpolygon.php – shasi kanth Feb 21 '11 at 14:25
12

This algorithm is quite good for cases when polygon's Xs and Ys are all positive but since question is about latitude and longitude: is it just me or this algorithm will fail spectacularly if polygon is crossed by greenwich meridian, i.e. one point has positive longitude like 1.000000 and the next one has negative like -1.000000? Possible solution: offset all longitudes with +180 (this is not moving east to China where math operations are cheaper but to make all longitudes positive :-) ) – Ognyan Dec 28 '11 at 19:00
Does this algorythm assume that the polygon is **not** self-closing? That is to say that it's final vertex is the line between it's penultimate point and it's last point. And **not** the line between the last point and it's first point as is the case with a self-closing polygon. _Note: I am using this to work with SVGs_ – Martin Joiner Oct 04 '13 at 15:45
1

@Ogre_BGR is right, have posted a solid proof version here -> http://stackoverflow.com/a/18190354/1407478 – davidkonrad Apr 15 '15 at 21:43
@SumithHarshan: Glad to have been able to help :) – Thariama Feb 26 '16 at 09:54
One question, are the vertices_x latitudes or longitudes? I've been trying to make it work (https://pastebin.com/M0aHvaK9, I commented and show the polygon/point) but always gives me "not in polygon". – Miguel Jun 29 '17 at 09:58
@Miguel: vertices_x are longitude values – Thariama Jun 30 '17 at 06:51
Hi can you please check https://stackoverflow.com/questions/61302366/point-in-polygon-algorithm-giving-wrong-results-for-negative-points – Apr 19 '20 at 16:55

score 15 · Answer 2 · answered May 15 '12 at 00:11

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;
}
?>

This function works pretty good, but it will not work if the test point is equal to one of the vertices. This is a simple test case to add. Also, you have to take care that your polygons do not cross the international dateline. If you need to do this, you must decompose the polygon into two polygons on either side. — Jake, May 19 '12 at 03:12
What specific typos did you correct? As far as I can see all you have done is moved the `-1` from outside the `is_in_polygon()` function to inline. — Martin Joiner, Oct 04 '13 at 15:41
As originally provided the code didn't parse correctly. It seems to have been fixed since (edited after my answer). See here: http://stackoverflow.com/posts/5065219/revisions — amh15, Dec 03 '14 at 22:44

score 7 · Answer 3 · answered Mar 14 '19 at 09:22

Above solution is not working as i expect, instead of using the above solution you can prefer below solutions

With PHP

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 lat lng sits exactly on a vertex
    if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {
        return "vertex";
    }

    // Check if the lat lng 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 lat lng 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]);
}
// Function to check lat lng
function check(){
    $points = array("22.367582 70.711816", "21.43567582 72.5811816","22.367582117085913 70.71181669186944","22.275334996986643 70.88614147123701","22.36934302329968 70.77627818998701"); // Array of latlng which you want to find
    $polygon = array(
        "22.367582117085913 70.71181669186944",
        "22.225161442616514 70.65582486840117",
        "22.20736264867434 70.83229276390898",
        "22.18701840565626 70.9867880031668",
        "22.22452581029355 71.0918447658621",
        "22.382709129816103 70.98884793969023",
        "22.40112042636022 70.94078275414336",
        "22.411912121843205 70.7849142238699",
        "22.367582117085913 70.71181669186944"
    );
    // The last lat lng must be the same as the first one's, to "close the loop"
    foreach($points as $key => $point) {
        echo "(Lat Lng) " . ($key+1) . " ($point): " . $this->pointInPolygon($point, $polygon) . "<br>";
    }
}

With MySql

CREATE TABLE `TestPoly` (
   `id` int(11) NOT NULL,
   `name` varchar(255) NOT NULL,
   `pol` polygon NOT NULL
 )

SET @g = 'POLYGON((22.367582117085913 70.71181669186944, 22.225161442616514 70.65582486840117, 22.20736264867434 70.83229276390898, 22.18701840565626 70.9867880031668, 22.22452581029355 71.0918447658621, 22.382709129816103 70.98884793969023, 22.40112042636022 70.94078275414336, 22.411912121843205 70.7849142238699, 22.367582117085913 70.71181669186944))';
INSERT INTO TestPoly (pol) VALUES (ST_GeomFromText(@g))

set @p = GeomFromText('POINT(22.4053386588057 70.86240663480157)');
select * FROM TestPoly where ST_Contains(pol, @p);

Here is the details : https://stackoverflow.com/questions/61302366/point-in-polygon-algorithm-giving-wrong-results-for-negative-points — , Apr 20 '20 at 11:28
you can check the below URL with your inputs. I agree google Maps is showing the right polygon. For the solution, you have to use the MySQL solution which I provide. It will work completely okay. https://www.keene.edu/campus/maps/tool/ — Renish Gotecha, Apr 20 '20 at 14:49
I have tried MySql solution as well but it is not working. You can check it from your end as well. — , Apr 20 '20 at 16:24
This code is taken from https://assemblysys.com/php-point-in-polygon-algorithm/. You should have added the credits. — cootje, Dec 27 '22 at 16:16

score 5 · Answer 4 · answered Oct 04 '13 at 16:09

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.

Hi can you please check this - https://stackoverflow.com/questions/61302366/point-in-polygon-algorithm-giving-wrong-results-for-negative-points — , Apr 19 '20 at 16:55

score 5 · Answer 5 · edited Sep 13 '20 at 19:30

I put Thailand polygon into MySQL. And compared accepted answer function with built-in function in MySQL 8.

CREATE TABLE `polygons` (
    `id` INT(11) NOT NULL AUTO_INCREMENT,
    `polygon` POLYGON NOT NULL,
    `country` VARCHAR(50) NULL DEFAULT NULL,
    PRIMARY KEY (`id`),
    SPATIAL INDEX `polygon` (`polygon`)
)
COLLATE='utf8mb4_0900_ai_ci'
ENGINE=InnoDB
AUTO_INCREMENT=652
;

INSERT INTO `polygons` (`country`, `polygon`) VALUES ('Thailand', ST_GEOMFROMTEXT('POLYGON((102.1728516 6.1842462,101.6894531 5.7253114,101.1401367 5.6815837,101.1181641 6.2497765,100.1074219 6.4899833,96.3281250 6.4244835,96.1083984 9.8822755,98.7670898 10.1419317,99.5800781 11.8243415,98.2177734 15.1569737,98.9868164 16.3201395,97.4267578 18.4587681,98.1079102 19.7253422,99.0087891 19.7460242,100.2612305 20.2828087,100.4809570 19.4769502,101.2060547 19.4147924,100.8544922 17.4135461,102.0849609 17.9996316,102.8320313 17.7696122,103.3593750 18.3545255,104.7875977 17.4554726,104.6337891 16.4676947,105.5126953 15.6018749,105.2270508 14.3069695,102.9858398 14.2643831,102.3486328 13.5819209,103.0297852 11.0059045,103.6669922 8.5592939,102.1728516 6.1842462))'));

Here is polygon with dots above - RED is 1st, BLUE - last:

I draw some dots outside and inside Thailand Polygon on the map using https://www.gpsvisualizer.com/draw/ and made screen to visualize all the dots.

I gave dots as coordinates for PHP function + compared results with MySQL function using query:

SELECT TRUE FROM `polygons` WHERE `polygons`.`country` = 'Thailand' AND ST_CONTAINS(`polygons`.`polygon`, POINT($long, $lat));

The result:

MySQL always gave me right answer about all the dots.
PHP function has wrong answers
- RED - if I delete closing dot of polygon
- ORANGE - not deleting last dot which is same as opening, and same like in MYSQL polygon.
- WHITE dots had same results PHP / MySQL and are right answers.

I tried to change polygon, but php function always making mistakes about those dots, means somewhere there is bug which I could not find.

Update 1

Found solution assemblysys.com/php-point-in-polygon-algorithm - this algo works same as MySQL algo!

Update 2

Compared PHP speed vs MySQL (I was thinking that PHP should be much more faster), but no. Compared 47k dots.

18-06-2020 21:34:45 - PHP Speed Check Start
18-06-2020 21:34:51 - FIN! PHP Check. NOT = 41085 / IN = 5512
18-06-2020 21:34:51 - MYSQL Speed Check Start
18-06-2020 21:34:58 - FIN! MYSQL Check. NOT = 41085 / IN = 5512

Founded solution https://assemblysys.com/php-point-in-polygon-algorithm/ - this algo works same as Mysql algo! — wtfowned, Jun 18 '20 at 17:28

score 3 · Answer 6 · answered Feb 21 '11 at 11:00

3

Here's a possible algorithm.

Define a new coordinate system with your point of interest at the center.
In your new coordinate system, convert all of your polygon vertices into polar coordinates.
Traverse the polygon, keeping track of the net change in angle, ∆θ. Always use the smallest possible value for each change in angle.
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.
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. :)

answered Feb 21 '11 at 11:00

awm

6,526
25
24

Sorry, but i could not understand the scenario... it looks very complex. Any example code or link ? – shasi kanth Feb 21 '11 at 11:02
1

There's probably a library of complicated math functions somewhere. Perhaps someone else knows where it is (I don't). My answer is only useful if you're going to write the code yourself. :) – awm Feb 21 '11 at 11:07

score 3 · Answer 7 · answered Apr 16 '20 at 07:58

Updated code so i will be easier to use with google maps: It accept array like:

Array
(
    [0] => stdClass Object
        (
            [lat] => 43.685927
            [lng] => -79.745829
        )

    [1] => stdClass Object
        (
            [lat] => 43.686004
            [lng] => -79.745954
        )

    [2] => stdClass Object
        (
            [lat] => 43.686429
            [lng] => -79.746642
        )

So it will be easier to use with google maps:

function is_in_polygon2($longitude_x, $latitude_y,$polygon)
{
  $i = $j = $c = 0;
  $points_polygon = count($polygon)-1;
  for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
    if ( (($polygon[$i]->lat  >  $latitude_y != ($polygon[$j]->lat > $latitude_y)) &&
     ($longitude_x < ($polygon[$j]->lng - $polygon[$i]->lng) * ($latitude_y - $polygon[$i]->lat) / ($polygon[$j]->lat - $polygon[$i]->lat) + $polygon[$i]->lng) ) )
       $c = !$c;
  }
  return $c;
}

score 2 · Answer 8 · edited Jun 20 '20 at 09:12

I have created code in php codeigniter, in my controller i have create two functions like below

public function checkLatLng(){
    $vertices_y = array(22.774,22.174,22.466,22.666,22.966,22.321);    // x-coordinates of the vertices of the polygon (LATITUDES)
    $vertices_x = array(70.190,70.090,77.118,77.618,77.418,77.757); // y-coordinates of the vertices of the polygon (LONGITUDES)
    $points_polygon = count($vertices_x)-1; 
    $longitude_x = $this->input->get("longitude");  // Your Longitude
    $latitude_y = $this->input->get("latitude");    // Your Latitude
    if ($this->is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
        echo "Is in polygon!";
    }
    else
        echo "Is not in polygon";
}

Another function for check the lat-lng is below

public 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;
}

For your testing purpose i passed below things

latitude=22.808059

longitude=77.522014

My Polygon

Find Point in polygon PHP

8 Answers8

Update 1

Update 2

Linked