1.减而治之(Decrease and Conquer)
插入排序
典范的减而治之算法就是插入排序方法
插入排序法: 在未排序中选择一个元素，插入到已经排序号的序列中
将凸包也采取减而治之的方法
2.In-Convex-Polygon Test
怎么判断引入的极点存在于多边形里面还是外貌？
也就是必要区分出6,7,9 和 8。
判断上述的核心就是判断引入的点在凸包里面还是在外貌
上述过程，先排序，再做二分算法，最后做In-Triangle test。
上述算法的问题：凸包并不是静态、一层不变的
如果采取插入排序法算法复杂度并不会低落，由于如果采取vector来存在，会存在失效的情况。实际情况复杂度还是n*n
还是采取淳厚元素的方法
进而采取 to-left test 判断一个点是在内部还是外部，算法的复杂度是n*n
3.Support Line
怎样将极点增加到现有的凸包上面去？
确定support line
st这一段就是Support Line/tangent
怎么确定s和t定点
4.Pattern Of Turns
s的特征：所有极点都在它的左侧
t的特征：所有点点都在它的右侧
5.Exterior/Interior
6. Selection Sort与凸包
采取选择排序的方法，可以制止已经sorted的部分被打乱掉，但是必要知道根据什么规则来进行排序
采取雷同于选择排序算法的方式，用在凸包寻找极点，缩小查找的范围
怎样在当前已有的极边查找下一个极点？
可以通过角度来确定下一个极点，但是这种做法并不明智。采取 to-left-test 更加机智
起始点怎样确定？
lowest-then-leftmost。 高度最低，然后最左边的点
实现
确认出发点
output Sensitivity
h代表在凸包上必要行驶的步数
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
