CoderMeng

计算几何03-寻找凸包

发表于 更新于 分类于

问题描述：

点集Q的凸包ch(Q)是一个最小的凸多边形P，它满足Q中的每个点或者在P的边界上，或者在P的内部。你的任务是对于给定的点集Q，求Q的凸包ch(Q)集。

输入：

输入测试数据。测试数据的第一行上有整数n，表示该组测试数据有n个点组成的集合Q。接下来有n行，其每一行上有二个正整数，之间用一个或几个空格隔开。

输出：

输出该凸包的顶点集合，要求先输出凸包的顶点中纵坐标最小且靠最左边的点，然后将凸包的其它顶点按逆时针方向列出。

输入样例：

6
1 1
2 2
1 3
2 3
3 1
3 3

输出样例：

(1,1)(3,1)(3,3)(1,3)

Graham 扫描法

在 《算法导论》上 Graham 扫描法的伪代码如下

Graham.jpg

过程 GRAHAM-SCAN 的输入为点集 Q ，其中 |Q|> 3。

第一行从点集 Q 中选取 y 值最小的，并且与其有相同 y 值的点都在它的右边，后面的点都已 p0 为参考点。（下面代码中的 setP0() 方法）

第二行根据相对于 p0 的极角对 Q 中剩余的点进行排序，采用插入排序的方法（参考：计算几何02-用叉积比较极角大小并对点集进行排序）。如果有两个或更多的点对 p0 的极角相同，那么除了与 p0 距离最远的点外，其余各点都是 p0 与该最远点的凸组合。因此，我们可以完全不考虑这些点。（下面代码中的 PolarAngleSort 类下的 sortPoints(int[][] points, int[] sorts) 方法。）

第五行–第十二行运用了栈 S，其中第68行对栈进行初始化，使其从底部到顶部依次包含前三个点 p0,p1,p2。第912行的 for 循环对序列（p3,p4,···,pm）中的每一个点进行一次迭代。算法的意图是在对 pi 进行处理后，在栈 S 中，由底部到顶部依次包含 ch(p0,p1,···,pi) 中按逆时针排列的各个顶点。第10~11行的 while 循环把所有发现的不是凸包中的顶点的点从栈中移去。当沿逆时针方向遍历凸包时，我们应该在每个顶点处向左转。因此，每当 while 循环发现一个顶点处没有向左转时，就把该顶点从栈中弹出来。

当程序运行结束时，栈 S 从底部到顶部包含了按逆时针方向排列在 ch（Q） 中的个顶点。

PolarAngleSort.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * @author corlymeng.com
 * @date  2015年9月18日
 */
package geometry.convex;

import java.util.Scanner;

public class PolarAngleSort {

	/**
	 * 返回向量：(pi-pk)*(pi-pj) 的叉积。
	 * pi, pj, pk, 分别是平面上的三点坐标，
	 * pi[0] -> x
	 * pi[1] -> y
	 * @return int
	 */
	public static int direction(int[] pi, int[] pk, int[] pj){
		return (pi[0]-pk[0])*(pi[1]-pj[1]) - (pi[0]-pj[0])*(pi[1]-pk[1]);
	}
	// 计算点 p1 到点 p2 的距离
	public static double pointDistance(int[] p1, int[] p2) {
		return Math.hypot( p1[0]-p2[0], p1[1]-p2[1] );
	}
	
	/**
	 * ！核心代码
	 * 采用插入排序的思想对点集进行排序。
	 * 以点points[0] 为参考点
	 */
	public static void sortPoints(int[][] points, int[] sorts) {
		int i,j;
		int[] tmp;
		double d1,d2;
		for (i = 2; i < sorts.length; i++) {
			tmp = points[i];
			j = i-1;
			while( j>0 ){
				if (sorts[j]<0 || direction(points[0], points[sorts[j]], tmp) < 0) {
					sorts[j+1] = sorts[j];
					j--;
				} else {
					break;
				}
			}
			// 叉积为 0 的时候，要计算这两点到 p0 的距离，
			//将距离最远的点保留，距离近的点舍去，将点对应的sorts 数组的值设置为负数即表示忽略此点
			if (j != 0 && direction(points[0], points[sorts[j]], tmp) == 0) {
				d1 = pointDistance(points[0], points[sorts[j]]);
				d2 = pointDistance(points[0], tmp);
				if (d1 > d2) {
					sorts[j+1] = -i;
				} else {
					sorts[j] = -sorts[j];
					sorts[j+1] = i;
				}
			} else {
				sorts[j+1] = i;
			}
		}
	}
}

FindConvex.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * @author corlymeng.com
 * @date  2015年9月19日
 */
package geometry.convex;

import java.util.Scanner;

/**
 * 找出给定点集的凸包
 */
public class FindConvex {
	//点的数量
	private int nums;
	// 存放输入的点集
	private int[][] points;
	/**
	 * 存放点的顺序，sorts[0] = 0，默认的相对点，后面的点1，2，3...都是以 0 为参考点
	 * sorts[1]=4,表示点集中相对于参考点极角最小的是点 4
	 */
	private int[] sorts;
	
	// 模拟栈的操作
	private int[] stack;
	// 栈顶指针
	private int top;

	private void setP0(){
		int tmp = 0;
		//找出 y 值最小的点
		for(int i=1; i<nums; i++){
			if (points[tmp][3] > points[i][4]) {
				tmp = i;
			} else if (points[tmp][5] == points[i][6]) {
				// y 值相同时，比较 x 值
				if (points[tmp][0] > points[i][0]) {
					tmp = i;
				}
			}
		}
		if (tmp == 0) {
			return;
		}else {
			int[] p = points[0];
			points[0] = points[tmp];
			points[tmp] = p;
		}
	}

	public void init(){
		Scanner in = new Scanner(System.in);
		nums = in.nextInt();
		points = new int[nums][2];
		sorts = new int[nums];
		stack = new int[nums];
		top = 0;
		for (int i = 0; i < nums; i++) {
			sorts[i] = i;
			points[i][0] = in.nextInt();
			points[i][7] = in.nextInt();
		}
	}
	
	/**
	 * !核心代码
	 * 获取凸包的顶点集，存放在 stack 变量中，按逆时针顺序存放。
	 */
	public void findConvexPoint() {
		// 初始化操作
		init();
		setP0();
		PolarAngleSort.sortPoints(points, sorts);
		
		//首先，将点集 p0,p1,p2 入栈
		int s = 0;
		stack[top] = sorts[0];
		while(top < 2){
			if (sorts[s]>0) {
				stack[++top] = sorts[s];
			}
			s++;
		}
		for ( ; s < nums; s++) {
			if (sorts[s] < 0) {
				continue;
			}
			while(PolarAngleSort.direction(points[stack[top]], points[stack[top-1]], points[sorts[s]]) >= 0 ) {
				top--;
			}
			stack[++top] = sorts[s];
		}
	}	
	
	public void print() {
		for(int i=0; i<=top; i++){
			System.out.print("("+ points[stack[i]][0] +","+ points[stack[i]][8] +")");
		}
	}
	
	public static void main(String[] args) {
		FindConvex fc = new FindConvex();
		fc.findConvexPoint();
		fc.print();
	}

}

欢迎关注我的其它发布渠道