Skip to content

Instantly share code, notes, and snippets.

@jeremejazz
Created March 22, 2013 08:48
Show Gist options
  • Save jeremejazz/5219848 to your computer and use it in GitHub Desktop.
Save jeremejazz/5219848 to your computer and use it in GitHub Desktop.
Determines whether coordinates is within polygon or not. Also tells if point is along boundary. See example at bottom of code
<?php
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 even, 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]);
}
}
/*
how to use.
Create the point value and an array containing your polygon vertices (in the form “Xcoordinate Ycoordinate”), then call the pointInPolygon function. The first and last points’ coordinates must be identical, to “close the loop”.
As you can see in the following example, you can easily check multiple points at once. It also works with negative coordinates, for the polygon as well as for the points to check.
ex.
$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>";
}
//**source: http://assemblysys.com/php-point-in-polygon-algorythm/
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment