平衡四叉树预设数据

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索引中也没有什么差别。