構建四叉樹

Question

我試圖使用四叉樹（一種四叉樹）來保存給定BMP中的信息。
我正在努力弄清楚如何構建給定任何BMP的樹。

基本上這樣的結構是這樣的，每一片葉子代表一個像素。每個節點有4個指針，每個指針指向圖像中其餘四個象限之一。因此每個節點將當前圖片分成4部分。當你在葉子時，你在一個特定的像素。

我不知道如何去構建一棵樹來映射某個圖像。假設圖像的尺寸是2的冪次，我該怎麼做。我明白，遞歸函數可能最優雅地做到這一點，但我正在努力弄清楚如何跟蹤圖像中的位置。

這是C++和目前我quadtree.h文件包括其中節點被定義爲與一個像素元件的結構和圖4點的指針到其它節點的節點*根。每個內部節點（非葉節點）應該保持所有4個RGB值的平均值。

我試圖做一個算法，但我想我可能需要在.h文件結構或兩項。有沒有更好的/更乾淨的方法來解決這個問題？

Answer 1

好吧，取決於你如何存儲你的位圖數據，你可能會做不同的事情。你是從文件中讀取它並直接放入樹中嗎？如果是這樣，.BMP文件（如果我沒有記錯的話）告訴你它們在頂部的寬度和高度，所以你可以真正使用它來確定你有多少級別，這可能會幫助你建立一些東西。另外，根據您的圖片的大小，您可以將所有像素存儲在二維節點數組中，並使樹排列在數組的頂部，以便您的葉子在數組中，並且其他一切都在別處。如果你這樣做，你可以編寫一些嵌套的循環，並且抓取四個節點的組，然後計算它們的平均值，並將它們集中在一起，然後對剛剛創建的節點執行相同的操作。這可能比從上到下構建樹更快，因爲你永遠不會平均超過四個像素，而從上到下構建平均需要除了最後一個以外的每個步驟平均超過四個像素。

如果你不想做在一個陣列中，最容易的事情，在我看來，將有每一個節點跟蹤它的X，Y座標。這將允許你做與數組基本相同的事情，但你不會只是插入索引。

對您有幫助嗎？你如何存儲位圖？什麼是最終目標？

Answer 2

STANN是目前最好的開源實現。

http://sites.google.com/a/compgeom.com/stann/

聰明人的話，使用伯爾尼等人的四叉樹構建算法和放棄時髦的樹操作。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.33.4634&rep=rep1&type=pdf

1. 排序所有Morton的順序分。
2. 計算每對連續點之間的四叉樹框長度。
3. 做一個最接近的最大值計算來找到父母/兄弟姐妹。

我正在爲OpenCl開發一個庫。我會在完成測試後發佈鏈接。