首页 > 代码库 > 分支算法——凸包问题

分支算法——凸包问题

求能够完全包含平面上n个给定点的凸多边形。这个问题一般使用快包算法。

快包思想:

1)将n个点按照x左边进行排序,找到P1和Pn,直线P1->Pn将平面上的点分为两部分S1和S2,成为上包和下包,递归的求解这两部分。

2)如何求S1和S2,这两部分算法一样,以S1为例。如果S1为空,上包就是一P1和Pn为端点的线段。如果S1不为空,找到S1中的顶点Pmax,它是距离直线P1Pn最远的点。然后该算法找出S1中所有在直线P1Pmax左边的点,这些点和p1,Pmax构成集合S1,1。同理,直线PmaxPn左边的点和Pmax,Pn构成集合S1,2。这样一直递归下去,最终就能得到整个集合的上包。

如何求Pamx?任何平面上的三个点,P1(x1,y1),P2(x2,y2),P3(x3,y3),那么三角形的面积等于下面行列式绝对值的二分之一:

|x1 y1 1| 

|x2 y2 1| = x1y2 + x3y1 + x2y3 - x3y2 - x2y1 - x1y3

|x3 y3 1|

Pmax是面积最大的点。

如何求直线左侧的点?当且仅当点P3(x3,y3)位于直线左侧时,上面的计算结果为正。使用这个计算公式,可以在固定时间内判断一个点是否位于直线的左侧。

分支算法——凸包问题