用于合并两个可从 python 访问的纠结凸包的快速库?

Fast libraries for merging two tangled convex hulls accessible from python?

我正在寻找增量的东西(具有可访问状态)。所以这可能意味着一些合并方法被公开了。

所以一般来说,我想从一组点开始,计算出一个 ConvexHull 并向其添加一个点(它本身就是一个凸包)。正在通过凸包合并寻找 BowyerWatson 的替代品。不确定这是否是个坏主意。不确定这是否应该是 CS 中的一个问题,除了它是关于在 python 回声系统中找到一个真正的解决方案。

我在这里看到了一些相关内容。

Merging two tangled convex hulls

Qhull(scipy Delaunay 和 ConvexHull 使用这个)有很多选项我还不明白

http://www.qhull.org/html/qh-optq.htm

您可以使用 Andrew's modification of the Graham scan 算法。

这里是对some short python code实现它的引用。

它适合您的需要的是,在 xy-order 中对点进行排序后,在 线性 时间内计算上层和下层外壳。由于您已经有了凸包(可能都是凸包),凸包点的 xy-sorting 将花费线性时间(例如,反转下包和 merge-sort 四个排序列表)。算法的其余部分将花费线性时间(在凸包上的点数中,这很可能比原始点数少得多)。

此实现的所有功能都在上面引用的代码中,对于合并,您可以使用 或实现您自己的。