高德地图两个多边形区域检测重叠解决方案

高德地图只提供了javascript的解决方案api，没有提供java sdk的解决方案。

import com.amap.api.maps.model.LatLng;

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

public class AreaOverlapUtil {

    private static boolean isSegmentsIntersect(List l1, List l2) {
        double x1 = (l1.get(0).latitude - l2.get(0).latitude) * (l1.get(1).longitude - l2.get(0).longitude) - (l1.get(0).longitude - l2.get(0).longitude) * (l1.get(1).latitude - l2.get(0).latitude);
        double x2 = (l1.get(0).latitude - l2.get(1).latitude) * (l1.get(1).longitude - l2.get(1).longitude) - (l1.get(0).longitude - l2.get(1).longitude) * (l1.get(1).latitude - l2.get(1).latitude);
        if (x1 * x2 >= 0) {
            return false;
        }
        double y1 = (l2.get(0).latitude - l1.get(0).latitude) * (l2.get(1).longitude - l1.get(0).longitude) - (l2.get(0).longitude - l1.get(0).longitude) * (l2.get(1).latitude - l1.get(0).latitude);
        double y2 = y1 + x1 - x2;
        return !(y1 * y2 >= 0);
    }

    private static boolean isPolygonsIntersect(List p1, List p2) {
        int il = p1.size();
        int jl = p2.size();
        for (int i = 0; i < p1.size(); i++) {
            for (int j = 0; j < p2.size(); j++) {
                List l1 = new ArrayList<>();
                l1.add(p1.get(i));
                l1.add(p1.get(i == il - 1 ? 0 : i + 1));
                List l2 = new ArrayList<>();
                l2.add(p2.get(j));
                l2.add(p2.get(j == jl - 1 ? 0 : j + 1));
                if (isSegmentsIntersect(l1, l2)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isPointInPolygonBidirectional(List p1, List p2) {
        for (LatLng latLng : p1) {
            if (isPointInPolygonBidirectional(latLng, p2)) {
                return true;
            }
        }
        for (LatLng latLng : p2) {
            if (isPointInPolygonBidirectional(latLng, p1)) {
                return true;
            }
        }
        return false;
    }

    private static boolean isPointInPolygonBidirectional(LatLng point, List polygon) {
        int nCross = 0;
        for (int i = 0; i < polygon.size(); i++) {
            LatLng p1 = polygon.get(i);
            LatLng p2 = polygon.get((i + 1) % polygon.size());
            if (p1.longitude == p2.longitude) {
                continue;
            }
            if (point.longitude < Math.min(p1.longitude, p2.longitude)) {
                continue;
            }
            if (point.longitude >= Math.max(p1.longitude, p2.longitude)) {
                continue;
            }
            double x = (point.longitude - p1.longitude) * (p2.latitude - p1.latitude) / (p2.longitude - p1.longitude) + p1.latitude;
            if (x > point.latitude) {
                nCross++;
            }
        }
        return (nCross % 2 == 1);
    }

    /**
     * 地图区域重叠检测
     *
     * @param p1 经纬度数据
     * @param p2 经纬度数据
     * @return boolean 是否重叠
     */
    public static boolean isPolygonsOverlap(List p1, List p2) {
        return isPolygonsIntersect(p1, p2) || isPointInPolygonBidirectional(p1, p2);
    }
}

测试用例

import com.amap.api.maps.model.LatLng;

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

public class main {

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
        test5();
    }

    public static void test1() {
        // 点位在内部重叠检测
        List s1 = new ArrayList<>();
        s1.add(new LatLng(39.910967, 116.376907));
        s1.add(new LatLng(39.919505, 116.384911));
        s1.add(new LatLng(39.919728, 116.40109));
        s1.add(new LatLng(39.911408, 116.411132));
        s1.add(new LatLng(39.899135, 116.412076));
        s1.add(new LatLng(39.892353, 116.402292));
        s1.add(new LatLng(39.892518, 116.3874));
        s1.add(new LatLng(39.899267, 116.376971));
        List s2 = new ArrayList<>();
        s2.add(new LatLng(39.906602, 116.390233));
        s2.add(new LatLng(39.908668, 116.395254));
        s2.add(new LatLng(39.906667, 116.400661));
        s2.add(new LatLng(39.898589, 116.400962));
        s2.add(new LatLng(39.894855, 116.395769));
        s2.add(new LatLng(39.898049, 116.390147));
        // 开始时间
        long start = System.currentTimeMillis();
        System.out.println("区域在区域内部: " + AreaOverlapUtil.isPolygonsOverlap(s1, s2));
        // 结束时间
        long end = System.currentTimeMillis();
        // 执行时间
        System.out.println("执行时间：" + (end - start) + "ms");
    }

    public static void test2() {
        // 区域重叠检测
        List s1 = new ArrayList<>();
        s1.add(new LatLng(39.96072, 116.309648));
        s1.add(new LatLng(39.96072, 116.483369));
        s1.add(new LatLng(39.846944, 116.482682));
        s1.add(new LatLng(39.861704, 116.313081));

        List s2 = new ArrayList<>();
        s2.add(new LatLng(39.926502, 116.211457));
        s2.add(new LatLng(39.892267, 116.212831));
        s2.add(new LatLng(39.942297, 116.539674));
        s2.add(new LatLng(39.907543, 116.547227));
        // 开始时间
        long start = System.currentTimeMillis();
        System.out.println("区域重叠但点位不重叠: " + AreaOverlapUtil.isPolygonsOverlap(s1, s2));
        // 结束时间
        long end = System.currentTimeMillis();
        // 执行时间
        System.out.println("执行时间：" + (end - start) + "ms");
    }

    public static void test3() {
        // 无接触检测是否重叠
        List s1 = new ArrayList<>();
        s1.add(new LatLng(39.96072, 116.309648));
        s1.add(new LatLng(39.96072, 116.483369));
        s1.add(new LatLng(39.846944, 116.482682));
        s1.add(new LatLng(39.861704, 116.313081));
        List s2 = new ArrayList<>();
        s2.add(new LatLng(39.997026, 116.501908));
        s2.add(new LatLng(39.975982, 116.521134));
        s2.add(new LatLng(39.988609, 116.55684));
        s2.add(new LatLng(40.018589, 116.529374));
        // 开始时间
        long start = System.currentTimeMillis();
        System.out.println("区域完全不重叠: " + AreaOverlapUtil.isPolygonsOverlap(s1, s2));
        // 结束时间
        long end = System.currentTimeMillis();
        // 执行时间
        System.out.println("执行时间：" + (end - start) + "ms");
    }

    public static void test4() {
        List s1 = new ArrayList<>();
        s1.add(new LatLng(40.126878,116.262566));
        s1.add(new LatLng(40.126989,116.262899));
        s1.add(new LatLng(40.126898,116.262931));
        s1.add(new LatLng(40.126783,116.262588));
        List s2 = new ArrayList<>();
        s2.add(new LatLng(40.126669,116.262368));
        s2.add(new LatLng(40.12671,116.262459));
        s2.add(new LatLng(40.126632,116.262405));
        s2.add(new LatLng(40.126665,116.262497));
        // 开始时间
        long start = System.currentTimeMillis();
        System.out.println("测试4: " + AreaOverlapUtil.isPolygonsOverlap(s1, s2));
        // 结束时间
        long end = System.currentTimeMillis();
        // 执行时间
        System.out.println("执行时间：" + (end - start) + "ms");
    }

    public static void test5() {
        List s1 = new ArrayList<>();
        s1.add(new LatLng(40.126878,116.262566));
        s1.add(new LatLng(40.126989,116.262899));
        s1.add(new LatLng(40.126898,116.262931));
        s1.add(new LatLng(40.126783,116.262588));
        List s2 = new ArrayList<>();
        s2.add(new LatLng(40.127087,116.262523));
        s2.add(new LatLng(40.127222,116.262604));
        s2.add(new LatLng(40.126521,116.262845));
        s2.add(new LatLng(40.126578,116.262985));
        // 开始时间
        long start = System.currentTimeMillis();
        System.out.println("测试5: " + AreaOverlapUtil.isPolygonsOverlap(s1, s2));
        // 结束时间
        long end = System.currentTimeMillis();
        // 执行时间
        System.out.println("执行时间：" + (end - start) + "ms");
    }

}

执行效果