迭代八叉樹遍歷

Question

我無法弄清迭代八叉樹遍歷的過程，儘管我嘗試用二叉樹遍歷的方式來處理它。對於我的問題，我有八叉樹節點具有子和父指針，我想迭代和只存儲在堆棧中的葉節點。 此外，迭代遍歷比遞歸遍歷更快嗎？

Answer 1

這確實像二叉樹遍歷，但你需要存儲一些中間信息。遞歸算法本身不會變慢，但爲O（log8）遞歸調用（八叉樹中10億個元素大約需要10個級別）使用更多的堆棧空間。迭代算法也需要相同數量的空間來提高效率，但是您可以將它放入堆中，因爲您擔心堆棧可能會溢出。

遞歸你會怎麼做（僞）：

function traverse_rec (octree): 
    collect value // if there are values in your intermediate nodes 
    for child in children: 
     traverse_rec (child) 

在迭代算法得出的最簡單方法是使用深度優先或廣度優先遍歷堆棧或隊列：

function traverse_iter_dfs(octree): 
    stack = empty 
    push_stack(root_node) 
    while not empty (stack): 
     node = pop(stack) 
     collect value(node) 
     for child in children(node): 
      push_stack(child) 

用一個隊列替換堆棧，你先呼吸一下。但是，我們在O（7 *（log8 N））節點的區域存儲了一些我們尚未遍歷的節點。如果你仔細想想，那就是更小的邪惡，除非你需要穿越真的大樹。唯一的另一種方式是使用父指針，當你完成一個孩子，然後你需要以某種方式選擇下一個兄弟。

但是，如果您沒有預先存儲當前節點（相對於它的兄弟姐妹）的索引，則只能搜索父節點的所有節點，以便找到下一個兄弟節點，這實際上會增加一倍要完成的工作（對於每個節點，你不只是循環通過孩子，而且還通過兄弟姐妹）。此外，看起來你至少需要記住你已經訪問過哪些節點，因爲一般來說不確定是下降還是下降，否則返回樹（證明我錯了某人）。

總而言之，我會建議不要尋找這樣的解決方案。

Answer 2

取決於你的目標是什麼。您是否試圖查找節點是否可見，光線是否與其邊界框相交，或者節點中是否包含點？

我們假設你正在做最後一個，檢查一個點是否應該包含在節點中。我會向Octnode添加一個方法，該方法需要一個點並檢查它是否位於Octnode的邊界框內。如果它確實返回true，否則爲false，非常簡單。從這裏，調用一個從頭節點開始的向下鑽取方法，並檢查每個孩子，簡單的「for」循環，查看它所在的哪個Octnode，它最多隻能有一個。

這裏是你的迭代vs遞歸算法的作用。如果要迭代，只需將指針存儲到當前節點，並將該指針從頭節點交換到包含您的點的指針。然後繼續向下鑽，直到達到最大深度或找不到包含它的Octnode。如果你想要一個遞歸的解決方案，那麼你會在你找到點的Octnode上調用這個向下鑽取方法。

我不會說迭代與遞歸在速度方面有很大的性能差異，但它可以在內存性能方面有所不同。每次遞歸時，都會將另一個呼叫深度添加到堆棧中。如果你有一個大八叉樹，這可能會導致大量的呼叫，可能會吹你的堆棧。