如何從k-d樹中獲取一組矩形？

如果你看看維基百科條目k-d trees，你會看到這個點和平面的illustration將二維空間分成矩形。如何從k-d樹中獲取一組矩形？

我的問題是我如何得到矩形的結果集？我認爲每個到葉節點的「路徑」可能會給我一個界限。對於任意深度的N點，是否有一種通用的方法？

請注意，我不是要求的是超矩形結構的kd樹，其中給定的輸入是一組矩形，然後可以查詢該矩形以進行範圍搜索等。我的輸入是一組隨機點，並且我想輸出一組「矩形」或完全細分笛卡爾空間的矩形。

2012-11-19 Progger

這裏似乎有兩個問題。你正在尋找一種算法，從一組隨機點構建一棵k-d樹，或者是一個給定k-d樹的枚舉分割矩形集的算法？或兩者？ – eh9

k-d樹通常不存儲矩形，它們存儲分割軸。你可以簡單地通過寫一小段矩形分割代碼來實現這一點，該代碼基本上通過一個2D矩形，每個節點沿着分割軸切割，將兩個新矩形發送給子元素。 – Jerdak

感謝eh9的編輯。爲了澄清輸入是由一組隨機點構造的k-d樹，輸出是所得矩形的集合。

感謝Jerdak提供的「微不足道」的解決方案：事實上，只要從根節點開始沿着樹走下去，並在每個軸深處保持分割矩形。唯一的附加信息是原始矩形的外邊界。一旦訪問完所有節點，就可以返回完整集合。

2012-11-20 23:49:19 Progger

許多kD-Trees實際上存儲了每個子樹/葉子的邊界超級變化，以便在KNN搜索中可以完成更好的修剪。請注意，這些不是覆蓋所有空間的矩形，而是在沒有任何點的葉子之間留下間隙。我個人認爲他們更酷;-)

2012-12-14 20:56:39 jkflying

回答