写不出 Qhull

旧文。大概写于 2017 年 9 月。

被囚禁于凸包之内的兔子

quick hull 算法很简单，但是要实现这个算法，而且要保证程序堪作大用，那就很难了。

要将一个凸包外部的点 x 合并到凸包上，首先需要在凸包上搜索 x 的可见域。我们身为万物之灵的人类，虽然深懂得眼见为实的道理，但也常常被 P 过的照片而欺骗。身为一个 n 维点的 x 也不能幸免，它也无法分辨属于可见域的那些凸包面片哪一个能真正为它所见。

将一张纸呈水平状置于眼前，让自己只能看到它的边。此时，看到的是一张纸吗？理论上，我们也无法确定。不过幸好我们的瞳孔直径大于纸的厚度，以致于总是能够隐约看到这张纸的两面，但即便如此，与我所见的那条边相对的边却不能为我所见。这种情况下，就不能宣称我看到的是一张纸，只能宣称我看到了一张纸的某条边。要让点 x 也像我这样去看一张纸，那么点 x 需要膨胀为一个以它为中心的小球，凸包上的面片需要有一个厚度，并且小球的直径应当大于面片的厚度。当面片贯穿小球时，点 x 便可以宣称它看到了一张有厚度的面片的部分边，并且还有一部分不能为它所见。这种情况下，点 x 称自己与该面片共面，并将其归于不可见域。

看起来，问题也很好解决。然而，点 x 并不知道自己应当膨胀多大。若膨胀得过大，会导致它经常看不到凸包上的面片而误以为可见域不存在。若膨胀得过小，又会导致不该看到的又被它看到了，而它又弄不明白那些不过是海市蜃楼。

问题始终都是问题。一个问题解决了，只不过是从原来的问题里挤压出来新的问题。这可能是这个世界固有的一些「Bug」决定的。

quick hull 算法的作者为该算法提供了一个很稳健的实现，即 Qhull 包。他的论文讲这个算法只用了不到 2 页纸，但是 Qhull 的 C 代码却有 17000 余行。人类语言的表现力秒杀程序语言。

Qhull 用了两种启发式方法尽量提高点 x 的可见域的合理性，一种是将近似共面的面片合并起来，另一种是轻微摇晃 x 的位置。第一种方法会导致凸包面片不够单纯，譬如三维凸包不能完全由三角形构成，而且也不能完全解决所有的面片维度退化问题。第二种方法会让点 x 觉得自己不再是自己。

这两种方法我一个都实现不出来。第一种方法会产生不单纯的凸包，我要用这种凸包，需要自己动手去处理那些不单纯的凸包面片，然而我也不清楚该如何处理它们。第二种方法很符合我的需要，毕竟我对点 x 在参与凸包构建过程的之后还是不是它原本的面目不太关心，然而我却很难确定在多大范围内摇晃点 x，这个问题的难度跟确定点 x 的膨胀直径差不多。

写不出来也不丢人。Matlab 与 Mathematica 的开发者们也没写出来，或不屑去写，所以它直接用了 Qhull。最终我实现出来的是一种冷酷无情的 quick hull。凡是与凸包上的某个面片近似共面的点 x，凸包的大门永远对其关闭。