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