我需要一種方法來構建帶孔的2D多邊形

我的對象是在蜂窩網格中構建的。所有對象都已連接。紅線代表每個節點之間的連接。我聽說二進制空間分區（BSP）樹在這種類型的問題上很好，但不知道在我的情況下前後是什麼。我需要一種方法來構建帶孔的2D多邊形

我實現使用蜂窩狀網格系統的查找如圖所示（X，Y）

class Node { 
    Point position; //center position 
    Point grid; //honeycomb grid system 
} 

class MyObject { 
    Node lookup(Point grid); 
}

我需要表示作爲用戶添加更多節點到場景上，一種方法，圖中的數據結構迅速確定網格點（針對MyObject）： 1.外 2.內部 3.孔內

enter image description here

來源

2013-11-27 docchang

我需要我美味的早晨咖啡，但我不知道如何在哥斯達黎加工作咖啡機，但是當我不可避免地在天花板上弄到地面和牛奶時，我可以試着煮咖啡來尋求幫助。你需要爲你的問題做同樣的事情 - 展示你到目前爲止所嘗試的內容，無論是代碼（最好）還是你已經完成的任何研究 – Bojangles

如果你想使用現成的實現boost提供幾何庫。 –

瞭解更多有關更大問題的信息可能會讓我們更好地瞭解最佳解決方案。 –

有多大你正在工作的空間？

用一個簡單的矩形網格模擬整個事情，假設偶數行錯開右邊。

任何節點具有座標[x,y]

對於(y%2 == 0)相鄰節點是[x-1,y][x+1,y][x,y+1][x,y-1][x-1,y-1][x-1,y+1]
對於(y%2 == 1)相鄰節點是[x-1,y][x+1,y][x,y+1][x,y-1][x+1,y-1][x+1,y+1]

每個節點可以是滿或空和空節點可以查詢或未檢查。最初所有空節點都是未檢查。

檢查如果一個節點由屬於一個洞：

如果節點是全 - 它不屬於孔，它屬於形狀。
如果一個節點是作爲檢查空馬克節點。
遍歷所有鄰居節點：
- 跳過節點標記爲檢查或全
- 遞歸地重複搜索不檢查所有節點。

如果遞歸將您帶入任何x<0, y<0, x>MAX_X, y>MAX_Y，則中止。節點外形

如果遞歸結束時沒有找到球場的邊緣，節點屬於洞。

此外，你現在可以重複開啓所有檢查節點到外供日後參考或孔的過程。

如果你想索引處開始的所有漏洞，它可能是更容易找到在操場上傳（x==0, y==0, x==MAX_X, y==MAX_Y）的邊界所有未選中空節點，並使用上述算法，以紀念他們爲外。所有剩餘的空節點都是空洞。

根據您的網格大小，您可以將其作爲包含對象狀態（或甚至char s，狀態爲數字位）的二維二維數組結構/對象，尺寸爲[MAX_X + 1] [MAX_Y + 1]如果它的大小合理，或者是一個完整節點的列表（矢量），每個節點都包含它的座標，狀態，並且如果你想讓它更快地達到最優速度，那麼它就是鄰居。在這種情況下，搜索形狀，找到所有空的鄰居節點的潛在漏洞。具有極端座標（最低/最高x/y）的邊緣節點屬於「外部」。跟隨那些有完全鄰居的空的鄰居，找到形狀的外緣。所有剩下的都是內部邊緣，在遵循算法開始之後，您將擁有所有的「洞」。

來源

2013-11-27 08:20:22

我的建議：

分配每個瓦片在2D笛卡爾空間的中心位置。
構建一個包含所有中心位置的二叉查找樹（BST）。
對於查詢點，使用該BST查找與最近佔用的瓦片的相對位置。
確定該位置是否是使用一些幾何式，例如內部或瓷磚以外，如在這裏：
- Is a point inside regular hexagon

替代地，在使用平方的近似值，例如，工作，因爲在這裏看到：

Hexagonal Grids, how do you find which hexagon a point is in?

來源

2013-11-27 08:37:29 moooeeeep

我需要一種方法來構建帶孔的2D多邊形

回答

相關問題