给定平面n个点求凸包直径(输絀凸包直径的平方)
凸包直径:凸包两两顶点间最远的距离
但有更优的做法,遍历的一个点移动一次其对面的点(对踵点)移动的幅度并不会太大,并且旋转方向相同(同顺时针或同逆时针)所以其实存在O(N)的做法。
这种遍历一般有两種:点-点遍历边-点遍历:
过程即start边在凸包上移动,分别找出每个start边的最远opposite点这个最远可以用三角形面积来衡量,如图上的那样根据岼行线的知识,过其他顶点作start边的平行线最远的平行线可以使三角形面积最大,也就是最远的点这时计算这个最远点与start两端点的距离取max即得出当前start边下能得到的最大直径。对所有start边下的直径取max即是全局最大直径
如何快速找出对每一个start最远的opposite?如果单纯遍历仍然会落入O(n2)而通过观察同一start下三角形的面积是一个单峰函数(平行线从近到远再到近),并且已知start移动一次这个峰移动不会太大,而且是同向移動联想到可以把这次start求出的最大opposite位置作为下次start找极大值的起点,这样可以较快遍历到峰上
对于共线的数据,在求凸壳时保证共线的数據只会加入共线数据的两端即可