空间数据的数据结构

我正在寻找一个良好的功能数据结构来存储空间（点）数据。数据结构应该允许对已经存在的点进行简单的epsilon查询。另外我需要经常修改数据。这意味着点可以移动并且应该能够在数据结构中更新。这可能可以使用正常的删除/添加来处理，但真正的移动可能会更快。空间数据的数据结构

现在我正在考虑使用quad/oct-trees（或更高版本），因为移动部分应该很容易做到。然而，就平衡而言，四叉树已知更糟糕。 KD-Trees可能是另一种选择，但更新似乎相当恶劣。另外，我能找到的大多数空间数据结构实现都只是程序性的，而我正在使用一种功能性语言。

2011-06-15 LiKao

只是为了澄清：是一个查询查询找到在给定点的指定距离内的点？ – aneccodeal 2011-06-15 15:40:16

KD树或四核/月树是合理的选择。在Haskell

实例：

两者都是很简单的编码为纯功能的数据结构。

2011-06-15 21:05:44

根据你如何使用它并快速移动点，你可能也会考虑sweep and prune。基本上，你保持点在一个维度排序（如x）。如果点很少改变位置，为每个模拟步骤运行插入排序实际上会很快。

（我想你的两个建议都已经相当不错了，顺便说一句）

2011-06-15 11:51:46

R-Trees和R * -Trees也是另一种解决方案，易于实现。

我在避难仿真中使用它们，更新步骤并没有那么慢。

2011-06-21 15:14:04 cynddl

看起来相当不错，虽然我不得不修理一些东西才能在这里工作。谢谢您的帮助... – LiKao 2011-07-03 13:17:03

This old paper作者：Overmars和van Leeuwen描述了伪四叉树 - 一种四叉树，它也可以平衡自己的插入和删除进度。插入和删除的摊销成本类似于O(log^d(n))，甚至可以与平衡完成量进行交易（您可以在论文中阅读更多关于此的内容）。

2011-06-21 20:04:45 axel22

回答