在KD樹中存儲矩形/圓/三角形

我在看Kd-tree並發現了這種算法的一些實現。所有這些都是存儲點（2d主要是個案）。我試圖實現的是在其中存儲不同的形狀，如矩形，三角形等。那麼有可能在kd-trees中存儲形狀？我有一些四叉樹的代碼。在那個形狀被存儲。在KD樹中存儲矩形/圓/三角形

來源

2013-07-15 Faisal Hafeez

二？你想在哪裏儲存形狀？有分的好處是它們不能被切斷。 –

我想你可以修改一個kd-tree來爲形狀增加葉子。按照慣例，非葉節點將是點。如何確定這些點可能有點複雜，需要確定如何處理分割形狀。 – Dukeling

請看看r-trees！ –

這與用於四叉樹的方法沒有太大區別。

對於每個形狀，你應該能夠計算：

它的質心。
它的信封。

當計算中位數時，請使用質心。形狀的包絡應該適合四邊形。在四邊形中插入形狀時，請檢查它的信封是否跨越超平面。如果屬實，則將形狀存儲在四邊形中。如果爲false，則將此形狀放置在您的左或右方形施工調用的適當形狀列表中。

乾杯

來源

2013-07-15 12:47:22 David

我應該如何檢查矩形將在左側還是右側？ –

矩形的包絡由其xMin/xMax，yMin，yMax，zMin，zMax表徵。您可以將這些座標與超平面座標進行比較。 – David

這取決於你想一旦你有你的kd樹爲它使用自己設置的形狀做什麼。假設您有一組矩形，並且您想要快速查找完全包含在查詢矩形中的所有矩形。然後，使用kd-tree（或更好的，範圍樹imo）的適當方式是將矩形的最小和最大x和y座標存儲爲四維點，併爲四維點構建樹。然後，對於查詢矩形（a0，a1）x（b0，b1），您可以使用樹在四維點上使用範圍（a0，+ inf）x（-inf，a1）x （b0，+ inf）x（-inf，b1）。

來源

2013-07-15 15:57:09 user2566092

我想做的完全一樣，我有一些矩形，我想查找矩形內的矩形。 http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C。這個項目使用四叉樹完成同樣的工作，但我想在四叉樹中做到這一點。 –

你是什麼意思的4維。你的意思是在kd-tree節點中保存4個點。我在想保存System.Drawing.Rectangle對象。 –

我的意思是，如果你的矩形具有最小的x座標x0和最大的x座標x1，以及類似的最小的y座標y0和最大的y座標y1，那麼你將該矩形存儲爲點（x0，x1，y0，y1 ）。然後查詢就像我描述的那樣。 – user2566092

這是KD樹的自然延伸。

當你在你的樹只有兩點：

樹中的節點對應於你的空間的區域
鑑於父節點P和子節點C1，C2，...，CN，孩子節點C i是相互脫節，他們劃分P
每個點x是存在於樹

的正好一個葉節點。當你哈ve在樹體積：

樹中的節點對應於你的空間的區域
鑑於父節點P和子節點C1，C2，...，CN，孩子節點C i是互不相交和它們分區P
每個容積v存在於樹的至少一個葉節點（它的「中的」使得它與相交的任何葉節點），如果切割分割的形狀中，會發生什麼

來源

2013-07-15 17:58:22

我應該如何檢查矩形將在左側還是右側？ –

如果它相交雙方，它應該在兩邊... –

我該如何檢查？我正在檢查要添加的當前節點和節點的x/y並向左或向右添加它。 –

在KD樹中存儲矩形/圓/三角形

回答

相關問題