Have you ever had the need to check if a specific coordinate (point) is located inside or outside a polygon shaped area? I never did, so I had to found out how to automate this process, so I didn’t have to do this by hand.
The problem with this kind of assignment is, that I did not know what to search for on Google. Hadn’t though of it, as being a point in a polygon shaped area. I tried searching with words like ‘coordinate inside area’, ‘longitude latititude in area” and things like that, without much luck. Then a guy on IRC suggested a search for “point in polygon” and wuhu. Bingo.
I then found this page: point in polygon, where the author has posted a PHP class that does all the hard work for you. Brilliant.
I have a database table in MySQL containing x and y coordinates for a number of different points. In another table a have coordinates for a number of polygon shapes and I then want to check which point are located inside which polygons.
This is actually pretty simple to do.
Lets say we have a point (2,2) and want to check if this is inside a polygon with these coordinates (1,1), (3,6), (4,0):
//include the point in the polygon classs
include_once("point_in_polygon.php");
$point = "2 2";
$polygon = array("1 1", "3 6", "4 0")
$pointLocation = new pointLocation();
print "Point in " . $pointLocation->pointInPolygon($point, $polygon) . " the polygon";
(NB: remember to arrange the coordinates in a clockwise direction, as counterclockwise returns incorrect results. Thanks to carson, for this tip).
Run the code and it will print:
$ php polygon.php Point is inside the polygon
So how does this work? All you have to do, is to “draw” a straight line from the point and all the way through the shape and then count have many lines you cross. If you cross an even or zero number of lines the point is outside the shape and if the number the uneven you are inside.
Got it? Well, there’s some quick drawings from Gimp to illustrate it:
The example from the above code:
Point is inside because of a uneven number of line crosses:
Point is outside because of a even or zero number of line crosses:
There you go. This is one way to check if a point is inside a polygon shaped area.
maj 2nd, 2010 at 19:57
Hello,
i tried this code also with longitude and lantitude but it doesnt work. Have someone an idea ?
maj 2nd, 2010 at 22:11
It’s difficult to help, when all you say is that it doesn’t work. How does it not work? What does you code look like?
maj 10th, 2010 at 11:27
I am wondering if it also works with coordinates of negative value?
Thanks
maj 10th, 2010 at 17:12
Carson: it should work on negative values, yes
maj 11th, 2010 at 18:24
Thank you for you feedback. I have tested it. It doesn’t matter if those coordinates contain positive or negative values, but they need to be arranged in clockwise order to form the polygon. otherwise, it returns wrong result, which I found it a bit troublesome. Do you think so?
maj 11th, 2010 at 18:55
I never actually thought about which way I was arranging the values – perhaps all my values already was giving in the clockwise direction.
I really appreciate your feedback. Thank you.
juni 7th, 2010 at 15:28
Carsten,
the easiest way to make it work with latitude and longitude is to make sure all values are positive.
If you increase latitude by 90 and longitude by 180 (degrees) for all points in your polygon as well as for your point, you can use this class without having to reorder your polygon.
What I found problematic however if this part:
if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) {
$intersections++;
}
It did not correctly recognize the need to increase the number of intersections. I had to omit this check but so far the code still works in the instances I tested it in.
oktober 26th, 2010 at 13:52
I’m currently working on a PHP Spatial library. I implemented the Ray Casting Algorithm for determining whether or not a polygon contains a point.
http://en.wikipedia.org/wiki/Point_in_polygon
code:
protected function testPolygonContainsPoint(Polygon $polygon, Point $point) {
if (!$polygon->getBoundingBox()->contains($point)) {
return false;
}
$length = $polygon->getVertices()->length();
$inPolygon = false;
$j = $length – 1;
for($i = 0; $i getVertex($i);
$vertex2 = $polygon->getVertex($j);
if ($vertex1->getY() getY() && $vertex2->getY() >= $point->getY() || $vertex2->getY() getY() && $vertex1->getY() >= $point->getY()) {
if ($vertex1->getX() + ($point->getY() – $vertex1->getY()) / ($vertex2->getY() – $vertex1->getY()) * ($vertex2->getX() – $vertex1->getX()) getX()) {
$inPolygon = !$inPolygon;
}
}
$j = $i;
}
return $inPolygon;
}
januar 6th, 2011 at 18:16
Do the values have be ints, or can they be floats?
I am attempting to use this with long and lat coordinates but its getting it wrong
Jake
april 23rd, 2011 at 11:42
I found another working php script for the case of finding a point in polygon:
http://www.assemblysys.com/dataServices/php_pointinpolygon.php
april 25th, 2011 at 11:04
#10 it’s not another script, but the same script. My post just explains know the script at assemblysys.com is working.
maj 16th, 2011 at 09:42
(NB: remember to arrange the coordinates in a clockwise direction, as counterclockwise returns incorrect results. Thanks to carson, for this tip).
Not direction is important in this script.
here is one error.
he’s checking x-1 bounds!
so…
after:
”
foreach ($polygon as $vertex) {
$vertices[] = $this->pointStringToCoordinates($vertex);
}
”
insert:
“$vertices[-1] = end($vertices);”
AND
change: “for ($i=1; $i < $vertices_count; $i++) {"
to: "for ($i=0; $i < $vertices_count; $i++) {"
SORRY OF MY ENGLISH…
maj 24th, 2011 at 13:43
#12 the algorithm on the original site is ok. in the original example is the first and last vertice the same! the example on this page is wrong, therefore you have to make your correction!