java 寻找最大凸多边形

系统管理员 2021-09-28 12:26 349阅读 0赞

最近再次用到的一段代码，在此记录一下。  
网上找了一圈，实在是找不到原文了。

算法大概是：先定位最左边并且最上面的点，计算这个点与其他点的夹角，找出顺时针转角最小的。按此规则依次递归，直到再次回到原点。

import java.util.ArrayList;
    import java.util.List;
    
    public class Test83 { 
    
    	public static void main(String[] args) { 
    		List<Point> points = new ArrayList<Test83.Point>();
    		Test83 util = new Test83();
    		Point a1 = util.new Point(0d, 0d);
    		Point a2 = util.new Point(0d, 1d);
    		Point a3 = util.new Point(0d, 3d);
    		Point a4 = util.new Point(0d, 2d);
    		Point a5 = util.new Point(0d, 4d);
    		Point a6 = util.new Point(1d, 1d);
    		Point a7 = util.new Point(0d, 1d);
    		points.add(a1);
    		points.add(a2);
    		points.add(a3);
    		points.add(a4);
    		points.add(a5);
    		points.add(a6);
    		points.add(a7);
    		List<Point> result = util.getPolygonByPoints(points);
    		for(int i = 0; i < result.size(); i++){ 
    			System.out.println(result.get(i).x + " ; " + result.get(i).y);
    		}
    	}
    	
    	private List<Point> getPolygonByPoints(List<Point> points){ 
    		
    	    if (null == points || points.size() == 0) { 
    	        return null;
    	    }
    
    	    Point corner = findStartPoint(points);
    	    if (null == corner) { 
    	        return null;
    	    }
    
    	    double minAngleDif, oldAngle = 2 * Math.PI;
    	    double oldLen = 0;
    
    	    List<Point> bound = new ArrayList(points.size());
    	    do { 
    	        minAngleDif = 2 * Math.PI;
    
    	        bound.add(corner);
    
    	        Point nextPoint = corner;
    	        double nextAngle = oldAngle;
    
    	        for (int i = 0;  i < points.size(); i++) { 
    	            if (points.get(i).founded) {  // 已被加入边界链表的点
    	                continue;
    	            }
    
    	            if (points.get(i).x == corner.x && points.get(i).y == corner.y) {  // 重合点
    	                /*if (!p.equals(bound.getFirst())) { p.founded = true; }*/
    	                continue;
    	            }
    
    	            double currAngle = angleOf(corner, points.get(i)); /* 当前向量与x轴正方向的夹角 */
    	            double angleDif = reviseAngle(oldAngle - currAngle); /* 两条向量之间的夹角（顺时针旋转的夹角） */
    	            
    
    	            if (angleDif < minAngleDif || (angleDif == minAngleDif && calLineLen(corner, points.get(i)) > oldLen)) { 
    	                minAngleDif = angleDif;
    	                nextPoint = points.get(i);
    	                nextAngle = currAngle;
    	                oldLen = calLineLen(corner, points.get(i));
    	            }
    	        }
    
    	        oldAngle = nextAngle;
    	        corner = nextPoint;
    	        corner.founded = true;
    	    } while (corner != bound.get(0)); /* 判断边界是否闭合 */
    
    	    return bound;
    	}
    	
    	/** * 查找起始点（保证y最大的情况下、尽量使x最小的点） * @param src * @return */
    	private Point findStartPoint(List<Point> src){ 
    		if (null == src || src.size() == 0) { 
    	        return null;
    	    }
    		
    		Point p = src.get(0);
    
    	    for(int i = 0; i < src.size(); i++){ 
    	        if (src.get(i).y > p.y || (src.get(i).y == p.y && src.get(i).x < p.x)) {  /* 找到最靠上靠左的点 */
    	            p = src.get(i);
    	        }
    	    }
    	    return p;
    	}
    	/** * 计算两点组成的向量与x轴正方向的向量角 * @param s * @param d * @return */
    	private static double angleOf(Point s, Point d){ 
    	    double dist = calLineLen(s, d);
    
    	    if (dist <= 0) { 
    	        return 0d;
    	    }
    
    	    double x = d.x - s.x; // 直角三角形的直边a
    	    double y = d.y - s.y; // 直角三角形的直边b
    
    	    if (y >= 0.) {  /* 1 2 象限 */
    	        return Math.acos(x / dist);
    	    } else {  /* 3 4 象限 */
    	        return Math.acos(-x / dist) + Math.PI;
    	    }
    	}
    	/** * 求两点之间的长度 * @param s * @param d * @return */
    	private static double calLineLen(Point ws, Point en){ 
    		if (null == ws || null == en) { 
    	        return 0d;
    	    }
    
    	    if (ws==en) { 
    	        return 0d;
    	    }
    	    double a = Math.abs(ws.x - en.x); // 直角三角形的直边a
    	    double b = Math.abs(ws.y - en.y); // 直角三角形的直边b
    
    	    double min = Math.min(a, b); // 短直边
    	    double max = Math.max(a, b); // 长直边
    
    	    /** * 为防止计算平方时float溢出，做如下转换 * √(min²+max²) = √((min/max)²+1) * abs(max) */
    	    double inner = min / max;
    	    return Math.sqrt(inner * inner + 1.0) * max;
    	}
    	/** * 修正角度到 [0, 2PI] * @param angle * @return */
    	private static double reviseAngle(double angle){ 
    		while (angle < 0.) { 
    	        angle += 2 * Math.PI;
    	    }
    	    while (angle >= 2 * Math.PI) { 
    	        angle -= 2 * Math.PI;
    	    }
    	    return angle;
    	}
    	
    	public class Point{ 
    		Double x;
    		Double y;
    		boolean founded = false;
    		Point(Double x, Double y){ 
    			this.x = x;
    			this.y = y;
    		}
    		Point(String x, String y){ 
    			this(Double.valueOf(x), Double.valueOf(y));
    		}
    		public Double getX() { 
    			return x;
    		}
    		public Double getY() { 
    			return y;
    		}
    		public boolean isFounded() { 
    			return founded;
    		}
    		
    	}
    
    }