Gift wrapping 算法計算凸包

計算給定集合中的凸包利用Gift wrapping algorithm算法，先找到最左下角的點加入集合，然後比較剩餘點到此點的偏轉角，找到偏轉角最小的加入集合，當偏轉角相同時，需要找到最長的一條邊的點加入集合，最後即可得到凸包的點集。

public static Set<Point> convexHull(Set<Point> points){
    	
            //throw new RuntimeException("implement me!");
        	ArrayList<Point> ConvexHull=new ArrayList<Point>();
            ArrayList<Point> temppoint=new ArrayList<Point>();
            
            
            temppoint.addAll(points);//将所有點集加入
            Point p0;
            if(temppoint.size()<=3) {
            	return points;
            }//少于三個點直接是凸包
            else {
        		    p0=temppoint.get(0);  //找尋橫縱坐标最小的點p0,p0一定是凸包裡的點
        		for(Point temp:points) {
        			if(temp.x()<p0.x()) {
        				p0=temp;
        			}
        			else if(temp.x()==p0.x()&&temp.y()<p0.y()) {
        				p0=temp;
        			}
        		}
        		ConvexHull.add(p0);//将p0加入凸包
        		temppoint.remove(p0);
        		
            }
         /*卷包算法：1.以p0為原點，找到極角最小的點，如果角度相同那麼選取距離p0遠的點。
         該點即為下一個p0，重複（1）中過程，直到回到原點，這個序列就是凸包序列。*/
           int j=0;
            Point p1=p0;
            //Point p2=p0;
            //double minangle=calculateBearingToPoint(0,(int)p0.x(),(int)p0.y(),(int)temppoint.get(0).x(),(int)temppoint.get(0).y());
           //double maxdistance=Math.pow(p0.x() - temppoint.get(0).x(), 2) + Math.pow(p0.y() - temppoint.get(0).y(), 2);//計算距離
            temppoint.add(p0);
            // int n=temppoint.size();
            do {
            	
            	if(j==1) {
            		temppoint.add(p1);
            	}
            	double maxdistance=0;
            	double minangle=360;
            	 
            	Point p2=null;
                 for(Point temp:temppoint) {
            	double tempangle=calculateBearingToPoint(0,(int)p0.x(),(int)p0.y(),(int)temp.x(),(int)temp.y());//計算極角
    			double tempdistance=Math.pow(p0.x() - temp.x(), 2) + Math.pow(p0.y() - temp.y(), 2);//計算距離
                if(tempangle<minangle) {//極角最小
                	minangle=tempangle;
                	p2= temp;
                	maxdistance=tempdistance;
                }
                if(tempangle==minangle&&tempdistance>maxdistance) {//極角相同，選取距離遠的點
                	maxdistance=tempdistance;
                	p2= temp;
                }
            	}
            	
            	ConvexHull.add(p2);
            	p0=p2;
            	temppoint.remove(p2);
            	j++;
            	
            }while(ConvexHull.get(j)!=p1);
    		
    		Set<Point> finalresult = new HashSet<Point>();
    		finalresult.addAll(ConvexHull);
    		return finalresult;
    	}
    
           

測試：

/**
	 * Tests convexHull.
	 */
	@Test
	public void convexHullTest() {
		Set<Point> points = new HashSet<Point>();
		Set<Point> convexHull = new HashSet<Point>();

		assertEquals(convexHull, TurtleSoup.convexHull(points));

		Point p11 = new Point(1, 1);
		Point p1010 = new Point(10, 10);
		Point p110 = new Point(1, 10);
		Point p12 = new Point(1, 2);
		Point p23 = new Point(2, 3);
		Point p32 = new Point(3, 2);

		points.add(p11);
		convexHull.add(p11);
		assertEquals(convexHull, TurtleSoup.convexHull(points));

		points.add(p1010);
		convexHull.add(p1010);
		assertEquals(convexHull, TurtleSoup.convexHull(points));

		points.add(p110);
		convexHull.add(p110);
		assertEquals(convexHull, TurtleSoup.convexHull(points));

		points.add(p12);
		assertEquals(convexHull, TurtleSoup.convexHull(points));

		points.add(p23);
		assertEquals(convexHull, TurtleSoup.convexHull(points));

		points.add(p32);
		convexHull.add(p32);
		assertEquals(convexHull, TurtleSoup.convexHull(points));
	}