经典模型 凸包问题(分治/快包)

经典模型 凸包问题(分治)

这里我使用的是模拟数据,下面是ppt做的图(丑陋了点)

思路:
快速排序(构造Arrays.sort(Comparator<? super T> c) 所有点 ,找到距离最远的两点
通过行列式三角形面积法求解得到 据直线最远的点indexMaxArea
分治, 每次递归得到hull(left ,indexMaxArea); hull(indexMaxArea ,right)
在递归之后并中序输出 达到顺时针输出凸包上点得效果(不需要单独声明一个容器用于打印结果)

总结:
1.根据指定比较器产生的顺序对指定对象数组的指定范围进行排序。
Arrays.sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)
这里的toIndex是不闭合,取不到值的
2.行列式求解2倍三角形面积->距直线最远的点

(公式的推导,无非就是代入坐标,硬算即可)
3.我感觉即便是三角形面积相等的情况下(同时不止一个点到直线距离一样远),也没有必要通过求角度来选取凸包上点,我觉得直接遍历到最后一个满足最远距离的点就可以了,毕竟这样做也可以保证顺序不会乱

public class 快包 {
	static Point[] points; 									//所有点
	public static void main(String[] args) {
		init();
		Arrays.sort(points ,0 ,points.length ,new Comparator<Point>(){
			@Override
			public int compare(Point o1, Point o2) {		//排序各点,得到相距最远的两个点
				if(o1.x ==o2.x) return (int)(o1.y -o2.y); else return (int)(o1.x -o2.x);
		}});
		System.out.println(points[0].x+" - "+points[0].y);
		hull(0 ,points.length -1 ,true);
		System.out.println(points[points.length -1].x+" - "+points[points.length -1].y);
		hull(0 ,points.length -1 ,false);
		System.out.println(points[0].x+" - "+points[0].y);
	}
	private static void hull(int left ,int right ,boolean isTop) {//isTop为true则为上包的情况
		int maxArea =0 ,indexMaxArea =left ,area =0;
		for(int i =left +1 ;i <right ;i ++) {
			if(isTop) area =getArea(left ,right ,i); else area =-getArea(left ,right ,i);
			if(area >=maxArea) { 
				maxArea =area;
				indexMaxArea =i;
			}
		}
		if(left ==indexMaxArea) return;
		//并中序输出
		hull(left ,indexMaxArea ,isTop);
		if(isTop) System.out.println(points[indexMaxArea].x+" - "+points[indexMaxArea].y);
		hull(indexMaxArea ,right ,isTop);
		if(!isTop) System.out.println(points[indexMaxArea].x+" - "+points[indexMaxArea].y);
	}
	//求解三角形面积
	private static int getArea(int left, int right, int index) {return points[left].x *points[right].y +points[index].x *points[left].y +points[right].x *points[index].y -points[index].x *points[right].y -points[right].x *points[left].y -points[left].x *points[index].y;}

	private static void init() {	//这里使用模拟数据
		points =new Point[10];
		points[0] =new Point(1 ,3);
		points[1] =new Point(2 ,1);
		points[2] =new Point(3 ,5);
		points[3] =new Point(4 ,4);
		points[4] =new Point(5 ,2);
		points[5] =new Point(3 ,2);
		points[6] =new Point(2 ,4);
		points[7] =new Point(4 ,2);
		points[8] =new Point(4 ,5);
		points[9] =new Point(6 ,3);
	}
}

class Point{
	int x ,y;
	public Point(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
}

最后感谢一波热心网友
https://www.cnblogs.com/musecho/p/11703227.html
https://blog.csdn.net/qq_39630587/article/details/79264119