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

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

程序员文章站 2023-12-27 10:21:21
...

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

这里我使用的是模拟数据,下面是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

相关标签: 经典模型

上一篇:

下一篇: