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: https://www.paypal.me/MichaelNiessen 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

Edmund PadillaHi Michael!

I want to thank you for this great article!

God Bless!

Ed

MichaelPost authorYou’re welcome, Ed!

WebidusGreat and clear article. I’ve implemented in my ‘geo-fence’ project and it works like a charm !!! If I could give it stars , I would give you 5/5 stars 🙂

MichaelPost authorThank you very much for your nice comment!

Michael

Fernandothank 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!

MichaelPost authorYou’re welcome, Fernando!

Michael

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

ParveenHi,

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”);

Please reply me as soon as possible.

Thanks,

Parveen

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

Parveen KumarHi Michael,

Thanks for the reply. I will test it again.

Thanks Again.

Parveen

Faisal Al ZamarThank you Michael, this article very help to solving my thesis

MichaelPost authorYou’re welcome, Faisal! Glad it helped you 😉