使用Path2D和凸包算法实现地理围栏服务

前言 

地理围栏（Geo-fencing）是LBS的一种新应用，就是用一个虚拟的栅栏围出一个虚拟地理边界。在物流配送行业应用比较广，划分每个配送网点或者商家配送的范围，提高配送员的配送效率和服务的范围。

 

1.使用Path2D创建一个多边形

Path2D类是java.awt.geom包提供的工具包，可表示任意几何路径的简单而灵活的形状。它可以完全表示PathIterator接口可以迭代的任何路径， 包括其所有段类型和绕组规则，并且它实现了Shape接口的所有基本命中测试方法。

使用Path2D.Float带有可表示且能使用浮点精度的数据的时候。使用Path2D.Double 对于需要双精度的准确性或范围的数据。

先通过高德地图在线编辑一个多边形覆盖图，然后获取到有序的坐标

https://lbs.amap.com/api/javascript-api/example/overlayers/polygon-draw-and-edit

代码示例如下:

//传参 有序的坐标范围
public static Path2D.Double create(List<PointDouble> polygon) {
    //创建path2D对象
    Path2D.Double generalPath = new Path2D.Double();
    //获取有序坐标范围的第一个坐标
    PointDouble first = polygon.get(0);
    //通过移动到指定坐标（以双精度指定），将一个点添加到路径中
    generalPath.moveTo(first.getX(), first.getY());
    //删除有序坐标范围第一个
    polygon.remove(0);
    //遍历有序坐标范围后面的坐标
    for (PointDouble d : polygon) {
        // 通过绘制一条从当前坐标到新指定坐标（以双精度指定）的直线，将一个点添加到路径中。
        generalPath.lineTo(d.getX(), d.getY());
    }
    // 将几何多边形封闭
    generalPath.lineTo(first.getX(), first.getY());
    //关闭路径
    generalPath.closePath();
    return generalPath;
}

以上用到了的方法详解

moveTo(double x, double y)

通过移动到以double精度指定的指定坐标，向路径添加一个点。

lineTo(double x, double y)

通过从当前坐标绘制直线到以double精度指定的新指定坐标，将路径添加到路径。

closePath()

通过将直线绘制回最后一个坐标来关闭当前子路径moveTo。

 

 

2.判断某个坐标是否在Path2D

代码示例

PointDouble point = new PointDouble(116.403322,39.920255);
//生成好的多边形是不是包含某个坐标
path2d.contains(point)

以上用到了的方法详解

contains(double x, double y)

测试指定坐标是否在边界内Shape

 

3.判断某个矩形区域是否在Path2D

contains(PathIterator pi, double x, double y, double w, double h)

测试指定的矩形区域是否完全位于指定的闭合边界内PathIterator

 

4.使用凸包算法把指定Path2D转换成一块大的覆盖面

凸包（Convex Hull）是一个计算几何（图形学）中的概念。在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1，...Xn)的凸组合来构造.在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。

代码示例：

/**
 * 凸包算法
 *
 * @author wangnian
 */
public class ConvexUtil {

    private static int MAX_ANGLE = 4;
    private double currentMinAngle = 0;
    private List<PointDouble> hullPointList;
    private List<Integer> indexList;
    private List<PointDouble> pointDoubles;
    private int firstIndex;

    /**
     * 获取凸包算法之后的坐标
     *
     * @param pointDoubleList
     * @return
     */
    public static List<PointDouble> getConvexPoint(List<PointDouble> pointDoubleList) {
        //排重一下
        pointDoubleList = pointDoubleList.stream().distinct().collect(Collectors.toList());
        ConvexUtil convexUtil = new ConvexUtil(pointDoubleList);
        return convexUtil.calculateHull();
    }

    public ConvexUtil() {

    }

    public ConvexUtil(List<PointDouble> pointDoubleList) {
        this.hullPointList = new LinkedList<>();
        this.indexList = new LinkedList<>();
        this.pointDoubles = pointDoubleList;
        firstIndex = getFirstPoint(pointDoubleList);
        addToHull(firstIndex);
    }


    public List<PointDouble> calculateHull() {
        for (int i = getNextIndex(firstIndex); i != firstIndex; i = getNextIndex(i)) {
            addToHull(i);
        }
        return showHullPoints();
    }

    private void addToHull(int index) {
        indexList.add(index);
        hullPointList.add(pointDoubles.get(index));
    }

