多边型无序点排序（地图绘制多边形）

谁借莪１个温暖的怀抱￠ 2022-04-11 02:18 402阅读 1赞

从这些点里随便选一个（比如最左边最下面哪一个）
    然后以这个点为原点按极角排序（极角相同按距离排序）

##  ##

## 前言 ##

任务需求要做一个区域高亮的功能，用到地图，想到了高德地图的多边形API，但是多边形顶点的顺序是要有序的，需求是无序，在API查找无果的情况下，只能手动实现点集合排序。

## 排序步骤 ##

1.  计算所有坐标的中心点（将x坐标相加处以数量，将y坐标相加处以数量）
2.  计算所有点与中点的夹角（水平夹角或者垂直夹角）
3.  按夹角大小排序

## 代码实现 ##

*  收集3个以上的坐标点放入到集合中`private ArrayList<LatLng> list;`
 *  计算中心点坐标

double plusX = 0, plusY = 0;
            for (LatLng latLng : list) {
                plusX += latLng.latitude;
                plusY += latLng.longitude;
            }
            center = new LatLng(plusX / list.size(), plusY / list.size());

*  通过工具方法获得2个点坐标对应的在垂直方向上的角度

/**
         * @param lat_a 纬度1
         * @param lng_a 经度1
         * @param lat_b 纬度2
         * @param lng_b 经度2
         * @return
         */
        private double getAngle1(double lat_a, double lng_a, double lat_b, double lng_b) {
    
            double y = Math.sin(lng_b - lng_a) * Math.cos(lat_b);
            double x = Math.cos(lat_a) * Math.sin(lat_b) - Math.sin(lat_a) * Math.cos(lat_b) * Math.cos(lng_b - lng_a);
            double brng = Math.atan2(y, x);
    
            brng = Math.toDegrees(brng);
            if (brng < 0)
                brng = brng + 360;
            return brng;
        }

*  将坐标数组转换为`HashMap<Integer, ArrayList<Object>>` 映射为`下标->(角度,坐标)`

HashMap<Integer, ArrayList<Object>> mapAll = new HashMap<>();
            for (int i = 0; i < list.size(); i++) {
                //第一个放经纬度 第二个放角度
                ArrayList<Object> objList = new ArrayList<>();
                objList.add(list.get(i));
                objList.add(getAngle1(center.latitude, center.longitude,
                        list.get(i).latitude, list.get(i).longitude));
                mapAll.put(i, objList);
            }

*  采用冒泡排序法对角度进行排序

ArrayList<Object> temp = new ArrayList<>();
            int size = mapAll.size();
            for (int i = 0; i < size - 1; i++) {
                for (int j = 0; j < size - 1 - i; j++) {
                    if (Double.parseDouble(mapAll.get(j).get(1).toString()) >
                            Double.parseDouble(mapAll.get(j + 1).get(1).toString()))  //交换两数位置
                    {
                        temp = mapAll.get(j);
                        mapAll.put(j, mapAll.get(j + 1));
                        mapAll.put(j + 1, temp);
                    }
                }
            }

*  生成新的顺时针的坐标点集合

list.clear();
            for (Integer integer : mapAll.keySet()) {
                if (mapAll.get(integer).get(0) instanceof LatLng) {
                    list.add((LatLng) mapAll.get(integer).get(0));
                }
            }

## 高德功能，将多点形成的多边形显示在一个屏幕上 ##

for (int i = 0; i < list.size(); i++) {
         boundsBuilder.include(list.get(i));//把所有点都include进去（LatLng类型）
      }
     aMap.animateCamera(CameraUpdateFactory.newLatLngBounds(boundsBuilder.build(), 100));//第二个参数为四周间隔

作者：超神的菠萝  
链接：https://www.jianshu.com/p/dc8fd3403f6d  
來源：简书  
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。