# 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.

## 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.

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

## 113 thoughts on “PHP point-in-polygon algorithm”

1. MrDog

Very nice and saved me a lot of work. But one query – you say the last point in the polygon must be the same as the first one to close the loop which I understand – but the first one is (-50,30) and the last one is (-50,-30) which are not the same – which implies to me that the last value is not really needed?

1. Michael Post author

Thanks for pointing that out!
It was a mistake (now corrected) in the sample. The last coordinate does have to be the same as the first one.

Regards

2. Rhijul

Is there a way to optimise the code to run the algorithm for searching multiple points. Basically if we can get the status of all the points whether they are inside or outside. I know we can run the same algorithm over all the points, but then the we will be repeating a lot of our intersection calculations and the algorithm would not be that efficient.

1. Jason

You can do this using foreach loops with multiple regions and points. I have gotten this to work but some points are saying they are inside of a region when they clearly are not.

1. Michael Post author

Hi,
The most probable cause is that your end point isn’t the same as the starting one. As mentioned in the article, they both must be identical in order to close the loop. You can also make the small improvement suggested by Alexis, which was not yet added to our original code, in order to remove that restriction.

1. Jason

Will this work when reformatting Google coordinates from a KML file? Here is the file that I am using to loop through all of the polygons with all of my points (https://github.com/jdmagic21/GMapParse/blob/master/polyPointInclude.php). I have even verified that the first coordinate and the last are the exact same. Here also is an example of what the coordinate array looks like in PHP. Before making the polygon into an array I use PHP explode to give each coordinate a key. Using my loops and your code I am able to return all the insides, but there seems to be an issue because some points say they are in inside another region when clearly they are not, such that a point in Carmel, IN should not say it is inside Westfield, IN which your function is telling me is. Ideas?

39.82481979999999 -86.1568022, 39.8251494 -86.1449575, 39.8398476 -86.145215, 39.84080320000001 -86.1453867, 39.8427144 -86.14573, 39.8485135 -86.1458588, 39.8622513 -86.1459875, 39.8621525 -86.149807, 39.8625478 -86.1522961, 39.8626466 -86.1528969, 39.8625808 -86.1540556, 39.863173700000004 -86.1556864, 39.863173700000004 -86.1562872, 39.8627125 -86.1572742, 39.82481979999999 -86.1568022

1. Michael Post author

Hi Jason,
Could you give me the coordinates of a few points (including Carmel, IN), so I can check it out?

2. Jason

If you use the above coordinates for the polygon, you can also use these points and they give the wrong data.

I think there are some that it says are outside which are inside.
Insides seems to be outside.

39.8908910 -86.1520479 Says outside and is outside ( correct )
39.6588720 -86.2064820 Says inside but is outside
39.8227610 -85.9702870 Says inside but is outside
39.8027410 -86.0554159 Says inside but is outside

Here are some more points I have not used yet and what the function claims they are:

(39.8032929 -86.0554240): inside
(39.8282110 -86.0045320): outside
(39.7218360 -86.2282910): inside
(39.7720200 -86.2045009): inside
(39.8283220 -86.1205470): outside
(39.7988650 -86.0596240): inside
(39.7990120 -85.9844390): inside
(39.8920670 -86.3149500): outside
(39.6656953 -86.1222955): inside
(39.8880950 -86.1037290): outside
(39.7696313 -86.1055516): inside
(39.7992860 -86.0575600): inside
(39.9741980 -85.9173570): outside
(39.8616300 -86.1439150): outside
(39.8382786 -86.2957541): outside

3. Michael Post author

I’m not sure what’s wrong with your implementation, but when I check those points with my original script, they are all found outside, as they should be:
point 1 (39.8908910 -86.1520479): outside
point 2 (39.6588720 -86.2064820): outside
point 3 (39.8227610 -85.9702870): outside
point 4 (39.8027410 -86.0554159): outside

2. Jason

If this is the result of transposing a KML file, is there support for using the default coordinates such as the following:

-86.1568022,39.82481979999999,0.0 -86.1449575,39.8251494,0.0 -86.145215,39.8398476,0.0 -86.1453867,39.84080320000001,0.0 -86.14573,39.8427144,0.0 -86.1458588,39.8485135,0.0 -86.1459875,39.8622513,0.0 -86.149807,39.8621525,0.0 -86.1522961,39.8625478,0.0 -86.1528969,39.8626466,0.0 -86.1540556,39.8625808,0.0 -86.1556864,39.863173700000004,0.0 -86.1562872,39.863173700000004,0.0 -86.1572742,39.8627125,0.0 -86.1568022,39.82481979999999,0.0

1. Jason

Sorry but, I still don’t know that it is working. I think there is an issue with having strings or numbers inside of the arrays.

2. Michael Post author

I really don’t know what else to say… If I run my original script with the 4 points you mentioned and create a polygon array with the coordinates you gave me, the 4 points are found outside. So there must be an error somewhere in your implementation.

3. Diego

Thank you so much, the algorithm works like a charm with latitudes/longitudes… I will definitively buy you coffee 😀

1. Michael Post author

Hi Leonard,
You don’t have anything to do, as it works as is with geographical coordinates. Of course, they must be in decimal degrees, not in degree/minute/second.

4. Nilesh Nayak

Hi,

I have a set of points as detailed below.

\$pointlocation = new pointLocation();

\$pts[] = “51.22881787980134 -1.157684326171875”;
\$pts[] = “51.138432319543924 -1.043701171875”;
\$pts[] = “51.11990293528057 -0.998382568359375 “;
\$pts[] = “51.12248887705868 -0.9455108642578125”;
\$pts[] = “51.19483648846099 -0.778656005859375”;
\$pts[] = “51.222367645529715 -0.701751708984375”;
\$pts[] = “51.269648373496736 -0.696258544921875”;
\$pts[] = “51.30443311306082 -0.71685791015625”;
\$pts[] = “51.336617716006664 -0.770416259765625”;
\$pts[] = “51.350771787631196 -0.9468841552734375”;

\$centerpoint = “51.263217 -0.9525255999999445”;
echo \$pointlocation->pointInPolygon(\$centerpoint, \$pts);

This seems to show that the point is outside when in effect, it is inside.

If I am not wrong, the following statement causes the issue.

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']) {

I am not sure what this statement is trying to do.

Can you please shed light on this as we are using this in one of our projects.

1. Michael Post author

Hi Nilesh,

Don’t forget that, as mentionned in the article, the first and last point of the polygon array must be identical, to close it 😉
So, just add \$pts[] = “51.22881787980134 -1.157684326171875”; as the last point and the script will return inside, as it should.

Kind regards,

Michaël

5. Parth

hey this how i am using this but it always show outside as result

\$pointLocation = new pointLocation();
\$points=array(“22.560019387 72.907277656”);
\$polygon = array(“72.9443135978394 22.5665187803137″,”72.9671445609741 22.5735726534814”,
“72.9671445609741 22.5735726534814″,”72.9735818626099 22.5691343034821″,”72.9702344657593 22.5570470009717”,
“72.9702344657593 22.5570470009717″,”72.9810920478516 22.5427786579349″,”72.9810920478516 22.5427786579349”,
“72.9810920478516 22.5427786579349″,”72.9496780158692 22.5259718289148″,”72.9496780158692 22.5259718289148”,
“72.9156890632324 22.5396077146951″,”72.9156890632324 22.5396077146951″,”72.9194656135254 22.5623576184676”,
“72.9440990211182 22.5663998917189″,”72.9443135978394 22.5665187803137”);

foreach(\$points as \$key => \$point) {
echo “point ” . (\$key+1) . ” (\$point): ” . \$pointLocation->pointInPolygon(\$point, \$polygon) . “”;
}

parth

1. Michael Post author

Hi Parth,

It seems you switched the x and y values of the point, but even if it were x=72.907277656 and y=22.560019387, it would clearly be outside, as none of the polygon coordinates has x less than 7.91

Regards,

Michaël

6. Jonas

Hey,

great work!
I have a question, is there a way to make a “hole” in the middle of a polygon (like in the sample picture; point 3).

Kind Regards from Germany

Jonas

1. Michael Post author

Thanks Jonas,
It is indeed currently not supported, but I’ll try to add it in a future version of the script. Anyway, the basic idea is to check the number of intersections with both boundaries (the external polygon and the “hole”) and add them up. If the total is an odd number (or 0), then the point is either outside or in the hole. I hope that helps.
Michaël

7. akismet-80400ff01fa0a76a61544fe392b1cb6b

Is there a way of inverting the search so that instead of searching for multiple points in a single polygon it searches for a single point in multiple polygons?

1. Michael Post author

Hi,
You just have to run the script in a loop, so it checks whether the point is inside/outside each of the polygons.
Regards,
Michaël

8. ideasbinariasangel

i have an array with coordinates:
\$polygons :
[0] => 18.41059802826527 -88.03557809904612
[1] => 18.41580996014612 -88.24981149747505
[2] => 18.4716617793069 -88.249813060726
[3] => 18.475569353943605 -88.30062482830219
[4] => 18.487291543546217 -88.31985090252014
[5] => 18.484686681799133 -88.34594343181584
[6] => 18.485989117621315 -88.36654279704898
[7] => 18.476871859036027 -88.37615583415798
[8] => 18.49510589119781 -88.40224836345367
[9] => 18.478174354235335 -88.44482038493693
….
[164] => 18.14315877533503 -87.9022376682663
[165] => 18.16044934189305 -87.92489697002266
[166] => 18.16044934189305 -88.02995373271435
[167] => 18.410310718038836 -88.03630833016227
[168] => 18.41059802826527 -88.03557809904612

if i write:
\$point = “18.511268 -88.289952 ”
it’s work fine, but when i write \$point inside a while structure (i get many points from a table) it’s don’t work, because coordinate 18.511268 -88.289952 says outside when must be inside.

i am thinking this mistake is because i have many points (543) to validate inside a while structure, so, the server’s memory may be is “confused” like a result of the operations.

* note that the first and last position are the same in \$polygons.

1. Michael Post author

Hi,
I don’t see why there would be an issue with the use of while. Since it works when you run the script with a single point, it should give the same result for that particular point when checking multiple points. The only thing that comes to mind would be that a variable is not reset properly in that while loop, but it’s really difficult to say without seeing the code.
As shown in the sample code above, you can put all the points in the \$points array, and they will all be checked in the foreach loop. Have you tried fetching all you points from the table (using while) to populate the \$points array and then running the point-in-polygon script in the foreach, as in that sample?
Regards,
Michaël

9. Paul Lee

Hi,
First of all, I’m very grateful that you’ve done this. I experimented with some code a long time ago but it became so long winded that I gave up 🙁

Could I possibly ask a question? (Hopefully you’re OK with this…)

I’m creating an array of objects in php, each one has member variables, including the vertices of a polygon. I’m trying to find out if a given co-ordinates is within the polygons, but I can’t get it to work.

This is my code so far

class EData
{
public \$datemod; // This is just a dummy for the time being
public \$vertices;

function __construct( \$dm, \$v )
{
\$this->datemod = \$dm;
\$this->vertices = \$v;
}
}

\$elist = array();
array_push(\$elist, new EData( “am”, array(“25 90”, “75 90”, “60 -90”, “40 -90”, “25 90”) ) );
array_push(\$elist, new EData( “pm”, array(“80 90”, “120 90”, “100 -90”, “90 -90”, “80 90″) ) );

\$lat = 50;
\$long = 80;

\$pointvar = \$lat . ” ” . \$long;
\$pointstr = (string) \$pointvar; // cast to string

\$pointLocation = new pointLocation();

for( \$i=0; \$i pointInPolygon(\$point, \$elist[\$i]->vertices) . “”;

}

The first output should say that the point is within the polygon but not the second but it says both are outside. Can you see what is wrong?

1. Michael Post author

Hi Paul,
Good to know it was just a typo and that it is working fine now.
And thanks for your comment. I’m very glad to know that this code is useful to you!

10. Alexis

Hi,

Thanks for this function. Very useful.
I suggest this improvement to close the polygon automatically if needed.

\$i=0;
\$first = null;
\$last = null;

foreach (\$polygon as \$vertex) {
\$vertices[] = \$this->pointStringToCoordinates(\$vertex);
if(\$i == 0){
\$first = \$this->pointStringToCoordinates(\$vertex);
}
\$last = \$this->pointStringToCoordinates(\$vertex);
\$i++;
}

if(\$first != \$last){
\$vertices[] = \$first;
}

1. Michael Post author

Thank you very much, Alexis. That’s indeed something I’ve intended to add for some time, but couldn’t find the time to do it yet. If you don’t mind, I’ll soon include your suggestion into my original code.

11. Jason

I think this only works for a small subset of points with a single polygon. I believe that the moment you add a while statement, this breaks.

1. Michael Post author

According to our tests and the feedback from many users, it works with big sets of points and multiple polygons as well, in loops. I really don’t know what the problem with your implementation is, but there is no reason to believe that my script stops working above a certain threshold, since in a loop it just starts from scratch with every value.

1. dosentti

I managed to repeat this problem and solved it.

I don’t know if the problem was exactly the same but for me the problem was that I had two while loops like this

while (\$area = fetch_assoc(\$areaResult)){
while(\$point = fetch_assoc(\$pointResult)){
//CALL THE pointInPolygon function..
}
}

This setup broke after second polygon. I fixed it by doing fetch_assoc separately before I go to this script. I also changed while to foreach. I’m not sure if the solution was foreach of moving fetch_assoc outside of that piece of code.

Anyways. hope this helps if someone bumps into this.

12. hallan

Hi, i’am from Brasil

Thank you, the class worked properly , but a detail when working with coordendas values ​​many EXTENDO and negative class error occurs in checking that the inside or outside.

1. Michael Post author

I do not understand what you mean by “many EXTENDO and negative class error occurs”, though. Could you please clarify?

13. Jan

Hi Michael,

thank you for the code, you saved me a lot of work.

1) Hole inside polygon:
You can simply define 2 polygons, one inside another. The smallest represents the hole. If a point is inside both you know it is in the hole. If it is only inside the bigger you know it is not in the hole.

