平衡四叉樹預設數據

Question

PMR矩形四叉樹是一個四叉樹，每個葉子中有一個（矩形）對象列表。這被稱爲一個桶。

此四叉樹的結構取決於插入元素的順序。
該四叉樹的發明者提出爲預先已知（靜態）的數據實現平衡四叉樹，這樣插入的（矩形）對象應該用x和y座標預先排序。

究竟是什麼意思排序的x和y座標來實現平衡四叉樹？
Asume我們採取長方形的SW角，這是否意味着按x排序，如果相等x按y排序？或者說這意味着第一個元素是最小的x，第二個是最小的y（獨立於x）？

該主題的聖經（Hanan Samet：Multidimensional and Metric Search Structures）並沒有解釋這一點。

Answer 1

似乎是一個話題，其中的訣竅是不是真的普及，我來回答它自己：

元素的預排列的順序被添加到四叉樹應該在莫頓順序。 （另請參見Hanan Samet的文章） Morton索引從給定的兩個（x，y）座標計算出一個int值，兩個座標相近的方式在它們的morton索引中也沒有什麼差別。