首页 > 代码库 > 分支算法——凸包问题
分支算法——凸包问题
求能够完全包含平面上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)位于直线左侧时,上面的计算结果为正。使用这个计算公式,可以在固定时间内判断一个点是否位于直线的左侧。
分支算法——凸包问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。