四元樹

四元樹是一種基於數的數據結構，它的根節點下有四個子節點。四元樹經常利用遞歸法把一部分二維空間細分為四個象限或區域。這個區域可以是正方形、矩形或是任意形狀。這種數據結構被Raphael Finkel和J.L.bentley在1974年命名為四元樹。還有一種熟知的劃分法Q-樹法與此類似。

所有的四元樹都有以下特點：

●它可以分解空間為一種可編輯的細胞。

●每個細胞有個最大的容積。當達到這個最大值時，這個細胞就分裂了。

●這個樹的方向是沿著四元樹空間分解方向的。