Last active
April 22, 2019 03:03
-
-
Save cevin/d739cdbf3e28bcb9bcc201857cba6ca0 to your computer and use it in GitHub Desktop.
is point in polygon
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
function is_point_in_polygon($point, $pts) { | |
$N = count($pts); | |
$boundOrVertex = true; //如果点位于多边形的顶点或边上,也算做点在多边形内,直接返回true | |
$intersectCount = 0;//cross points count of x | |
$precision = 2e-10; //浮点类型计算时候与0比较时候的容差 | |
$p1 = 0;//neighbour bound vertices | |
$p2 = 0; | |
$p = $point; //测试点 | |
$p1 = $pts[0];//left vertex | |
for ($i = 1; $i <= $N; ++$i) {//check all rays | |
// dump($p1); | |
if ($p['lng'] == $p1['lng'] && $p['lat'] == $p1['lat']) { | |
return $boundOrVertex;//p is an vertex | |
} | |
$p2 = $pts[$i % $N];//right vertex | |
if ($p['lat'] < min($p1['lat'], $p2['lat']) || $p['lat'] > max($p1['lat'], $p2['lat'])) {//ray is outside of our interests | |
$p1 = $p2; | |
continue;//next ray left point | |
} | |
if ($p['lat'] > min($p1['lat'], $p2['lat']) && $p['lat'] < max($p1['lat'], $p2['lat'])) {//ray is crossing over by the algorithm (common part of) | |
if($p['lng'] <= max($p1['lng'], $p2['lng'])){//x is before of ray | |
if ($p1['lat'] == $p2['lat'] && $p['lng'] >= min($p1['lng'], $p2['lng'])) {//overlies on a horizontal ray | |
return $boundOrVertex; | |
} | |
if ($p1['lng'] == $p2['lng']) {//ray is vertical | |
if ($p1['lng'] == $p['lng']) {//overlies on a vertical ray | |
return $boundOrVertex; | |
} else {//before ray | |
++$intersectCount; | |
} | |
} else {//cross point on the left side | |
$xinters = ($p['lat'] - $p1['lat']) * ($p2['lng'] - $p1['lng']) / ($p2['lat'] - $p1['lat']) + $p1['lng'];//cross point of lng | |
if (abs($p['lng'] - $xinters) < $precision) {//overlies on a ray | |
return $boundOrVertex; | |
} | |
if ($p['lng'] < $xinters) {//before ray | |
++$intersectCount; | |
} | |
} | |
} | |
} else {//special case when ray is crossing through the vertex | |
if ($p['lat'] == $p2['lat'] && $p['lng'] <= $p2['lng']) {//p crossing over p2 | |
$p3 = $pts[($i+1) % $N]; //next vertex | |
if ($p['lat'] >= min($p1['lat'], $p3['lat']) && $p['lat'] <= max($p1['lat'], $p3['lat'])) { //p.lat lies between p1.lat & p3.lat | |
++$intersectCount; | |
} else { | |
$intersectCount += 2; | |
} | |
} | |
} | |
$p1 = $p2;//next ray left point | |
} | |
if ($intersectCount % 2 == 0) {//偶数在多边形外 | |
return false; | |
} else { //奇数在多边形内 | |
return true; | |
} | |
} | |
/** | |
* @name 围栏算法,判断一个坐标,是否在围栏里面.如:['113.664673,34.810146','113.681667,34.796896','113.69231,34.794711','113.702009,34.809159'] | |
* @param array $fences 围栏,是一组坐标数组 如:113.674458,34.804719 | |
* @param string $point | |
* @return bool | |
*/ | |
function in_fences($fences, $point) { | |
$nvert = count($fences); | |
$vertx = []; | |
$verty = []; | |
list($testy, $testx) = explode(',', $point); | |
foreach ($fences as $r) { | |
list($lng, $lat) = explode(',', $r); | |
$vertx[] = $lat; | |
$verty[] = $lng; | |
} | |
$i = $j = $c = 0; | |
for ($i = 0, $j = $nvert - 1; $i < $nvert; $j = $i++) { | |
if (( ($verty[$i] > $testy) != ($verty[$j] > $testy) ) && | |
($testx < ($vertx[$j] - $vertx[$i]) * ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) + $vertx[$i])) | |
$c = !$c; | |
} | |
return $c; | |
} | |
/** | |
* 判断某个经纬度是否在多边形范围内 | |
* @param type $polygon | |
* @param type $lnglat | |
* @return boolean | |
*/ | |
function isPointInPolygon($polygon, $lnglat) { | |
$count = count($polygon); | |
$px = $lnglat['lat']; | |
$py = $lnglat['lng']; | |
$flag = FALSE; | |
for ($i = 0, $j = $count - 1; $i < $count; $j = $i, $i++) { | |
$sy = $polygon[$i]['lng']; | |
$sx = $polygon[$i]['lat']; | |
$ty = $polygon[$j]['lng']; | |
$tx = $polygon[$j]['lat']; | |
if ($px == $sx && $py == $sy || $px == $tx && $py == $ty) { | |
return TRUE; | |
} | |
if ($sy < $py && $ty >= $py || $sy >= $py && $ty < $py) { | |
$x = $sx + ($py - $sy) * ($tx - $sx) / ($ty - $sy); | |
if ($x == $px) { | |
return TRUE; | |
} | |
if ($x > $px) { | |
$flag = !$flag; | |
} | |
} | |
} | |
return $flag; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment