一 前言

维基百科上面是英文，所有找了一段百度百科的定义

地理围栏(Geo-fencing)是LBS的一种应用, 就是用一个虚拟的栅栏围出一个虚拟地理边界. 当手机进入, 离开某个特定地理区域, 或在该区域内活动时, 手机可以接收自动通知和警告.

很明显核心问题就是判断点是否在多边形内。

二 判断点在多边形内部

• 射线法（对凹凸多边形都适用）。实现原理：如下图（懒得画了，截取了文章1的图）从判断点开始沿着X轴画一条射线，依次判断该射线与边的交点。
  如果交点个数是奇数，则点在多边形内，如果个数是偶数，则点在多边形外。

  
  
  射线法判断点在多边形内外.png

交点的x坐标求解用的是相似多边形性质，计算公式如下图（这个是自己画的）

求解交点坐标.png

算法实现

/**
     *
     * @param point  判断点
     * @param points 多边形的顶点集合
     * @return
     */
    public boolean pointInPoly(Point point ,Point[] points){
        boolean isContains=false;
        int end=points.length-1;
        for (int i=0;i<points.length;i++){
            //通过判断点的y坐标和每条边的两个端点的y坐标比较，判断点是否在这条边的中间
            if (point.getY()>points[i].getY()&&point.getY()<=points[end].getY()||point.getY()<=points[i].getY()&&point.getY()>=points[end].getY()){
                //计算交点的x坐标值，如果小于x则记为一次（只需要判断射线一侧的点个数即可）
                if((point.getY()-points[i].getY())/(points[end].getY()-points[i].getY())*(points[end].getX()-points[i].getX())+points[i].getX()<point.getX()){
                    isContains=!isContains;
                }
            }
            //移动顶点位置
            end=i;
        }
        return isContains;

    }

参考文章

[1]Point-In-Polygon Algorithm
[2]Point-In-Polygon算法