從多個點的集合計算凸面

Question

我有一個多邊形的集合（如果你喜歡圖論），我想找到整個特徵集合的凸包，而不是每個單獨的特徵/多邊形。我正在考慮使用單調鏈，這使得我有一組點，但由於我可以有0到n個點的集合，是否有更好的方法來實現快速處理時間？

感謝

Answer 1

如果您的多邊形是凸的，可以考慮使用的rotating calipers。

他們的一個應用是建立共同凸包的兩個凸多邊形（重複凸包融合了越來越多的多邊形）（chapter 5，chapter 2.6）

Answer 2

有2種方式來acheive你想要做什麼：

第一種方法 使用「在線」凸包算法。 「在線」意味着（動態添加），使您可以逐個添加點。我已經完成了O（log h）中每個點的算法，可以在GitHub中訪問。它實際上是最快的藥劑。它基於Ouellet Convex hull。該項目是OuelletConvexHullAvl2Online。在你的情況下，你循環你的每個多邊形，併爲他們每個人，你循環他們的每個點提供在線算法。

使用範例：

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

       return convexHullOnline.GetResultsAsArrayOfPoint(); 

第二種方式 使用「複合」的設計模式來包裝你的多邊形，因爲這將是點的向量（一個IEnumerable或點）的單個實例。然後，您使用複合對象提供任何常規算法。複合材料將爲您所有多邊形的每個節點提供服務，就好像它們是單個對象（一種點數組）。順便說一下，我在類OuelletConvexHullAvl2Online中使用了複合算法：ConvexHullEnumerator，它將枚舉包含在4象限（AVL樹）中的結果凸包點。