2

我正在查看 Kd-tree 并找到了该算法的一些实现。所有这些都是存储点（主要是 2d）。我想要实现的是在其中存储不同的形状，如矩形、三角形等。那么在 kd-trees 中是否可以存储形状？我有一些四叉树的代码。在那个形状被存储。

4

3 回答 3

3

这与用于四叉树的方法没有太大区别。

对于每个形状，您应该能够计算：

  • 它的质心。

  • 它的信封。

计算中位数时，使用质心。形状的包络应该适合四边形。在四边形中插入形状时，检查其包络是否穿过超平面。如果为真，则将形状存储在四边形中。如果为假，则将此形状放入左或右四边形构造调用的适当形状列表中。

干杯

于 2013-07-15T12:47:22.407 回答
2

这取决于一旦你有你的 kd-tree，你想对你的形状集做什么。假设您有一组矩形，并且您想快速找到完全包含在查询矩形中的所有矩形。然后使用 kd-tree（或者更好的是，范围树 imo）的适当方法是将矩形的最小和最大 x 和 y 坐标存储为 4 维点，并为 4 维点构建树. 然后，对于查询矩形 (a0,a1)x(b0,b1)，您使用树对 4 维点使用范围 (a0,+inf) x (-inf, a1) x 进行范围查询(b0, +inf) x (-inf, b1)。

于 2013-07-15T15:57:09.613 回答
1

这是 KD 树的自然扩展。

当您的树中只有点时：

  • 树中的节点对应于您空间的区域
  • 给定一个父节点 P 和子节点 C1, C2, ..., CN，子节点 Ci 互不相交，它们划分 P
  • 每个点 x恰好存在于树的一个叶节点中

当树中有卷时：

  • 树中的节点对应于您空间的区域
  • 给定一个父节点 P 和子节点 C1, C2, ..., CN，子节点 Ci 互不相交，它们划分 P
  • 每个卷 v 都存在于树的至少一个叶节点中（它“在”与它相交的任何叶节点中）
于 2013-07-15T17:58:22.153 回答