多边形等距离外扩

实现多边形形成的多边形进行等距外扩或收缩的算法实现

涉及技术

• 腾讯地图
• jdk1.8

问题描述

开发一款应用，前端在地图上标记经纬度坐标点集合形成一个多边形，现需要在后端将多边形做一个等距外扩或者收缩。

在网上查了好多的算法，经过尝试验证，在小经度多边形进行收缩外扩都或多或少存在一些问题，因此自己参考写出了

一个多边形外扩收缩的算法。

JAVA代码实现

坐标点实体（Point）

/**
 * 地图上一个点的经纬度
 *
 * @author yanggl
 * @version 1.0
 * @date 2022/5/9 15:03
 */
public class Point implements Serializable {

    private static final long serialVersionUID = 45122365987322547L;

    /**
     * 经度
     */
    private Double longitude;

    /**
     * 纬度
     */
    private Double latitude;

    public Double getLongitude() {
        return longitude;
    }

    public void setLongitude(Double longitude) {
        this.longitude = longitude;
    }

    public Double getLatitude() {
        return latitude;
    }

    public void setLatitude(Double latitude) {
        this.latitude = latitude;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("{");
        sb.append("longitude=").append(longitude);
        sb.append(", latitude=").append(latitude);
        sb.append('}');
        return sb.toString();
    }

}

向量工具类 (VectorUtil)

/**
 * 向量工具类
 *
 * @author yanggl
 * @version 1.0
 * @date 2022/7/8 10:29
 */
public class VectorUtil {

    /**
     * 向量求模数
     */
    public static double norm(Point point) {
        return Math.sqrt(point.getLongitude() * point.getLongitude() + point.getLatitude() * point.getLatitude());
    }

    /**
     * 向量加法
     */
    public static Point add(Point point1, Point point2) {
        Point point = new Point();
        point.setLongitude(point1.getLongitude() + point2.getLongitude());
        point.setLatitude(point1.getLatitude() + point2.getLatitude());
        return point;
    }

    /**
     * 向量减法
     */
    public static Point sub(Point point1, Point point2) {
        Point point = new Point();
        point.setLongitude(point1.getLongitude() - point2.getLongitude());
        point.setLatitude(point1.getLatitude() - point2.getLatitude());
        return point;
    }

    /**
     * 向量乘法
     */
    public static Point mul(Point p, double d) {
        Point point = new Point();
        point.setLongitude(p.getLongitude() * d);
        point.setLatitude(p.getLatitude() * d);
        return point;
    }

    /**
     * 向量叉乘
     */
    public static double cross(Point p1, Point p2) {
        return p1.getLongitude() * p2.getLatitude() - p1.getLatitude() * p2.getLongitude();
    }

}

核心工具类 (DistanceUtil)

/**
 * 工具类
 *
 * @author yanggl
 * @version 1.0
 * @date 2022/7/8 10:23
 */
public class DistanceUtil {

    /**
     * 操作多边形扩张/收缩
     *
     * @param points 待扩/收缩张多边形
     * @param dist   距离 正数扩张，负数收缩
     * @return 扩张/收缩后的多边形
     */
    public static List<Point> expansion(List<Point> points, double dist) {
        if (points.size() < 3) {
            throw new RuntimeException("not enough 3 point");
        }
        List<Point> npList = new LinkedList<>();
        List<Double> lngList = new LinkedList<>();
        List<Double> latList = new LinkedList<>();

        for (Point point : points) {
            lngList.add(point.getLongitude());
            latList.add(point.getLatitude());
        }
        Double minLng = Collections.min(lngList);
        Double minLat = Collections.min(latList);

        for (Point point : points) {
            Point p = new Point();
            p.setLongitude(point.getLongitude() - minLng);
            p.setLatitude(point.getLatitude() - minLat);
            npList.add(p);
        }

        List<Point> list = enlarge(npList, dist);
        LinkedList<Point> resultList = new LinkedList<>();
        for (Point point : list) {
            Point np = new Point();
            np.setLongitude(point.getLongitude() + minLng);
            np.setLatitude(point.getLatitude() + minLat);
            resultList.add(np);
        }

        return resultList;
    }

    /**
     * 多边形外扩/收缩
     */
    private static List<Point> enlarge(List<Point> points, double dist) {
        LinkedList<Point> resultList = new LinkedList<>();
        int size = points.size();
        double angle = dist * dmi();
        angle = isConvex(points) ? angle : -angle;

        for (int i = 0; i < size; i++) {
            Point pi = points.get(i);
            Point v1 = VectorUtil.sub(points.get((i - 1 + size) % size), pi);
            Point v2 = VectorUtil.sub(points.get((i + 1) % size), pi);
            double norm1 = VectorUtil.norm(v1);
            double norm2 = VectorUtil.norm(v2);

            if (norm1 <= 0 || norm2 <= 0) {
                // 剔除重复点（或距离极近的点）
                points.remove(i);
                return enlarge(points, dist);
            }

            Point normalizeV1 = VectorUtil.mul(v1, 1 / norm1);
            Point normalizeV2 = VectorUtil.mul(v2, 1 / norm2);
            double sinTheta = VectorUtil.cross(normalizeV1, normalizeV2);
            Point qi = VectorUtil.add(pi, VectorUtil.mul(VectorUtil.add(normalizeV1, normalizeV2), angle / sinTheta));
            resultList.add(qi);
        }

        return resultList;
    }

    /**
     * 计算1米代表的角度 这里只是近似计算，事实上随着纬度的变化其变动范围将受到影响
     */
    private static double dmi() {
        double s = 6378.137 * 1000;
        return 1 / (Math.PI / 180 * s);
    }

    /**
     * 判断是否凸多边形
     */
    private static boolean isConvex(List<Point> points) {
        double area = 0;
        Point p1 = VectorUtil.sub(points.get(1), points.get(0));
        Point p2;
        for (int i = 2; i < points.size(); i++) {
            p2 = VectorUtil.sub(points.get(i), points.get(0));
            area += VectorUtil.cross(p1, p2);
            p1 = p2;
        }
        return area > 0;
    }

    /**
     * 多边形周长
     */
    private static double perimeter(List<Point> points) {
        int size = points.size();
        double perimeter = 0.0d;
        Point point;
        for (int i = 0; i < size; i++) {
            point = points.get(i);
            perimeter += VectorUtil.norm(VectorUtil.sub(points.get((i - 1 + size) % size), point));
        }
        return perimeter;
    }

}

经测试，对于小经度多边形的外扩是能够正常的。