-1

PMR 矩形四叉树是一个四叉树,它在每个叶子中都有一个(矩形)对象列表。这称为桶。

此四叉树的结构取决于插入元素的顺序。
该四叉树的发明者提议为预先已知(静态)的数据实现平衡四叉树,这样要插入的(矩形)对象应按 x 和 y 坐标进行预排序。

通过 x 和 y 坐标排序以实现平衡的四叉树究竟是什么意思?
假设我们取矩形的 SW 角,这是否意味着按 x 排序,如果相等 x 按 y 排序?或者这是否意味着第一个元素是最小的 x,第二个是最小的 y(与 x 无关)?

该主题的圣经(Hanan Samet:多维和度量搜索结构)没有解释这一点。

4

1 回答 1

1

似乎是一个知识并不普及的话题,我必须自己回答:

要添加到四叉树的元素的预排序顺序应该是 morton 顺序。(另见 Hanan Samet 的论文) morton 索引从给定的两个 (x,y) 坐标计算 int 值,在某种程度上,两个靠近的坐标在它们的 morton 索引上也几乎没有差异。

于 2013-04-17T09:24:43.290 回答