【算法】判断一个点是否在不规则多边形内-php版

这是别人问到的一个问题，当时完全没有思路。因为平时工作中，基本上没有用到类似的方法。这其实是一个GIS系统中判断坐标是否在范围内的算法，主要用在配送中，如外卖、快递等是否属于自己的配送范围。仔细想想，这还真是常用到的一个算法，所以重新写了一次，以防下次用到。

实现这个算法，主要用到射线判断法。即在一个多边形上，无限延长x轴，看看与多边形的相交点。如果相交点为奇数，则在多边形内；如果为偶数，则在多边形外。参考算法：https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html

PHP实现：

/**
 * @name 判断某点是否在多边形内
 * @param $areas 原始坐标点
 * @param $points 需要判断的坐标点
 * @return bool true-多边形内，false-多边形外
 */
function piontInPolygon($areas, $points)
{
    //print_r($points);
    //如果刚好在顶点
    $count = count($areas);
    for($i = 0; $i < $count; $i++){
        if($areas[$i][0] === $points[0] && $areas[$i][1] === $points[1]){
            //echo 'on point';
            return true;
        }
    }

    //取最边的四个点，判断点是否在边外
    $minX = $minY = $maxX = $maxY = 0;
    $vertX = $vertY = [];
    for($i = 0; $i < $count; $i++){
        $vertX[] = $areas[$i][0];
        $vertY[] = $areas[$i][1];

        $minX = $areas[$i][0] < $minX ? $areas[$i][0] : $minX;
        $maxX = $areas[$i][0] > $maxX ? $areas[$i][0] : $maxX;
        $minY = $areas[$i][1] < $minY ? $areas[$i][1] : $minY;
        $maxY = $areas[$i][1] > $maxY ? $areas[$i][1] : $maxY;
    }
    //echo '$minX:'.$minX.'---$maxX:'.$maxX.'---$minY:'.$minY.'----$maxY:'.$maxY;
    //如果在四边外
    if($points[0] < $minX || $points[0] > $maxX || $points[1] < $minY || $points[1] > $maxY){
        //echo 'outside';
        return false;
    }


    $c = false;
    //x射线，斜率
    for($x = 0, $y = $count-1; $x < $count; $y = $x++){
        if( ($vertY[$x] > $points[1]) != ($vertY[$y] > $points[1]) &&
            ($points[0] < ($vertX[$y] - $vertX[$x]) * ($points[1] - $vertY[$x]) / ($vertY[$y] - $vertY[$x]) + $vertX[$x] )
        ){
            $c = !$c;
        }
    }
    //var_dump($c);
    return $c;
}


//测试

$areas = [
    [1,1],
    [5,0],
    [8,0],
    [8,2],
    [5,7],
    [3,7]
];
//$points = [7,5];//false
$points = [2,3];//true
$data = piontInPolygon($areas, $points);
var_dump($data);
die();