Osheep

时光不回头,当下最重要。

点是否在多边形之内

  平时在项目开发过程中我们可能经常遇到一个几何运算,如地图围栏,可恨当年高数没学好呀!没关系,这里楼主带大家一样看看,如何计算“点是否在多边形之内”。
  做过地图开发的同学可能都知道,高德已经开放了JSAPI,参考链接已经贴在文末。PHP的话也有相应的组件和扩展,如phpgeo,参考链接也已经贴在文末,有兴趣的同学请移步。
  这里我们扒开phpgeo核心源码来看看,最主要和最复杂的也就是FOR和IF那一段,如果要完全理解这段代码你需要结合整个类来阅读,这里就不做过多的讲解了。

    /**
     * Determine if given point is contained inside the polygon. Uses the PNPOLY
     * algorithm by W. Randolph Franklin. Therfore some edge cases may not give the
     * expected results, e. g. if the point resides on the polygon boundary.
     *
     * @see http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
     *
     * For special cases this calculation leads to wrong results:
     *
     * - if the polygons spans over the longitude boundaries at 180/-180 degrees
     *
     * @param Coordinate $point
     *
     * @return boolean
     */
    public function contains(Coordinate $point)
    {
        $numberOfPoints = $this->getNumberOfPoints();
        $polygonLats    = $this->getLats();
        $polygonLngs    = $this->getLngs();
        $polygonContainsPoint = false;
        for ($node = 0, $altNode = ($numberOfPoints - 1); $node < $numberOfPoints; $altNode = $node ++) {
            if (($polygonLngs[$node] > $point->getLng() != ($polygonLngs[$altNode] > $point->getLng()))
                && ($point->getLat() < ($polygonLats[$altNode] - $polygonLats[$node])
                                       * ($point->getLng() - $polygonLngs[$node])
                                       / ($polygonLngs[$altNode] - $polygonLngs[$node])
                                       + $polygonLats[$node]
                )
            ) {
                $polygonContainsPoint = ! $polygonContainsPoint;
            }
        }
        return $polygonContainsPoint;
    }

  下面我们直接切入主题,看了上面的代码有同学可能知道它用的就是较常见的射线法。所谓射线法就是从一个点向任意方向射出一条射线,判断射线和多边形的交点,如果交点是奇数,那么点就在多边形内,否则点就在多边形外。我们看下面两张图:

《点是否在多边形之内》

点在多边形之外
《点是否在多边形之内》

点在多边形之内

从北京站向任意方向射出一条射线,判断它与蓝色边框的多边形的交点,可以更加直观的帮我们理解射线法。

最后楼主直接贡献一段完整的PHP方法,判断点是否在多边形之内。

    /**
     * @param array $gather 多边形坐标集合
     * @param int $x  点的X坐标
     * @param int $y  点的Y坐标
     * @return bool   点是否在多边形内
     */
   function polygon($gather = array(), $x = 0, $y = 0){
        $c = false;
        $l = count($gather);
        for($i = 0, $j = $l - 1; $i < $l; $j = $i++){
            if(($gather[$i]['y'] > $y) != ($gather[$j]['y'] > $y) && ($x < ($gather[$j]['x'] - $gather[$i]['x']) * ($y - $gather[$i]['y']) / ($gather[$j]['y'] - $gather[$i]['y']) + $gather[$i]['x'])){
                $c = !$c;
            }
        }
        return $c;
    }

注:如有错误,敬请指正。

点赞