使用空间索引查找彼此范围内的点
让·皮埃尔·科夫
我正在尝试找到适合特定问题的空间索引结构：使用联合查找数据结构，我想连接\关联彼此在一定范围内的点。我有很多要点，我正在尝试通过使用更好的空间索引来优化现有解决方案。
现在，我正在使用一个简单的2D网格索引我的点图的每个宽度[阈值距离]正方形，然后通过搜索网格中相邻正方形中的点来寻找潜在的并集。
然后，我计算到相邻像元组合的平方欧几里得距离，并将其与平方阈值进行比较，然后使用联合查找结构（使用路径压缩等进行优化）来构建点组。
这是该方法的一些说明。单个黑点实际上代表了属于网格单元的一组点，而向外的彩色箭头代表了与外部点的实际距离比较。
（我还在检查属于同一单元的潜在连接点）。
通过使用此模式，可以确保我不会通过使用适当的“邻居单元”模式进行两次距离比较，该模式在迭代网格单元时不会与已测试的东西重叠。
问题是：这种方法甚至还不够快，我正在尝试用可能更快的方法代替“空间网格索引”方法。
我已经研究了四叉树作为解决此问题的合适空间指标，但我认为不适合解决此问题（我看不出有任何方法可以使用四叉树对特定单元格进行更有效的重复“邻居”检查四叉树），但也许我错了。
因此，我正在寻找一种更好的算法\数据结构来有效地索引我的点并查询它们的接近度。
提前致谢。
蒂尔曼
我有一些评论：
1）我认为您的问题等同于“空间连接”。空间连接采用两组几何图形，例如一组矩形R和一组点P，并为每个矩形找到该矩形中的所有点。在您的情况下，R是每个点周围的矩形（边长= 2 *最大距离），P是点集。搜索空间连接可能会为您提供一些有用的参考。
2）您可能想看看空间填充曲线。空间填充曲线为一组空间实体（点）创建线性顺序，其特性是，线性顺序中的闭合通常在空间中也闭合（反之亦然）。这在开发算法时可能很有用。
3）看看OpenVDB。OpenVDB具有高度优化的空间索引结构，以遍历“体素”单元及其相邻单元。
4）看一看PH树（免责声明：这是我自己的项目）。PH树有点像四叉树，但是使用低级位操作来优化导航。它也是Z顺序/ Morten顺序的（请参见上面的空间填充曲线）。您可以为每个点创建一个窗口查询，该查询返回该矩形内的所有点。据我所知，PH-树是此类操作最快的索引结构，尤其是在矩形中通常只有9个点的情况下。如果您对代码感兴趣，则V13的实现可能是最快的，但是V16应该更容易理解和修改。我在较旧的台式机上进行了尝试，使用大约1,000,000个点，每秒可以执行大约200,000个窗口查询，因此，大约需要5秒钟才能找到每个点的所有邻居。
如果您使用的是Java，则我的空间索引集合可能也很有用。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
在范围内使用索引键awk
- 2
Excel：在查找范围内使用通配符
- 3
使用 EPPlus 查找范围内的文本
- 4
查找落在给定范围内的索引
- 5
R：跨多列在彼此范围内的数据框中查找行
- 6
查找范围内的序列
- 7
查找日期在范围内
- 8
查找范围内的值
- 9
Excel / VBA：使用公式查找范围内的常数
- 10
使用wrapX在范围内查找矢量源特征
- 11
使用vba在excel范围内查找特定行
- 12
使用 XSLT 查找日期是否在日期范围内
- 13
在句子范围内查找单词范围
- 14
在一个点的x英里范围内查找对象
- 15
C ++生成范围内的（xyz）点
- 16
在Python中查找介于0到100之间的值范围内的索引
- 17
查找序列中两个数字在指定范围内的差异的索引的算法
- 18
检测值是否在彼此的范围内并取中点-MATLAB
- 19
MySQL：选择彼此在日期范围内的行
- 20
Scala查找范围内的缺失值
- 21
在彩色范围内查找中位数
- 22
查找范围内大于x的数字
- 23
查找日期范围内的可用日期
- 24
球拍-查找范围内最大的素数
- 25
查找值是否在范围内
- 26
查找给定范围内的缺失值
- 27
查找日期范围内的行数-MySQL
- 28
查找日期范围内的NA值
- 29
查找时间范围内的月份
我来说两句