地圖上多邊形環繞零點不超過8個頂點

在圖像地圖上（500 x 500）我只有零和一個。大多數情況下，所有東西都是一個，但是我有幾個有零點的集羣（代表障礙物，所以玩家不能跨越山丘）。障礙物可以具有任意形狀，因此需要簡化，我決定找到一種方法，用一個不超過8個頂點的多邊形圍繞每個障礙物（周圍多邊形可以有一些內部的1s，但障礙物的所有0必須在裏面該多邊形）。對於我需要生成一個多邊形的每個障礙物。我可以連接障礙物外部邊界上的每個0，但它會產生n（n >> 8）個頂點的多邊形。我正在尋找任何建議如何做到這一點或一些類似算法的名稱。地圖上多邊形環繞零點不超過8個頂點

來源

2013-01-21 PaolaJ.

你打算如何使用多邊形？ –

@GarethRees我需要頂點來創造圖形和路徑發現 –

1.我編輯了我能解密的東西。但句子「我可以連接每個外部0，但它會產生具有n（n >> 8）個頂點的多邊形」是絕對不可讀的。爲什麼你認爲這是可能**爲每個形狀和障礙物的位置創建這樣的多邊形？我只會同意，如果poligons可以相交。 – Gangnus

您應該最初爲您的羣集構建凸包。在此之後，你可以使用以下策略減少頂點量至8： enter image description here

您找到任何對連接點的交叉點。在提供的圖像點8和9被一個10代替，但增加多邊形尺寸。

注意：此方法不保證此多邊形不會與另一個「零」羣集重疊。有時也許有8個頂點的多邊形無法覆蓋沒有其他簇相交的簇。

來源

2013-01-21 13:44:10

一個好的開始，但是這個假設障礙本身大多是凸起的。例如，一個凸出的邊界多邊形將防止進入U形山脈的山谷。 –

@Tolja感謝您的回答，但如何找到多邊形，我的障礙並不總是凸起（我編輯的問題來澄清） –

那麼，什麼？即使障礙物不是凸起的，多邊形也可以是凸起的。你的任務說不要反對它。 – Gangnus

您可以選擇障礙物S，SW，W，NW，N，NE，E和SE的最遠點，並創建一個按垂直方向穿過這些點的線段設置的八邊形。即適當的：W-E，NW-SE等等。我認爲，這將是最快和最簡單的算法，與@Толя的解決方案相反，它永遠不會給你額外的長星形射線頂點。

來源

2013-01-21 16:36:19 Gangnus

地圖上多邊形環繞零點不超過8個頂點

回答

相關問題