2) Boundary
I thin it is impossible to find out if a point is on the boundary, except it is a perfectly horizontal or perfectly vertical line. If it is anything else you would need infinite precision or define some degree of tolerance?
Please, correct me if I’m wrong.

Thank you again, it works like a dream.

Jan

14. Andrew Karlsson

Hello, great work how i can use a varible like

\$data = “lat long”, “lat2 long2″…. etc etc

and put this string into

\$polygon = array(\$data);

regards
Andrew Karlsson

1. Michael Post author

It seems to me that you could use the explode function (http://php.net/manual/en/function.explode.php), possibly after str_replace to remove the double quotes from your string. If you still have trouble, don’t hesitate to post the exact string you have in \$data. It might be easier to help you that way.

15. Andrew Karlsson

thanks you Michael.

for example i have this polygon data

\$data = ‘ “-1 2″,” -2 -3″,”-2 -2″, “1 -1″,”-1 2″ ‘;

\$data comes as result from a mysql query

polygon = array(\$data);

when i put the above the code doesn’t works, but when i put literal the info from \$data varible it does.

i think that

polygon= array(\$data) is expecting at least 4 o more arguments and with only one argument fail

best regards
Andrew.

1. Michael Post author

Hi Edward,
The problem is indeed what I thought it were. That is, you try to feed the array as if it were a simple string. Run the following code:

```\$data = ' "-1 2"," -2 -3","-2 -2", "1 -1","-1 2" '; \$polygon = array(\$data); print_r(\$polygon); \$polygon=explode(',',str_replace('"','',\$data)); print_r(\$polygon);```

As you’ll see, the first \$polygon has only one value, which is the whole string, and is thus unusable by my script. On the other hand, when using explode and str_replace, you feed the 5 distinct coordinates sets to the array. This is how it should be.
Don’t hesitate to check the arrays section in the online PHP manual, as it explains everything quite clearly and with lots of examples and comments.
I hope that helped!

16. Andrew Karlsson

Michael after make the modification it works! thanks you again for your support and time

best regards
ak

17. Juan Antonio Rosales Fuentes

Hi, i have a question, you do know how check if a point it is in a ruta. I have a ruta that have points, but not is a polygon. Thanks for you response.

18. apicton

I’m wondering if I’m missing something obvious in my long/lat implementation.

In the google kml file, the coordinates are listed as:
-93.20251460000001,45.1589218,0.0 -93.202858,45.1263512,0.0 -93.1415749,45.1219909,0.0 -93.1499863,45.156864,0.0 -93.20251460000001,45.1589218,0.0

In your script, I don’t see all of the 0.0 values and you are using spaces between values instead of commas…and commas instead of spaces between pairs. I want to make sure I am not missing something since it isn’t quite working.

Would you simply convert the coordinate string above like this?:
“-93.20251460000001 45.1589218”, “-93.202858 45.1263512”, “-93.1415749 45.1219909”, “-93.1499863 45.156864”, “-93.20251460000001 45.1589218”

19. Kashif Ali

Hello
I have created some polygone, then i want to check whether some point is inside the polygon or not. I take one point randomnly from the google map and check . i come to know that that this functions shows that this point is in polygin but actually its not. I am writing polygon co-ordinates and also point to check. Can anyone guide me…

Array
(
[0] => 26.050845512925907 56.085097789764404
[1] => 26.049399678541796 56.085333824157715
[2] => 26.04880206178719 56.08919620513916
[3] => 26.05125034335748 56.08938932418823
[4] => 26.051751560049787 56.09561204910278
[5] => 26.053274474541126 56.09838008880615
[6] => 26.053293751812927 56.10245704650879
[7] => 26.054488936471344 56.1057186126709
[8] => 26.055645555180284 56.10726356506348
[9] => 26.05358291050932 56.11136198043823
[10] => 26.053178088134597 56.113035678863525
[11] => 26.051269620962195 56.11870050430298
[12] => 26.054623875908952 56.124515533447266
[13] => 26.057592504224658 56.12816333770752
[14] => 26.057939481846148 56.135029792785645
[15] => 26.068386882247918 56.14262580871582
[16] => 26.06904222316999 56.15108013153076
[17] => 26.069736109561056 56.15378379821777
[18] => 26.054469659396155 56.16537094116211
[19] => 26.019920048025202 56.18236541748047
[20] => 26.018454549386245 56.18236541748047
[21] => 26.016911899472703 56.18155002593994
[22] => 26.00950689769804 56.182236671447754
[23] => 26.00491710488046 56.181464195251465
[24] => 26.00187000049708 56.177945137023926
[25] => 25.99666274043475 56.181464195251465
[26] => 25.995119804239533 56.18129253387451
[27] => 25.988099188740094 56.1875581741333
[28] => 25.984280106395293 56.1910343170166
[29] => 25.979264961345528 56.19614124298096
[30] => 25.97563849243092 56.195068359375
[31] => 25.967999394173663 56.18760108947754
[32] => 25.962211868251202 56.18760108947754
[33] => 25.953800156428763 56.184425354003906
[34] => 25.952256657793875 56.18382453918457
[35] => 25.94878371187306 56.17515563964844
[36] => 25.946313999114096 56.17283821105957
[37] => 25.947471683419742 56.16640090942383
[38] => 25.942454969228923 56.16477012634277
[39] => 25.932189334232934 56.17086410522461
[40] => 25.926091277959006 56.174211502075195
[41] => 25.91868055704811 56.17850303649902
[42] => 25.907409192724135 56.18142127990723
[43] => 25.891890004346582 56.179189682006836
[44] => 25.887334233241205 56.173439025878906
[45] => 25.875750972731616 56.161251068115234
[46] => 25.857987767091547 56.173095703125
[47] => 25.85752434338477 56.16365432739258
[48] => 25.830333640494594 56.14588737487793
[49] => 25.820135515894055 56.141252517700195
[50] => 25.811172802496618 56.139793395996094
[51] => 25.79672286265453 56.15464210510254
[52] => 25.757304983972784 56.15429878234863
[53] => 25.75282133721186 56.15962028503418
[54] => 25.736972608773677 56.162109375
[55] => 25.723518858924308 56.166744232177734
[56] => 25.6850048884496 56.15129470825195
[57] => 25.61954899653852 56.17584228515625
[58] => 25.61540843950344 56.1991024017334
[59] => 25.612119109698366 56.2031364440918
[60] => 25.611732123769468 56.21455192565918
[61] => 25.60960367876392 56.229872703552246
[62] => 25.602405383946717 56.25330448150635
[63] => 25.60641094019358 56.26601815223694
[64] => 25.609342457902095 56.26152276992798
[65] => 25.613115592698005 56.254591941833496
[66] => 25.615882482511378 56.25452756881714
[67] => 25.6170046992798 56.2549352645874
[68] => 25.618939531027024 56.257134675979614
[69] => 25.620729222499204 56.25774621963501
[70] => 25.622509213371792 56.2589693069458
[71] => 25.62329278790311 56.2609326839447
[72] => 25.624327872306147 56.26191973686218
[73] => 25.62518882352834 56.26293897628784
[74] => 25.627481438653753 56.263883113861084
[75] => 25.62796510710966 56.26444101333618
[76] => 25.62796510710966 56.26697301864624
[77] => 25.628284327217596 56.26848578453064
[78] => 25.629067863865274 56.26920461654663
[79] => 25.62947414010327 56.26967668533325
[80] => 26.382027976025352 56.88720703125
[81] => 26.46565563783836 56.2225341796875
[82] => 26.30818854315368 56.07421875
[83] => 26.05157806220655 56.08350992202759
[84] =>

)
latitudue and longitude to check is blow
\$latitude=’25.162528′;
\$longitude=’56.084213′;

help will be highly appreciated

20. Victor

Thank you very much, Michael!

I’ve faced up this problem recently and I had exactly the same thought about algorithm! It was easy enough, but the question was to code it. So I was looking for a turnkey solution, even i was adviced to use GeoPHP. It was overcomplicated for that simple task and also required additional GEOS lib to execute the “contains” operation, so it just irritated me.

Then luckily I meet your solution and I liked it. I’ve read every line of code there and have got how to alter it for my purposes (hope you don’t mind it 8D). I definitely agree with the math part.

And I just LOVE this line of code:
if (\$point[‘y’] > min(\$vertex1[‘y’], \$vertex2[‘y’]) and \$point[‘y’] <= max(\$vertex1['y'], \$vertex2['y']) …
It helps to avoid the danger I was warried about, that the horizontal line we "draw" will cross the polygon right at the vertex. Your code is able to count it right!

Still I think in this condition:
if (\$vertex1['x'] == \$vertex2['x'] || \$point['x'] <= \$xinters)
first clause (\$vertex1['x'] == \$vertex2['x']) is excessive cause the second one will duplicate it. But it really doesn't matter 🙂

Thank you once more for your script, it's awesame and performs nice.

1. Victor

And one thing you probably missed.
PHP may annoy you while operating floats. It can easily decide that the point (1.2 1.2) does not lay on the boundary with vertices (1.1 1.1) and (1.3 1.3) as long as you use equality operator == for floats.
So it’s reasonable to make a constant:

// Max error while operating floats
const EPSILON = 1E-6;

And then instead of strict equality
if (\$xinters == \$point[‘x’]) { … }

use approximate comparsion
if (abs(\$xinters – \$point[‘x’]) < self::EPSILON) { … }

Best regards and do not get caught in that float trap 🙂

1. Michael Post author

Thank you very much for your comments, Victor! Happy to know that it was useful to you. As for the float issue, your advise might indeed be taken into account; I’ll try to update it code soon.

21. Alex Duffield

To all having difficulties using this with Google Maps data and KML files.

1) KML files will store out the polygon as “lng, lat, elevation” . Google Maps points are normally lat, lng … Notice that in KML its LNG first, and in maps points are normally LAT first.. Make sure your order is correct.

2) This code assumes that the coordinates are “x y” (or “lat lng”) with a space, but google data is “lat, lng” with a comma separating them.

