c - 在数组中搜索 3D 坐标的高效算法

Question

我有一个大型数组(>10^5 个条目)的 3D 坐标 r=(x, y, z)，其中 x、y 和 z 是 float 。这是在数组中搜索给定坐标 r' 并给出数组索引的最有效方法。请注意，r' 的准确度可能与 r 不同；比如说，如果数组存储了坐标 (1.5, 0.5, 0.0) 并且 r' 给出为 (1.49999, 0.49999, 0.0)，则算法应该正确地选择坐标。我正在用 C 语言开发代码。

如何使用哈希表的 O(1) 搜索能力来达到这一目的？由于与精度相关的问题，将坐标转换为字符串是不可能的。是否有任何特定的数据结构有助于 O(1) 算法？

谢谢

OnRoadCoder

Answer 1

检查 R-trees ，已经在一些 RDBMS 上实现，比如 SQLite 和(我认为)Postgres