    private List<PointDouble> showHullPoints() {
        Iterator<PointDouble> itPoint = hullPointList.iterator();
        List<PointDouble> resultList = new ArrayList<>();
        while (itPoint.hasNext()) {
            PointDouble p = itPoint.next();
            resultList.add(new PointDouble(p.getX(), p.getY()));
        }
        return resultList;
    }

    private int getNextIndex(int currentIndex) {
        double minAngle = MAX_ANGLE;
        double pseudoAngle;
        int minIndex = 0;
        for (int i = 0; i < pointDoubles.size(); i++) {
            if (i != currentIndex) {
                pseudoAngle = getPseudoAngle(pointDoubles.get(i).getX() - pointDoubles.get(currentIndex).getX(),
                        pointDoubles.get(i).getY() - pointDoubles.get(currentIndex).getY());

                if (pseudoAngle >= currentMinAngle && pseudoAngle < minAngle) {
                    minAngle = pseudoAngle;
                    minIndex = i;
                } else if (pseudoAngle == minAngle) {
                    if ((abs(pointDoubles.get(i).getX() - pointDoubles.get(currentIndex).getX()) >
                            abs(pointDoubles.get(minIndex).getX() - pointDoubles.get(currentIndex).getX()))
                            || (abs(pointDoubles.get(i).getY() - pointDoubles.get(currentIndex).getY()) >
                            abs(pointDoubles.get(minIndex).getY() - pointDoubles.get(currentIndex).getY()))) {
                        minIndex = i;
                    }
                }
            }

        }
        currentMinAngle = minAngle;
        return minIndex;
    }

    private double getPseudoAngle(double dx, double dy) {
        if (dx > 0 && dy >= 0) {
            return dy / (dx + dy);
        }
        if (dx <= 0 && dy > 0) {
            return 1 + (abs(dx) / (abs(dx) + dy));
        }
        if (dx < 0 && dy <= 0) {
            return 2 + (dy / (dx + dy));
        }
        if (dx >= 0 && dy < 0) {
            return 3 + (dx / (dx + abs(dy)));
        }
        throw new Error("坐标有重复");
    }

    private int getFirstPoint(List<PointDouble> pointDoubleList) {
        int minIndex = 0;
        for (int i = 1; i < pointDoubleList.size(); i++) {
            if (pointDoubleList.get(i).getY() < pointDoubleList.get(minIndex).getY()) {
                minIndex = i;
            } else if ((pointDoubleList.get(i).getY() == pointDoubleList.get(minIndex).getY())
                    && (pointDoubleList.get(i).getX() < pointDoubleList.get(minIndex).getX())) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    public static void main(String[] args) {
        List<PointDouble> resultList = new ArrayList() {{
            add(new PointDouble(1.0, 4.0));
            add(new PointDouble(1.0, 4.0));
            add(new PointDouble(2.0, 2.0));
            add(new PointDouble(2.0, 2.0));
            add(new PointDouble(3.0, 3.0));
            add(new PointDouble(3.0, 3.0));
            add(new PointDouble(4.0, 4.0));
            add(new PointDouble(4.0, 4.0));
            add(new PointDouble(4.0, 2.0));
            add(new PointDouble(4.0, 2.0));
            add(new PointDouble(5.0, 2.0));
            add(new PointDouble(5.0, 2.0));
        }};
        System.out.println(ConvexUtil.getConvexPoint(resultList));

    }

 

5. 根据当前地图窗口查询所有相交Path2D

  根据当前地图显示范围获取到northeast东北角和southwest西南角的坐标位置,查询相交的所有Path2D

高德地图示例地址:

https://lbs.amap.com/api/javascript-api/example/map/map-bounds/?sug_index=2

 

代码示例

//获取西南的纬度  也就是X
double lng = southwest.getLng();
//获取西南的经度  也就是Y
double lat = southwest.getLat();
//东北角的X减去西南角的X ，得到宽
double w = northeast.getLng() - southwest.getLng();
//东北角的Y减去西南角的Y ，得到高
double h = northeast.getLat() - southwest.getLat();


//判断是否相交
Path2D.intersects(lng, lat, w, h)

以上用到了的方法详解

intersects(double x, double y, double w, double h)

测试内部是否与Shape指定矩形区域的内部相交。

 

提示: 以上只是一些关键的局部代码，在实际应用中，需要将所有的范围对象按照凸包算法或者其他纬度的行政区域进行分类并缓存，方便快速遍历查询。

 

欢迎大家关注凯京技术团队  https://my.oschina.net/keking  很多专业的干活技术分享。