3) Finally, this does not return a true/false value . It returns a sting of “inside” and “outside”

These were a few “gatchas” that had me stumped, but once I figured those out, this is the best “inPolygon” function I have found..

Thanks!!!

1. Michael Post author

Just a little precision regarding 3). This script can return 4 values, that’s why a simple true/false value would not be possible. Indeed, besides “inside” and “outside”, it can return “boundary” and (optionally) “vertex”, as explained in the article.
Regards,

22. bruno

Hello i have a problem. Hope you can help me out.
It really really strange, for example i have
\$cadena = “25.608365293320226 -100.26979207992554, 25.61142253412417 -100.26567220687866, 25.603992142085193 -100.25863409042358, 25.600702498129785 -100.26545763015747”;
and i have
\$cadena2 = array(“25.608365293320226 -100.26979207992554”, “25.61142253412417 -100.26567220687866”, “25.603992142085193 -100.25863409042358”, “25.600702498129785 -100.26545763015747”);
assuming the first one comes from data from the database, but im shorting it up.
for some reason, when i use the \$cadena with the explode function, your point in polygon doesnt works and says all the points are outside. and when i use the manually defined array it works. (i used a script found up to dont need to close the polygon).

i even compared the 2 vars with and if(\$v1==\$v2) and they are the same. im loosing my head here. already tried to define \$cadena = array(); before the explode function and it doesnt works.

