algorithm - 包含点的树 - 需要改进

Question

目前，我正在制作自己的结构来保存二维空间中的点。我知道有很多现成的算法和树，但我想要一些轻量级的东西。所以我在每个节点内部都有 (x, y) 点，每个节点包含 4 个子节点:topLeft、topRight、botLeft、botRight 下一个节点。

插入:

每个新节点的插入都取决于它的位置。
如果树为空，插入新节点/如果树不为空，转到第一个节点并执行:
1.判断当前节点相对于新节点的位置。
2.如果是e。 G。 topLeft 且未被占用则插入新节点。
3. 如果位置topLeft被占用，转到该节点并重复。

删除:

我需要的结构不需要具有“删除特定节点”功能，因此如果完成工作，析构函数将递归删除整个树。

检查节点是否在特定区域内:

如果树不为空，则转到第一个节点，然后:
1. 检查给定区域的 x 是否小于节点的 x，区域的 y 是否小于节点的 y，如果是则转到 topLeft 子节点(如果存在)。
2. topRight 相同(检查区域的 x + 宽度位置和 y)。
3. botRight 相同(检查区域的 x + 宽度和 y + 高度)。
4. botLeft 相同(检查区域的 x 和 y + 高度)。
5. 检查当前节点是否在区域内，如果它是你想用一个点做的事情。递归返回并重复。

这就是我的结构的样子，图像显示了将针对特定区域检查哪些键(橙色 颜色): link

我的问题是，有没有更好的算法？我可以改进什么？我看到了四叉树，但它似乎有所不同，它包含更多数据。我需要一些可以轻松保持 2D 移动物体的东西。感谢您的帮助。

Answer 1

您拥有的基本上是四叉树，但您使用数据进行拆分而不是典型的中间树。

您可以通过切换到 KD tree 来稍微改进系统.它是相似的，除了在每个点上你沿着一个维度分割。主要区别在于每个节点只有两个指针(而不是 4 个)，因此可以节省大约一半的内存。

另一件事是，你会分割你的空间，直到你得到 1 分。因为现代 CPU 做的事情真的很花哨，对于小值，线性搜索会比遍历树更快。所以我只会在你已经有 50-100 分的情况下拆分一个空间。这也将节省一堆根本不需要存储的指针。

如果您对自己的点数分布有所了解，您可能会做得更好。如果分布有点均匀，您可以简单地将空间分成均匀的单元格并将这些点存储在关联的单元格中。一条经验法则是，如果你有 N 个点，你应该有 sqrt(N) 个单元，但你应该尝试看看什么最有效。