convexHull实现

// 计算转向角度，以y轴正向为极坐标顺时针转动，角度限制在0~360°之间
public static double calculateBearingToPoint(double currentBearing, int currentX, int currentY,
                                                 int targetX, int targetY) {
        double X = targetX - currentX, Y = targetY - currentY , targetAngle ;
        
        if( X == 0 ) {
            if( Y >= 0 )
                targetAngle = - currentBearing;
            else
                targetAngle =  180 - currentBearing;
        }
        else {
            if( X > 0 ) {
                if( Y >= 0 )
                    targetAngle = 90 - currentBearing - 180 * Math.atan( Y/X ) / Math.PI ;
                else
                    targetAngle = 90 - currentBearing - ( 360 + 180 * Math.atan( Y/X ) / Math.PI );
            }
            else {
                targetAngle = 90 - currentBearing - ( 180 + 180 * Math.atan( Y/X ) / Math.PI );
            }
        }
        
        if( targetAngle - 360.0 >= 0 )
            return targetAngle - 360.0;
        else {
            if( targetAngle + 360.0 <= 0 )
                return targetAngle + 720.0;
            else {
                if ( targetAngle < 0 )
                    return targetAngle + 360.0;
                else
                    return targetAngle;
                }
            }
    }


convexHull// 主函数
public static Set<Point> convexHull(Set<Point> point) {
        
        Iterator<Point> it = point.iterator() ;
        HashSet<Point> HullHashSet = new HashSet<>();
        
        if(point.isEmpty())  {                    //点集为空，返回空集
            return HullHashSet ;
        }
        
        Point first_point = it.next();            //找到最左点
        while(it.hasNext()) {
            Point pr = it.next() ;
            if (pr.x() < first_point.x() ) {
                first_point = pr ;
            }
        }
        
        HullHashSet.add(first_point);            //凸包中加入最左点
        point.remove(first_point);                //剩余点集中删除最左点
        
        Point this_point = first_point;            //当前点
        Point next_point;                        //下一个点
        Point add_point = this_point;            //加入凸包中的点   
        double min_angle;                        //最小转动角度
        double next_angle;                        //当前转动角度
        
        do {
            it = point.iterator();
            min_angle = 360;
            
            while(it.hasNext()) {
                next_point = it.next();
                next_angle = calculateBearingToPoint(0 , (int)this_point.x() , (int)this_point.y() , (int)next_point.x() ,(int) next_point.y() );
                if(next_angle < min_angle) {    //选取角度最小的点
                    add_point = next_point;
                    min_angle = next_angle;    
                }
                else if( next_angle == min_angle ) { //若角度相同，选取距离最远的点
                    if(Math.pow((this_point.x()-next_point.x()), 2) + Math.pow((this_point.y()-next_point.y()), 2) >
                        Math.pow((this_point.x()-add_point.x()), 2) + Math.pow((this_point.y()-add_point.y()), 2)) {
                        add_point = next_point ;
                    }
                }
            }
            
            this_point = add_point;
            HullHashSet.add(add_point);    //加入凸包
            point.remove(add_point);    //从剩余点集中删除
            point.add(first_point);        //加入初始点，否则没有循环结束条件
            
        }while(add_point != first_point);
     
        point.addAll(HullHashSet);
        return HullHashSet ;
    }