do you have any idea what could be wrong here?? it seems that php is haunted or crazy. is there a way yo fix this or is there a way i could input a whole string with all the polygon points into your function and it processes it internally?

1. Michael Post author

Thanks for your comment! No need for a medal, but I’d appreciate a cup of coffee or a beer 😉

23. SUPERMARIO

you forgot to add if(\$intersections == 0 ) echo ‘outside’;
you can check the issue with a triangle who has one vertical segment and one horizental segment.
Regards 🙂

24. Dylan

This has been a huge help, I have used this to determine if an address is inside a Google Maps drawn polygon, and the shapes have been quite complex!

Something I just discovered is that it can return false positives for ‘inside’ if one of the intersections occurs between the first and last points (Google Maps connects these automatically).

If anyone encounters this issue, you can use the comparison logic (everything inside the for-loop) to compare \$vertices[0] and \$vertices[\$vertices_count].

Thanks again, Michael this has been a huge help.

25. Armand Hansen

This is one of the cleanest, shortest code that I have found (and I have been searching and testing over 30 code snips) and it WORKS. No matter how complex the Polygon. Thank you so much for sharing this code with everyone! I will be sharing it to Stack Overflow so other people can also get their code working. And of course be linking you in there!

26. Rene

Thanks a lot for the great script!

