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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
<?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 ;) PayPal: michael.niessen@assemblysys.com As long as this notice (including author name and details) is included and UNALTERED, this code is licensed under the GNU General Public License version 3: http://www.gnu.org/licenses/gpl.html */ 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.

1 2 3 4 5 6 7 8 9 |
<?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>"; } ?> |

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

bvbnice!

MrDogVery 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?

MichaelPost authorThanks 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

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

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

MichaelPost authorHi,

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.

JasonWill 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

MichaelPost authorHi Jason,

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

JasonIf 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

MichaelPost authorI’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

JasonIf 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

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

MichaelPost authorI 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.

SVery nice. Thanks for this example.

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

MichaelPost authorHi Diego,

Thank you very much for the coffee!

Nilesh NayakHi,

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.

MichaelPost authorHi 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 returninside, as it should.Kind regards,

Michaël

Nilesh NayakHi Michael,

Thank you for very much for replying. Hadn’t noticed this. Will do the correction.

Regards

Nilesh

Parthhey 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) . “”;

}

please help

parth

MichaelPost authorHi Parth,

It seems you switched the

xandyvalues 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 hasxless than 7.91Regards,

Michaël

JonasHey,

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

MichaelPost authorThanks 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

akismet-80400ff01fa0a76a61544fe392b1cb6bIs 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?

MichaelPost authorHi,

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

ideasbinariasangelhi, i need help please.

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.

please help me, thank you.

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

MichaelPost authorHi,

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 thatwhileloop, 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

foreachloop. Have you tried fetching all you points from the table (usingwhile) to populate the $points array and then running the point-in-polygon script in theforeach, as in that sample?Regards,

Michaël

fcimohamedtahathanks a lot can i use it with google maps

MichaelPost authorHi,

Absolutely, you can use it with coordinates fetched from Google maps.

bigeagle1986Thanks a lot for this code. Helps me a lot!

Paul LeeHi,

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?

Paul LeeI think I’ve fixed it. A stupid typo on my part.

MichaelPost authorHi 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!

AlexisHi,

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;

}

MichaelPost authorThank 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.

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

MichaelPost authorAccording 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.

hallanHi, 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.

MichaelPost authorThanks for your comment!

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

JanHi Michael,

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

I have two comments:

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

Wai WongGreat script, same me lot of time. Thanks!

Pepy Eddythank you for this well done work!!! really usefull. thanx again