什麼是管理正方形的幾何細分的適當數據結構？

Question

我正在尋找一種數據結構，可以管理矩形對象（O LxH）以及矩形對象的所有細分（內部分區）的數據。

一個應該能夠添加更多的分區，以及訪問現有的分區。每個分區應被視爲另一個矩形對象（O LxH）。

我在想我可以使用BSP樹，但我認爲這可能是對我的問題過於複雜的解決方案。

實施例在圖中

分區「B」應與原點，一個長度和一個高度另一個對象。

Answer 1

我會說你肯定需要某種樹。

你提到你擔心BSP樹可能對這個問題過於複雜 - 這取決於你需要解決方案的強大程度。您可能還想考慮是否可以將對象分割爲兩部分以上 - 如果不是，則可以使用二叉樹。

基本上，樹中的每個節點都有一個大小和形狀，以及子節點。此外，該節點將負責確保其子女的大小和形狀是有意義的 - 即他們不重疊，他們填充整個父母，他們不會超出父母。

訪問分區可以通過給每個節點相對於其父節點的相對ID來完成。第一個孩子得到relativeID = 0，第二個孩子1等。對每個節點的每個孩子重複這一點。然後你可以編寫一個方法來獲取相關ID列表，並使用它遍歷樹並找到正確的分區（每個級別剝去一個相對ID，以移動到下一級）。

Answer 2

基本實現

struct Node 
{ 
    vector<Node*> vChildNodes; 
    double x0,y0,x1,y1; 
}; 

...並且通常將需要添加遞歸拆分（） - 並找到（） - 方法。

你試圖實現的看起來類似於四叉樹 - 參見http://en.wikipedia.org/wiki/Quadtree或kd-tree，http://en.wikipedia.org/wiki/K-d_tree。你可以嘗試現有的實現。