改变自 几何算法：点集合构造简单多边形 - AndyZeng - 博客园  的 java版

package util.polygon_sort;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class PolygonSort{

    public static void main(String[] args)  {
        
        /*
        Point p1 = new Point(53.0418333,24.9208333);//经度在前，纬度在后。
        Point p2 = new Point(53.0446667,24.9175); 
        Point p3 = new Point(53.0448333,24.9045);
        Point p4 = new Point(53.0481667,24.9211667);
        Point p5 = new Point(53.057,24.8946667);
        Point p6 = new Point(53.0568333,24.8938333); 
        Point p7 = new Point(54.0568333,24.9038333); 

        Point[] pList = { p1,p2,p3,p4,p5,p6,p7 };   
        
        Map sortedMap = sort(pList) ;
        for (Map.Entry entry:sortedMap.entrySet() ){
            System.out.println("angle=" + entry.getKey() +",坐标等于 " + entry.getValue().toString() );
        }
        */
        String s = "POLYGON((63.2505 24.6003333,62.5005 24.6003333,62.5005 24.3503333,63.2505 24.3503333))";
        s = s.substring("POLYGON((".length(),s.lastIndexOf("))"));
        String[] ar = s.split(",");
        Map  sortedMap2 = sort(ar) ;
        for (Map.Entry entry:sortedMap2.entrySet() ){
            System.out.println("angle=" + entry.getKey() +",坐标等于 " + entry.getValue().toString() );
        }        
    }
  
    /*    https://www.cnblogs.com/andyzeng/p/3754005.html
     *     点集合构造 简单多边形，排序 方向角，达到：边与边无交叉。
     */
    public static Map sort(Point[] pList) {
        
        int minIdx = findMinLat(pList);
        
        Map bMap = getAngleMap(pList,minIdx);
        Map sortedMap = new TreeMap(new MapKeyComparator());
        sortedMap.putAll(bMap);
        
        /*double[] angle = getAngleList(pList,minIdx);
        /double[] sortedAngle = ArraySort.bubbleSort(angle,"asc");*/
        return sortedMap;
    }

    /*
     * 计算每个点到最小纬度点的angle
     */
    public static Map  getAngleMap(Point[] pList,int minIdx) {
        Map map = new HashMap();
        double angle = 0;
        for(int i=0;i
            angle = 0;
            if( i != minIdx ) {
                angle = aTan2(pList[minIdx],pList[i]);
                System.out.println( (i+1) + "->" +  (minIdx+1) + ":角度"+  angle);    
            }
            map.put(angle,pList[i]);
        }
        return map;
    }
    
    /*
    public static double[]  getAngleList(Point[] pList,int minIdx) {
        double[] angleList = new double[pList.length];
        for(int i=0;i
            if( i != minIdx ) {
                angleList[i] = aTan2(pList[minIdx],pList[i]);
                System.out.println( (i+1) + "->" +  (minIdx+1) + ":角度"+  angleList[i]);    
            }else {
                angleList[i] = 0;
            }
        }
        return angleList;
    }
    */
    /*
     *     找到最小lat的起点point,
     *     起点，在所有的其它点的下面，这样 其它点到起点的角度angle，都为正值（0度~180度），容易排序
     */
    public static int findMinLat(Point[] pList) {
        
        int minIdx = 0;
        double min = 10000000;
        int minIdx2 = -1 ;
        
        for(int i=0;i
            if( pList[i].getLat() < min ) {
                min = pList[i].getLat();
                minIdx = i;
            }else if(pList[i].getLat() == min ) {
                minIdx2 = i;
            }
        }
        //System.out.println( "------第一遍---------最小lat的point的序号 为:  " + (minIdx+1)  + "=数组游标" + minIdx + "+1");
        if( minIdx2 >=0  ) {
            //System.out.println( "------第2遍---------最小lat的point的序号 为:  " + (minIdx+1)  + "=数组游标" + minIdx + "+1");
            if( pList[minIdx2].getLon() > pList[minIdx].getLon() ) {
                return minIdx2;
            }else if(pList[minIdx2].getLon() > pList[minIdx].getLon() ){
                System.out.println( "存在完全相同的点，不正常，手工剔除它们");
                return -1;
            }
        }
        return minIdx;
    }
    
    public static double aTan2(Point p1,Point p2) {//注意这里的aTan2返回degree,not radian
        double x = p2.getLon() - p1.getLon();
        double y = p2.getLat() - p1.getLat();
        //System.out.print(y + "," + x );
        return Math.toDegrees( Math.atan2(y,x) );
    }
    
    /*java的atan2函数学习例子 */
    public static void test()  {
        double d = 45;
        double dR = Math.toRadians(d);//角度 转 弧度
        
        //System.out.println( (d* 180) / Math.PI);
        
        System.out.println( "tag " + d+ "(角)度=弧度：" + dR + "=" + Math.tan(dR) + "，约等于1, Math.atan(dR)= " + Math.atan(dR));//0.9999999999999999  约 等于 1
        //System.out.println( "atag45度=" + Math.atan(dR) + "，这个非常奇怪不等于 Math.tan ！！");//0.9999999999999999
        System.out.println( "java.lang.Math.atan2()是已知一个角的正切值（也就是 y/x），求该角的弧度值。比如：Math.atan2(1,1) = " 
        + Math.atan2(1,1) + ",转换成角度=" + Math.toDegrees( Math.atan2(1,1)  ));//0.9999999999999999
        
        double dR30 = Math.toRadians(30);
        
        System.out.println("---------");
        System.out.println("正玄sin 30度=1/2=" + Math.sin(dR30) + "");//
        System.out.println("反正玄 asin 30度=2/1=" + Math.asin(dR30) + ",1/Math.sin(dR30)=" + (1/Math.sin(dR30) ) );//

        System.out.println("---------");
        System.out.println("cos 30 度=sqrt(3)/2=" + Math.cos(dR30) + "，  而手工计算(Math.sqrt(3)/2)= " + (Math.sqrt(3)/2) 
                );//
        
        System.out.println("tag 30 度=1/sqrt(3)=" +Math.tan(dR30) + "，  而手工计算(1/Math.sqrt(3))= " + (1/Math.sqrt(3)));//    
        System.out.println(Math.atan(dR30) + ",squar(3)/1=" + Math.sqrt(3));//   
        
        System.out.println("---------");
        
        Point p1 = new Point(0,0);
        Point p2 = new Point(1,1);
        Point p3 = new Point(-1,Math.sqrt(3));
        System.out.println(  aTan2(p1,p2) + ",角度=" + Math.toDegrees(aTan2(p1,p2) ));
        System.out.println(  aTan2(p1,p3) + ",角度=" + Math.toDegrees(aTan2(p1,p3) ));
    }
    

    public static Map sort(String[] strList) {
        
        Point[] pList = new Point[strList.length];
        
        Point p = null;
        double lat,lon;
        
        for( int i=0;i
            lat = Double.parseDouble(strList[i].split(" ")[0]);
            lon = Double.parseDouble(strList[i].split(" ")[1]);

            p = new Point(lat,lon);
            pList[i] = p;
            System.out.println( (i+1) + " 点：" + lat + " " + lon );
            
        }
        
        return sort(pList);
    }      
}

class MapKeyComparator implements Comparator{
    @Override
    public int compare(Double angle1, Double angle2) {
        if( angle1>angle2 ) {
            return 1;
        }else if(angle1 < angle2 ){
            return -1;
        }else{
            return 0;
        }
    }
}

package util.polygon_sort;public class Point {double lat;double lon;public Point(double lon,double lat) {//经度在前，纬度在后。this.lat = lat;this.lon = lon;}public Point(String lon,String lat) {//经度在前，纬度在后。this.lat = Double.parseDouble(lat);this.lon = Double.parseDouble(lon);}	public void setLat(double lat) {this.lat = lat;}public double getLat() {return lat;}public void setLon(double lon) {this.lon = lon;}public double getLon() {return lon;} @Overridepublic String toString() {return lon + " " + lat ;}   
}