旋转卡壳——凸多边形间最大距离

凸多边形间最大距离

给定两个凸多边形 P 和 Q， 目标是需要找到点对 (p,q) （p 属于 P 且 q 属于 Q） 使得他们之间的距离最大。

很直观地，这些点不可能属于他们各自多边形的内部。 这个条件事实上与直径问题非常相似：

两凸多边形 P 和 Q 间最大距离由多边形间的对踵点对确定。
虽然说法一样， 但是这个定义与给定凸多边形的对踵点对的不同。
与凸多边形间的对踵点对本质上的区别在于切线是有向且反向的。 下图展示了一个例子： 
 
上述结论暗示不单纯只是顶点对需要检测， 而仅仅是特定的顶点对需要被考虑到。 事实上他们只检测一个基于旋转卡壳模式的算法确立的平行切线。
考虑如下的算法， 算法的输入是两个分别有 m 和 n 个顺时针给定顶点的凸多边形 P 和 Q。

1. 计算 P 上 y 坐标值最小的顶点（称为 yminP ） 和 Q 上 y 坐标值最大的顶点（称为 ymaxQ）。
2. 为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。 此时 LP 和 LQ 拥有不同的方向， 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。
3. 计算距离(yminP,ymaxQ) 并且将其维护为当前最大值。
4. 顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。
5. 一个新的对踵点对产生了。 计算新距离， 与当前最大值比较， 如果大于当前最大值则更新。 如果两条线同时与边发生重合， 此时总共三个对踵点对（先前顶点和新顶点的组合）需要考虑在内。
6. 重复执行步骤4和步骤5， 直到新的点对为(yminP,ymaxQ)。
7. 输出最大距离。

旋转卡壳模式确保了所有的对踵点对都被考虑到。 此外， 整个算法拥有线性的时间复杂度， 因为（除了初始化）， 执行步数与顶点数相同。

类似的算法可以被用于凸多边形间最小距离问题中。

 

原文地址：http://cgm.cs.mcgill.ca/~orm/maxd2p.html

 

转载请注明出处，谢谢！