On PHP 7.0.3 you will receive a deprecated message:

PHP Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; pointLocation has a deprecated constructor in [removed]\pointLocation.lib.php on line 18

Deprecated: Methods with the same name as their class will not be constructors in a future version of PHP; pointLocation has a deprecated constructor in [removed]\pointLocation.lib.php on line 18

Removing

function pointLocation() {
}

helps.

Best regards

27. logic

There is a bug with polygons going over the 180th meridian (the anti-meridian). Here’s a simple fix:

// Fix for 180th meridian
if(\$vertex1[‘y’] < 0) \$vertex1['y'] = \$vertex1['y'] + 360;
if(\$vertex2['y'] < 0) \$vertex2['y'] = \$vertex2['y'] + 360;
if(\$point['y'] < 0) \$point['y'] = \$point['y'] + 360;

Add the lines above after this line in original code:
\$vertex2 = \$vertices[\$i];

28. Kevin R

Hi Michael!

Thank you for your script and visual representations. Everything was very clear. I still have one issue. At the moment you calculate all intersections along the x axis, the xinters results. But is there a way to calculate intersections on the y axis, the yinters so to speak. I can’t seem to wrap my head around it.

Greetings
Kevin

1. Michael Post author

Hi Kevin,
Yes, it is possible, following the same logic but for Y instead of X. Unfortunately, I don’t have the time right now to do it, but could you tell me why you’d like to do it that way instead of using the script as is?

29. TomH

Thanks for this – very useful. I am passing an associative array eg \$point = array(“x”=>1,”y”=>2) so have amended the start of your code to this:

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

etc

1. Michael Post author

Hi,
If a point is out of the polygon, it will simply return “outside”, so you can use that to validate each set of coordinates.

30. gmar

Hi,

I’m trying to use this script for a polygon with the following longitude and latitudes:

\$polygon = array(“43.231297 -79.813721″,”43.238438 -79.810768″,”43.230335 -79.809395″,”43.230312 -79.809296″,”43.240208 -79.808983″,”43.230225 -79.808884″,”43.240116 -79.808617″,”43.229823 -79.807388″,”43.231235 -79.802649″,”43.237137 -79.800774″,”43.231297 -79.813721”);

For the following point (which is inside the polygon), I am getting “outside”:

\$points = array(“43.2353 -79.807541”);

However, I have randomly spotted that if I remove the point “43.229823 -79.807388” from the original polygon and re-run the script, then it gives me “inside”. i.e.

\$polygon = array(“43.231297 -79.813721″,”43.238438 -79.810768″,”43.230335 -79.809395″,”43.230312 -79.809296″,”43.240208 -79.808983″,”43.230225 -79.808884″,”43.240116 -79.808617″,”43.231235 -79.802649″,”43.237137 -79.800774″,”43.231297 -79.813721”);

