【算法】凸包问题--分治法

时间:2024-03-01 08:38:10

凸包问题--分治法

求能够完全包含平面上n个给定点的凸多边形。


示例:


一、分治法:

(一)算法思路:

(这里所说的直线都是有向直线的。)

将数组升序排序,若x轴坐标相同,按照y轴坐标升序排序。

最左边的点p1和最右边的点p_n一定是该集合凸包的顶点。该直线将点分为两个集合,上包为S1,下包为S2。在p1 p_n线上的点不可能是凸包的顶点,所以不用考虑。

在上包S1中,找到p_max(距离直线p1p_n最远距离的点),若有两个距离同样远的点,取∠p_max p1 p_n最大的那个点(即△p_max p1 p_n面积最大)。

(一次递归到这里结束)

找出S1中所有在直线p1 p_max左边的点,这些点中一定有构成上包中左半部分边界的顶点,用上面的算法递归查找点,直到上包就是以p1和p_n为端点的线段。

下包S2中找下边界 同理。


*如何判断点是否在直线p1 p_max左边(同 p1 p_n上方)?

如果q1(x1,y1),q2(x2,y2),q3(x3,y3)是平面上的任意三个点,那么三角形△q1 q2 q3的面积等于下面这个行列式绝对值的二分之一。

当且仅当点q3=(x3,y3)位于直线q1 q2的左侧时,该表达式的符号为正,该点位于两个点确定的直线的左侧。


(二)实现中碰到的问题

  • 如何用快速排序来排序Point类(内有坐标x,y)的一维数组?

    按照x坐标排序很简单,若碰到x相同,y不同的怎么办?


在快排的原基础上修改,以j向前逼近说明:

