Wikipedia 和Chan 的论文 都指出,一旦 Graham 的扫描完成后,我们的原始集合 $P$ 的 $n//m$ 个子集就完成了,因为每个子船体都是从最低点开始按逆时针旋转从最小到最大的顺序排列的,我们可以在每个山丘上使用二分搜索来执行 Jarvis March。
来自维基百科:
.... 集合 $Q_k$、$C_k$ 的凸包是已知的,并且最多包含 $m$ 个点(按顺时针或逆时针顺序列出),这允许计算 $f(p_{ i},Q_{k})$ 通过二分查找在 $O(\log m)$ 时间内完成。
来自 Chan 的论文:
由于通过二分或斐波那契搜索[5],[25***](对偶问题是用射线与凸多边形相交)寻找凸多边形的切线需要对数时间,因此包装步骤所需的时间为O ((n/m) log m)。 [第 2 页] 还, 通过对 conv(Pi) 的顶点执行二分搜索来计算使 $ ngle p_{k-1}p_k q_i$ 最大化的点 $q_i\in P_i$ [第 3 页]
我不知道该怎么做。
我在网上查找了更完整的解释,但大多数来源都跳过了二进制 jarvis March 的实际实现。我看过一些实现,但是他们的代码和 GitHub 上 Chan 算法的实现不太容易阅读。
*** 我尝试浏览“计算几何:简介 - F Peparata,M I Shamos”,这是第一个引用 Chans 论文中的 [25]。不幸的是,我找不到二进制贾维斯。我在计算几何方面也没有经验。
我非常感谢我所说的二进制 jarvis 的 python 实现,或者至少解释如何编写它的伪代码。
常规贾维斯行军的内循环扫描集合 P 中的所有点,以找到凸包的下一个点。下一个点是根据线段 [CurrentPoint, NextPoint] 和 OX 轴之间的极角来选择的 - 该角度必须最小化。
然而,Chan 算法中使用的 Jarvis March 的变体处理许多带有顶点的已经创建的凸多边形,并以逆时针顺序存储。因此,这个变体的内部循环不需要扫描这些多边形的所有点 - 它可以使用(某种)二分搜索来查找当前点和每个多边形之间的切线,然后选择具有最小极角的线。
至于Python源代码,