从多个点集合计算凸包

Question

我有一个多边形集合（如果你喜欢图论，可以考虑循环），我想找到整个特征集合的凸包，而不是每个个体 feature/polygon。我正在考虑使用单调链接，这让我有 O(n log n) 时间处理一组点，但由于我可以有 0 到 n 个点集合，是否有更好的方法来实现快速处理时间？

谢谢

Answer 1

如果您的多边形是凸面的，请考虑使用 rotating calipers。

他们的一个应用是为两个凸多边形构建公共凸包（对越来越多的多边形重复凸包合并）(chapter 5, chapter 2.6)

Answer 2

有两种方法可以实现你想要做的事情：

第一种方式 使用 "online" 凸包算法。 "Online" 表示（动态添加），使您可以一个一个地添加点。我已经完成了每点 O(log h) 的算法，可以在 GitHub. It is actually the fastest aglorithm. It is based on Ouellet Convex hull 中访问。该项目是 OuelletConvexHullAvl2Online。在您的情况下，您遍历每个多边形，并针对每个多边形遍历它们的每个点，为在线算法提供数据。

示例用法：

OuelletConvexHullAvl2Online.ConvexHullOnline convexHullOnline = new OuelletConvexHullAvl2Online.ConvexHullOnline();
                foreach (Point pt in points)
                {
                    convexHullOnline.DynamicallyAddAnotherPointToConvexHullIfAppropriate(pt);
                }

                return convexHullOnline.GetResultsAsArrayOfPoint();

第二种方式 使用 "Composite" 设计模式来包装您的多边形，因为它将是点向量（IEnumerable 或点）的单个实例。然后将复合对象提供给任何常规算法。复合材料将努力提供所有多边形的每个节点，就好像它们是单个对象（一种点数组）一样。顺便说一下，我确实在 class OuelletConvexHullAvl2Online:ConvexHullEnumerator 的算法中使用了 composite ，它将枚举包含在 4 象限（AVL 树）中的结果凸包点。

从多个点集合计算凸包

Calculating Convex Hull from Multiple Collection of Points

python

pandas

geometry

convex-hull