(第一个while循环)当前比较数的横坐标>基准点的时,j向前逼近。此处不加等于号,排序是不稳定的,即相等元素的相对位置可能发生改变。(快排详见博客:https://www.cnblogs.com/musecho/p/11647349.html)

(第二个while为添加内容)比较相等元素的纵坐标,基准点的更小,j继续向前逼近,即相等元素的相对位置不发生改变;否则,则改变。也就是将原来快排中while循环拆分为两个,增加相等元素另外比较纵坐标的情况。

while (i < j && points[j].getX() > center.getX()) {
					j--;
				}
				while (i < j && center.getX() == points[j].getX() && points[j].getY() > center.getY()) {
					j--;
				}
				/*
				 * (i<j)若points[j].getX()< center.getX()或 center.getX() ==
				 * points[j].getX()且points[j].getY()<center.getY() 以上两种情况,需要赋值
				 */
				if (i < j)// 跳出循环也有可能时因为i=j,所以这里要判断一下
					points[i++] = points[j];


  • 如果使用全局数组visit标识点是否访问,能确定凸包的所有顶点,但怎么顺序输出?

在已经求的凸包顶点里逐一确定边界,判断是不是所有点都在这条边界的一侧,如果是则确定一条边界。

        convexHullList.add(convexHullVertex[0]);// 开始点
		int haveCount = 1;// 已经加入点的个数
		// 逐条确定边界,判断是否除了该条假设边界上的点,其他凸包的顶点都在直线的右边。
		// 如果是,则此条直线为边界;如果不是,取下一个边界终点,继续判断。
		int start = 0;// 起点
		for (int end = start + 1; haveCount < count;) {
			boolean boundRight = true;
			for (int i = 0; i < count; i++) {
				while (i < count && (i == start || i == end)) {// 不能写if,start和end可能是连在一起的
					i++;
				}
				if (i >= count)
					break;

				// 点在直线左侧或线上,错误
				if (PointJudge(convexHullVertex[start], convexHullVertex[end], convexHullVertex[i]) >= 0) {
                    
					boundRight = false;
					end = (end + 1) % count;// end取下一个
					break;
				}
			}
			if (boundRight == true) {
				convexHullList.add(convexHullVertex[end]);
				start = end;
				end = (start + 1) % count;
				haveCount++;
			}
		}

(三)注意点

  • 注意方法PointJudge(Point beginP, Point endP,Point p)和PointCal(Point beginP,Point endP,Point p)中,传参放在第几个:

    前两个点是直线的两端,第三个是需要判断的点


  • 注意下包循环中的 起始点、终点、判断条件
for (int i = begin - 1; i >= end + 1; i--)

(四)源代码


1.ConvexHullProblem_DC

package ConvexHullProblem;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 凸包问题(分治法):
 */

public class ConvexHullProblem_DC {
	boolean[] visit;// 标志点是否是凸包的顶点:1是,0不是
	Point[] points;// 所有点
	Point[] convexHullVertex;// 凸包的顶点
	ArrayList<Point> convexHullList = new ArrayList<>();;// 凸包的顶点(顺序存放)

	public void ConvexHullProblem(Point[] points) {
		this.points = points;
		quickSort(0, points.length - 1);// 升序排序
//		System.out.println("升序:" + Arrays.toString(points));

		visit = new boolean[points.length];

		recursion(0, points.length - 1);// 上包
		recursion(points.length - 1, 0);// 下包

		orderConvexHull();
	}

	/**
	 * @title: recursion
	 * @description: 在凸包的上包或下包中,找使△p_max p1 p_n面积最大的点p_max,并递归
	 * @date: 2019年10月16日 下午8:33:14
	 * @param begin 直线的起点
	 * @param end   直线的终点 void
	 * @throws:
	 */
	void recursion(int begin, int end) {
		// 直线的两端点为凸包的顶点
		visit[begin] = true;
		visit[end] = true;

		if (begin < end) {
			boolean flag = false;// 标志直线左侧是否有点
			int maxArea = 0;// 最大面积
			int maxAreaindex = begin + 1;// 最大面积的点下标

			for (int i = begin + 1; i <= end - 1; i++) {// begin和end已经是顶点,不需要判断
				if (PointJudge(points[begin], points[end], points[i]) > 0) {// 点在直线左侧
					// 找距离最远的点,因为底相同都是p1 pn,也就是求三角形面积最大的
					flag = true;
					int area = PointCal(points[begin], points[end], points[i]);
					if (area > maxArea) {
						maxArea = area;
						maxAreaindex = i;
					} else if (area == maxArea) {// 若面积相同,取∠p_max p_begin p_end最大的那一个
						System.out.println(22);
						double degreeA = Degree(points[begin], points[i], points[end]);
						double degreeB = Degree(points[begin], points[maxAreaindex], points[end]);
						if (degreeA > degreeB) {
							maxArea = area;
							maxAreaindex = i;
						}
					}
//					System.out.println("area=" + area + ",Point=" + points[i]);
				}
			}
//			System.out.println("maxArea=" + maxArea + ",Point=" + points[maxAreaindex]);
//			System.out.println("over");

			// 若直线左侧还有点,则递归;没有点,则结束
			if (flag == true) {
				recursion(begin, maxAreaindex);
				recursion(maxAreaindex, end);
			}
		} else if (begin > end) {
			boolean flag = false;
			int maxArea = 0;// 最大面积
			int maxAreaindex = end + 1;// 最大面积的点下标

			for (int i = begin - 1; i >= end + 1; i--) {// 注意下包循环中的 起始点、终点、判断条件
				if (PointJudge(points[begin], points[end], points[i]) > 0) {// 点在直线左侧
					flag = true;
					int area = PointCal(points[begin], points[end], points[i]);
					if (area > maxArea) {
						maxArea = area;
						maxAreaindex = i;
					} else if (area == maxArea) {// 若面积相同,取∠p_max p_begin p_end最大的那一个
						System.out.println(22);
						double degreeA = Degree(points[begin], points[i], points[end]);
						double degreeB = Degree(points[begin], points[maxAreaindex], points[end]);
						if (degreeA > degreeB) {
							maxArea = area;
							maxAreaindex = i;
						}
					}
//					System.out.println("area=" + area + ",Point=" + points[i]);
				}
			}
//			System.out.println("maxArea=" + maxArea + ",Point=" + points[maxAreaindex]);
//			System.out.println("over");

			if (flag == true) {
				recursion(begin, maxAreaindex);
				recursion(maxAreaindex, end);
			}
		}
	}

	/**
	 * @title: quickSort:运用Hoare
	 * @description: 快速排序: 选取第一个元素作为基准点(可以随机选取),将剩下元素与基准点进行比较,
	 *               比基准点大的放在右边,比基准点小的放在左边, 得到左子表和右子表,递归调用本函数;
	 * @param points 数组
	 * @param begin  开始下标
	 * @param end    结束下标
	 * @throws:
	 */
	void quickSort(int begin, int end) {
		if (begin >= 0 && begin < end && end < points.length) {
			int i = begin, j = end;
			Point center = points[i];// 中心元素

			while (i != j) {
				while (i < j && points[j].getX() > center.getX()) {
					j--;
				}
				while (i < j && center.getX() == points[j].getX() && points[j].getY() > center.getY()) {
					j--;
				}
				/*
				 * (i<j)若points[j].getX()< center.getX()或 center.getX() ==
				 * points[j].getX()且points[j].getY()<center.getY() 以上两种情况,需要赋值
				 */
				if (i < j)// 跳出循环也有可能时因为i=j,所以这里要判断一下
					points[i++] = points[j];

				while (i < j && points[i].getX() < center.getX()) {
					i++;
				}
				while (i < j && points[i].getX() == center.getX() && points[i].getY() < center.getY()) {
					i++;
				}
				/*
				 * (i<j)若points[i].getX()> center.getX()或 center.getX() ==
				 * points[i].getX()且points[i].getY()>center.getY() 以上两种情况,需要赋值
				 */
				if (i < j)
					points[j--] = points[i];
			}
			points[i] = center;// 中心元素到达最终位置

			quickSort(begin, i - 1);
			quickSort(i + 1, end);
		}
	}

	/**
	 * @title: PointCal
	 * @description: 计算行列式的值
	 * @date: 2019年10月15日 下午7:53:07
	 * @param beginP 直线的开始点
	 * @param p      判断的点
	 * @param endP   直线的终点
	 * @return int 行列书的值
	 * @throws:
	 */
	private int PointCal(Point beginP, Point endP, Point p) {
		int cal = 0;// 行列式值

//x1y2+x3y1+x2y3-x3y2-x2y1-x1y3
		cal = beginP.getX() * endP.getY() + p.getX() * beginP.getY() + endP.getX() * p.getY() - p.getX() * endP.getY()
				- endP.getX() * beginP.getY() - beginP.getX() * p.getY();
		return cal;
	}

	/**
	 * @title: PointJudge
	 * @description:返回点p在直线beginP endP的位置
	 * @date: 2019年10月15日 下午7:56:56
	 * @param beginP
	 * @param p      判断的点
	 * @param endP
	 * @return int :1在直线左侧,0在线上,-1在右侧
	 * @throws: 注意传参放在第几个,前两个点是直线的两端,第三个是需要判断的点
	 */
	private int PointJudge(Point beginP, Point endP, Point p) {
		if (PointCal(beginP, endP, p) > 0) {
			return 1;
		} else if (PointCal(beginP, endP, p) == 0)
			return 0;
		else
			return -1;
	}

	/**
	 * @title: Degree
	 * @description: 余弦公式求∠pa pb pc的度数
	 * @date: 2019年10月16日 下午6:59:29
	 * @param pa 点
	 * @param pb
	 * @param pc
	 * @return double:返回∠c的度数(°为单位)
	 * @throws:
	 */
	double Degree(Point pa, Point pb, Point pc) {
		double degree = 0;// ∠pa pb pc度数

		// 三角形的三边长
		double a = Math.sqrt(Math.pow(pa.getX() - pb.getX(), 2) + Math.pow(pa.getY() - pb.getY(), 2));
		double b = Math.sqrt(Math.pow(pb.getX() - pc.getX(), 2) + Math.pow(pb.getY() - pc.getY(), 2));
		double c = Math.sqrt(Math.pow(pc.getX() - pa.getX(), 2) + Math.pow(pc.getY() - pa.getY(), 2));

		// 余弦公式求∠pa pb pc度数
		System.out.println("acos=" + Math.acos((a * a + b * b - c * c) / (2.0 * a * b)));
		degree = Math.toDegrees(Math.acos((a * a + b * b - c * c) / (2.0 * a * b)));
		System.out.println("degree=" + degree);

		return degree;
	}

	/**
	 *@title: orderConvexHull 
	 *@description: 凸包顶点按顺时针输出
	 *@date: 2019年10月19日 上午9:28:44 
	 *void
	 *@throws:
	 */
	void orderConvexHull() {
		/** 将凸包顶点存放进另一个数组 */
		int count = 0;// 凸包的顶点个数
		for (int i = 0; i < visit.length; i++) {
			if (visit[i] == true) {
				count++;
			}
		}
		convexHullVertex = new Point[count];
		for (int j = 0, i = 0; j < visit.length; j++) {
			if (visit[j] == true) {
				convexHullVertex[i] = points[j];
				i++;
			}
		}

		convexHullList.add(convexHullVertex[0]);// 开始点
		int haveCount = 1;// 已经加入点的个数
		// 逐条确定边界,判断是否除了该条假设边界上的点,其他凸包的顶点都在直线的右边。
		// 如果是,则此条直线为边界;如果不是,取下一个边界终点,继续判断。
		int start = 0;// 起点
		for (int end = start + 1; haveCount < count;) {
			boolean boundRight = true;
			for (int i = 0; i < count; i++) {
				while (i < count && (i == start || i == end)) {// 不能写if,start和end可能是连在一起的
					i++;
				}
				if (i >= count)
					break;

				// 点在直线左侧或线上,错误
				if (PointJudge(convexHullVertex[start], convexHullVertex[end], convexHullVertex[i]) >= 0) {
//					System.out.println("****");
//					System.out.println(convexHullVertex[start]);
//					System.out.println(convexHullVertex[end]);
//					System.out.println(convexHullVertex[i]);
//					System.out.println("****");
					
					boundRight = false;
					end = (end + 1) % count;// end取下一个
					break;
				}
			}
			if (boundRight == true) {
				convexHullList.add(convexHullVertex[end]);
				start = end;
				end = (start + 1) % count;
				haveCount++;
			}
		}
		convexHullList.add(convexHullVertex[0]);// 结束点
		System.out.println("凸包顶点顺时针输出:" + convexHullList);
	}
}


2.Point

package ConvexHullProblem;

/**
 * 点的信息
 */
public class Point {
	private int x, y;// 横纵坐标

	public Point(int x,int y) {
		this.x=x;
		this.y=y;
	}
	
	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public String toString() {
		return " (" + x + ", "+ y + ")";
	}

}


3.Demo_DC

package ConvexHullProblem;

import java.util.Arrays;
import java.util.Scanner;

public class Demo_DC {
	public static void main(String[] args) {

		//示例
		Point[] points=new Point[13];
		points[0] = new Point( 4, 5);
		points[1] = new Point(10, 11);
		points[2] = new Point( 4, 11);
		points[3] = new Point( 1, 1);
		points[4] = new Point( 10, 6);
		points[5] = new Point( 8, 14);
		
		//横坐标最两侧的点
		points[6] = new Point( 13, 7);
		points[7] = new Point( 13, 0);
		points[8] = new Point( 0, 9);
		points[9] = new Point( 0, 7);
		
		points[10] = new Point( 5, 5);
		points[11] = new Point( 7, 9);
		points[12] = new Point( 11, 3);

//		Scanner scanner = new Scanner(System.in);
//		System.out.println("**********凸包问题**********");
//		System.out.println("请输入点的数量:");
//		int n = scanner.nextInt();
//		Point[] points = new Point[n];
//		points = randomPoint(points);
		
		System.out.println("随机生成点:" + Arrays.toString(points));
		ConvexHullProblem_DC convexHullProblem = new ConvexHullProblem_DC();
		convexHullProblem.ConvexHullProblem(points);

	}

	static Point[] randomPoint(Point[] points) {
		for (int i = 0; i < points.length; i++) {
			int x = (int) (Math.random() * 21);// [0-20]
			int y = (int) (Math.random() * 21);// [0-20]

			points[i] = new Point(x, y);
		}

		return points;
	}
}


(运行结果)