包含一組點的多邊形

Question

我有一組點S（2D：由x和y定義），我想要找到P，最小的（意思是：用最少的點數）多邊形包圍所有的點該集合P是S的有序子集。有沒有任何已知的算法可以計算出這個值？

（我在這個領域缺少文化是驚人的...）

感謝您的幫助

Answer 1

有這個問題很多算法。它被稱爲「minimum bounding box」。你會發現解決方案也搜索「convex hull」，尤其是here。

一種方法是找到最左邊的點，然後重複搜索所有其他點位於行p（n-1）p（n）右側的點。

Answer 2

您可能表示您想要最小的區域，即凸包。

如果你真的想要最少的點，你可以做一個三角形超大的頂點位置，使所有的點都包含在內。

Answer 3

這裏有一個簡單的解決方案...

與任何三點開始形成一個三角形。通過以下操作將每個附加點添加到多邊形：

將邊緣劃分爲兩個連續路徑，其中每條邊的線將該點與其餘多邊形的點分開（我們稱之爲「分離路徑」）並且在另一路徑中，每條邊的線具有與多邊形相同的一側上的點。

（注意：只要你的形狀保持凸的，它必須，這兩個路徑將是連續的，並形成整體的形狀）

如果分離路徑具有無毛邊，該點在多邊形內部和應該被忽略，否則，從多邊形中刪除分離路徑。將其替換爲兩段，將分離路徑的每個端點連接到新點。

Ta-da！ :)

Answer 4

這裏的凸包算法一個很好的資源：The Convex Hull of a 2D Point Set or Polygon (by Dan Sunday)