google/amap folygon 多边形交叉排序

多坐标点凸包检测排序

  最近在做一个自助选房项目，涉及到地图绘制多边形的场景
  由于多边形坐标点有可能是乱序，会导致绘制出的多边形会交叉
  Grahanm's Scan实现代码也比较简单

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Grahanm's Scan 凸包算法 排序
 * @author gary.wang
 * @version 2020/9/4 12:06
 **/
public class LatLongSort {

    // 用于存储起始点
    private CustomPoint centerCustomPoint;

    // 叉积
    public static double CJ(double x1, double y1, double x2, double y2) {
        return x1 * y2 - x2 * y1;
    }

    // 计算向量(p1->p2)和(p2->p3)两个向量的叉积
    public static double compare(CustomPoint p1, CustomPoint p2, CustomPoint p3) {
        return CJ(p2.x - p1.x, p2.y - p1.y, p3.x - p2.x, p3.y - p2.y);
    }

    /**
     * 凸包算法解决坐标顺序导致的地图多边形交叉
     * Grahanm's Scan
     *
     * @param CustomPointList
     */
    public List<CustomPoint> grahanmScan(List<CustomPoint> CustomPointList) {

        List<CustomPoint> CustomPoints = new ArrayList<>();
        for (int i = 0; i < CustomPointList.size(); i++) {
            double x = CustomPointList.get(i).x;
            double y = CustomPointList.get(i).y;
            CustomPoint CustomPoint = new CustomPoint(x, y);
            // 找到x,y都最小的点作为起始点
            if (centerCustomPoint == null || centerCustomPoint.y > CustomPoint.y || (centerCustomPoint.y.equals(CustomPoint.y) && centerCustomPoint.x > CustomPoint.x)) {
                centerCustomPoint = CustomPoint;
            }
            CustomPoints.add(CustomPoint);
        }
        // 把起始点拿出去
        CustomPoints.remove(centerCustomPoint);

        // 按照与起始点向量的极角排序
        Collections.sort(CustomPoints, (p1, p2) -> {
            if (Math.atan2(p1.y - centerCustomPoint.y, p1.x - centerCustomPoint.x) != Math.atan2(p2.y - centerCustomPoint.y, p2.x - centerCustomPoint.x)) {
                // atan2可以计算极角
                return Math.atan2(p1.y - centerCustomPoint.y, p1.x - centerCustomPoint.x) < Math.atan2(p2.y - centerCustomPoint.y, p2.x - centerCustomPoint.x) ? -1 : 1;
            }
            // 极角相同与中心点距离越近，则x坐标也就越近
            return Double.valueOf(Math.abs(p1.x - centerCustomPoint.x) - Math.abs(p2.x - centerCustomPoint.x)).intValue();
        });

        // 用数组模拟栈
        CustomPoint[] stack = new CustomPoint[CustomPointList.size()];
        stack[0] = centerCustomPoint;
        // 栈顶指针
        int top = 0;

        // 遍历点集中每一个点
        for (int i = 0; i < CustomPoints.size(); ) {
            //如果栈中元素大于等于2并且(p2->p3)在(p1->p2)的顺时针方向，栈顶的点抛出
            while (top >= 1 && compare(stack[top - 1], stack[top], CustomPoints.get(i)) < 0) top--;
            // 找到在逆时针方向的点了，将p2放入栈顶
            stack[++top] = CustomPoints.get(i++);
        }
        // 输出栈中的所有点就是凸包上的点
        List<CustomPoint> sortedList=new ArrayList<>();
        for (int i = 0; i <= top; i++) {
            sortedList.add(stack[i]);
        }
        return sortedList;
    }
}