欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

软件构造Lab1-ConvexHulls

程序员文章站 2024-02-09 16:07:22
...

要求如下:
/**
* Given a set of points, compute the convex hull, the smallest convex set that contains all the points
* in a set of input points. The gift-wrapping algorithm is one simple approach to this problem, and
* there are other algorithms too.
*
* @param points a set of points with xCoords and yCoords. It might be empty, contain only 1 point, two points or more.
* @return minimal subset of the input points that form the vertices of the perimeter of the convex hull
*/
意思就是说,给你一堆点,要你在这些点里找到最外面的那一圈,这个其实比较简单,流程如下:

  1. 如果点的个数小于4,直接返回点集,否则:
  2. 找到当前最左下的点为起始点和终结点,并加入点集
  3. 执行如下循环
    计算当前点到其余每个点的转角度数并遍历 这些点中距离当前点最远的那个点即为下一个要找的点 以该点为当前点,并将其加入集合
  4. 直到终结点等于起始点,返回点集

代码如下,还是比较简单的

public static Set<Point> convexHull(Set<Point> points) {
		Point pointNow;
    	Point pointNext = null;
    	Point pointMin = null;
    	Point[] pointsArr = points.toArray(new Point[0]);
    	int len = pointsArr.length;
    	double bearingNow;
    	double bearingNext;
    	double bearingPre;
    	double lengthNext;
    	Set<Point> pointsNew = new HashSet<Point>();
    	
    	if(len != 0) {
    		if(len < 4)
    			return points;
    		for(int i = 0; i < len; i ++) {
    			if(pointMin == null)
    				pointMin = pointsArr[i];
    			else if(pointMin.x() > pointsArr[i].x()) pointMin = pointsArr[i];
				else if(pointMin.x() == pointsArr[i].x())
					if(pointsArr[i].y() < pointMin.y()) pointMin = pointsArr[i];
    		}
    		pointsNew.add(pointMin);
    		pointNow = pointMin;
    		bearingPre = 0;
    		while(true) {
    			bearingNext = 360;
    			lengthNext = Double.MAX_VALUE;
    			for(int i = 0; i < len; i ++) {
    				if(pointsArr[i].equals(pointNow)) continue;
    				bearingNow = calculateBearingToPoint(bearingPre,(int)pointNow.x(),(int)pointNow.y(),(int)pointsArr[i].x(),(int)pointsArr[i].y());
    				if(bearingNext == bearingNow) {
    					if(lengthNext < (Math.pow(pointsArr[i].x()-pointNow.x(), 2)+Math.pow(pointsArr[i].y()-pointNow.y(), 2))) {
    						lengthNext = Math.pow(pointsArr[i].x()-pointNow.x(), 2)+Math.pow(pointsArr[i].y()-pointNow.y(), 2);
    						pointNext = pointsArr[i];
    					}
    				} else if (bearingNext > bearingNow) {
    					lengthNext = Math.pow(pointsArr[i].x()-pointNow.x(), 2)+Math.pow(pointsArr[i].y()-pointNow.y(), 2);
    					bearingNext = bearingNow; 
    					pointNext = pointsArr[i];
    				}
    			}
    			if(pointMin.equals(pointNext)) break;
    			pointNow = pointNext;
    			bearingPre += bearingNext;
    			pointsNew.add(pointNext);
    		}
    	}
    	return pointsNew;
    }