Are you able to offer any advice please as to why the first polygon fails to provide the correct answer, but by removing one (seemingly random) point, it then gives the correct answer?

31. Jeff King

While your initial graphic does include an enclosed ring in the shape, it appears your class does not handle this case. Is that correct?

1. Michael Post author

Hi Jeff,
Indeed, you can only use one polygon in the script. That said, if you need to do that, you could run it twice. For instance, with the sample image in my article: If the point is inside the ring (#3), there is no need to go further. For points that are outside the ring (#1 and #2), run the script again but this time with the outside shape. Combining the results will thus allow you to check whether a point is inside or outside a shape with a hole in it.
Hope that helps.

32. MMOes

Hey Michael, the beer is yours, GREAT SCRIPT! Do you have any code example how it must look like if I want to check multiple polyglones? I’m just a Beginner and very happy with any help regarding a piece of working code examples

1. Michael Post author

Hi Magnus,
Thank you very much for the donation!
If you want to check multiple polygons with the same points, you could simply replace the \$polygon array by a “multidimensional array” (arrays within an array) and then simply loop through it just as with the points. It would be something like this:

\$polygons = array(array(“-50 30″,”50 70″,”100 50″,”80 10″,”-50 30″),array(“110 -10″,”110 -30″,”-20 -50″,”-30 -40″,”110 -10″));
// For each one of the polygons, the last point’s coordinates must be the same as the first one’s, to “close the loop”
foreach(\$polygons as \$pkey => \$polygon) {
foreach(\$points as \$key => \$point) {
echo “polygon \$pkey – point ” . (\$key+1) . ” (\$point): ” . \$pointLocation->pointInPolygon(\$point, \$polygon) . “<br>”;
}
}

Hope that helps!
Michaël

33. Vinoth Krishnan

Hi,

Am getting outside result.

x-coordinates of the vertices of the polygon
——————————————–

Array ( [0] => 103.71052550850436 [1] => 103.70640563545749 [2] => 103.71773528633639 [3] => 103.72803496895358 [4] => 103.73421477852389 [5] => 103.74073791084811 [6] => 103.7349014240317 [7] => 103.76168059883639 [8] => 103.76580047188327 [9] => 103.77747344551608 [10] => 103.79326629219577 [11] => 103.78468322334811 [12] => 103.77816009102389 [13] => 103.77610015450045 [14] => 103.76648711739108 [15] => 103.75893401680514 [16] => 103.75721740303561 [17] => 103.7400512653403 [18] => 103.7349014240317 [19] => 103.73181151924655 [20] => 103.72425841866061 [21] => 103.74176787910983 [22] => 103.74176787910983 [23] => 103.70606231270358 [24] => 103.66932677803561 [25] => 103.65731048164889 [26] => 103.6466674762778 [27] => 103.7019424396567 [28] => 103.70468902168795 )

y-coordinates of the vertices of the polygon
——————————————–

Array ( [0] => 1.3157088608289513 [1] => 1.3486589361925596 [2] => 1.356896385753888 [3] => 1.3527776644691114 [4] => 1.3445402009455167 [5] => 1.3486589361925596 [6] => 1.3555234794371298 [7] => 1.3802356732739276 [8] => 1.3637609056334548 [9] => 1.364790581929094 [10] => 1.352091210241309 [11] => 1.3435105160471006 [12] => 1.3400782299198641 [13] => 1.3352730212639332 [14] => 1.3304678032144759 [15] => 1.3369891682925708 [16] => 1.324289651973947 [17] => 1.3229167273821032 [18] => 1.3297813427282703 [19] => 1.3280651906777277 [20] => 1.3060983397151458 [21] => 1.275207131411755 [22] => 1.2679991291306587 [23] => 1.2395101628735419 [24] => 1.212737119913689 [25] => 1.2470614852772457 [26] => 1.2745206558718953 [27] => 1.2995768937253298 [28] => 1.3002633625187114 )

x-coordinate of the point
————————-
103.730222

y-coordinate of the point
————————-
1.3505069

How to fix this.

Thanks,
Vinoth K

1. Michael Post author

Hi Vinoth,
How do you feed the polygon coordinates to the script? As mentioned in the article, the last set of coordinates must be the same as the first one, to “close the loop”. Not doing so is often a cause of incorrect results.
Regards,
Michaël

34. Prabhu

HI there,
Really helpful post.. I did like what u have given in the description. But point is showing as outside the polygon.Plz help me.. My project is in codeigniter..

polygon latlng:- Array ( [0] => 12.908748880663135 77.57892608642578 [1] => 12.904021961371704 77.57579326629639 [2] => 12.906908320943131 77.58300304412842 [3] => 12.908748880663135 77.57892608642578 )

User latlng:- Array ( [0] => 12.906420291259 77.579140663147 )

outside

1. Michael Post author

Hi Prabhu,
My best guess is that you don’t populate the arrays correctly, because I don’t see any problems when using the following:
```\$points = array("12.906420291259 77.579140663147"); \$polygon = array("12.908748880663135 77.57892608642578", "12.904021961371704 77.57579326629639", "12.906908320943131 77.58300304412842", "12.908748880663135 77.57892608642578");```
The point is given as “inside”.
Regards,
Michaël

1. Prabhu

hi michael,
Thanks for replying bro.. If i can send you the code will u be able to figure it out what is the issue.. I’m surprised that U replied me immediately.. Once again thanx.. One last favour i’m asking.. plz.. Tell me how can i send u the code..

1. Prabhu

Hi michael,
Can u plz help me in resolving this problem. Waiting for your reply.. Finishing this project can definately get u a cup of coffee.. I assure u.. Thank u..

1. Michael Post author

Hi Prabhu,
I’ve contacted you by e-mail so you can send the code back and I can take a look at it.

35. prabhu

Hi michael,
Finally I solved that problem myself.. Actually the problem was due to extra space in the coordinates which i was fetching from database.. So explode was not working properly.. which i noticed and corrected.. Thanks a lot bro for showing interest in my problem..

36. Lewis

This is a great resource – thanks a lot.

I made a couple of changes to the class (possibly partly due to own preference). Firstly removed the blank constructor as in PHP7 they are depreciated from being the same as class name and is possible not required in there?

“array_push(\$vertices, \$vertices[0]);”

Under here:
“foreach (\$polygon as \$vertex) {
\$vertices[] = \$this->pointStringToCoordinates(\$vertex);
}”

That way it saves having to pass the initial co ordinate twice (I’m getting my co ordinates in a way where I only get passed the co ordinates once each.).

Working exceptionally well so thanks for creating this – just what I was looking for.

1. Michael Post author

Indeed, the constructor could be removed for users of PHP7.
array_push() is also a nice little addition.
Kind regards,
Michaël

37. Parveen

Hi,

I getting wrong response. Function giving response “inside”, but when I checked at google given point is not exit in given area.

Points are :

\$points = array(“30.71102842 76.70939199”);
\$polygon = array(“30.711064231914783 76.7093163728714″,”30.711140331172867, 76.7094960808754″,”30.711008886962087, 76.7096221446991″,”30.71093509364243, 76.70941829681396”);

Thanks,

Parveen

1. Michael Post author

Hi Parveen,
As mentioned in the article, the polygon must be “closed”, that is, the first and last point must be identical. This is likely the cause of the wrong response. Just duplicate the first point’s coordinates to the end of the polygon array.
Regards,
Michael

38. esoares9483

For whoever else had this problem, it took me about three weeks to realize my rookie mistake.
When polygons from the database will not work but works when pasted in your file it is because the polygon is a string and not an actual array. This is a simple way i fixed that problem.

The example is CodeIgniter blah blah, just explode your string you get from MySQL, I did not even have to use array() either, in fact I think it broke it when pulling from database.

\$polygons = \$this->location_model->get_geoCoordinates(\$location_id);
\$polygon = explode(‘”,”‘,\$polygons);

In closing let me know if you get stuck.

39. Fernando

thank you so mucho… you saved me a lot of time. My project is about Google maps polygons and i should found region in vaious that a point is inside. Thanks, you are the man!