平面凸包问题

 

平面凸包:为了包含几个元素,由最外面的元素连接形成的最小凸多边形

 

斜率逼近法:

1.寻找y值最小的点,从水平方向开始,逆时针旋转寻找第一个k>0且k最小的点

(ps:若有多个点符合目标要求,则选取最远的点,保证划定面积最大)

2.一直找到p1=pm为止

 

pps:平面凸包必然存在

 

方法漏洞:若k趋向于无穷则该题无解

 

Jarvis算法

不严谨的数学描述:一条直线过一点A,使得其他所有点在直线同一侧,然后顺时针或逆时针抡这根棍子,直到抡到除A以外的一点B。

遇到多个点一定要选取离A最远的点

 

方法漏洞:由于人为设置可以导致时间复杂度爆炸

 

Graham算法

求极角:

atan2(a[i].y,a[i].x)

 

选择y值最小,若y值相同则选择x值最小的点,按照极角大小进行排序

 

连接时若现左拐再右拐则出栈

 

平面凸包问题

上一篇:华强买瓜?程序员版


下一篇:window.name 跨域数据传输