graphics - 有没有一种算法，可以将空间划分为 N 个给定随机数 N 的分区，其中 N<50

Question

我阅读了有关空间分区的 R-Tree、kd-tree、边界间隔层次结构等。我发现这些数据结构对于空间查询很有用。虽然，他们做分区，但我不知道如何从数据结构中检索这些分区。所以，我的问题归结为“给定一个数字 N 和一个包含 X 个多边形的地图，我可以得到 N 个包含大约相等数量多边形的分区吗？”

Answer 1

好吧，如果你想要恰好 N 个分区，那么 R-Tree 的任何常见批量加载策略都应该有效。它不一定是最佳的，但您可以强制它们生成大小大致相等的 N 个分区。

kd-tree 将包含既不在左侧也不在右侧的对象。但是你可以使用 kd-tree 批量加载策略并修改它以产生 N 个分区。实际上，另一种简单但有时非常有效的批量加载和 R-tree 方法。

当您将 N 限制为 2 的幂，或者甚至更好的d某个数字的 th 幂时，拆分通常会变得更好。因此，将 3D 数据集拆分为 9 页比将其拆分为 8 页更容易实现。