高效的数据结构用于存储3D点

Question

我正在寻找用于存储3D点（x，y，z）的高效数据结构。将点存储在数据结构中的效果应生成更加内存高效的结构和更快速的搜索特定坐标集。这些3D点映射到特定的ID，因此应该能够跟踪每个坐标集。我正在寻找任何可用的实现。

其中x，y，z给出每个节点的笛卡尔坐标。

id x y z

1 14.566132 34.873772 7.857000

2 16.022520 33.760513 7.047000

3 17.542000 32.604973 6.885001

4 19.163984 32.022469 5.913000

5 20.448090 30.822802 4.860000

6 21.897903 28.881084 3.402000

7 18.461960 30.289471 8.586000

8 19.420759 28.730757 9.558000

坐标数量可能非常巨大，可能约为100万个。

提前致谢！

- Yoko

---

你目前考虑了哪些选项？ - Oliver Charlesworth

考虑过八叉树（https://en.wikipedia.org/wiki/Octree）和R树（https://en.wikipedia.org/wiki/R-tree），但没有找到适合存储3D坐标的好实现。 - Yoko

你应该明确你的重点是什么。代码可读性（简单的结构数组），自动向量化（数组结构），或者可能是良好的插入/搜索时间（八叉树）？例如，在N体计算中，八叉树是最好的方法，因为它具有O(nlog n)的时间复杂度。 - Hopobcn

100万个浮点三元组远远不算巨大。 - o9000

使用比顺序列表更节省内存的数据结构来获得更快的搜索时间是不太可能的。通常情况下，这是一种权衡。如果你想要更快的搜索速度，那么你可能需要使用更多的内存。如果你想要使用更少的内存，那么你就必须承受更慢的搜索时间。 - Jim Mischel

Answer 1

更节省内存的数据结构

相对于什么更节省内存呢？如果是相对于列表，那就需要压缩。

更快速地搜索特定坐标集合

如果您想从一组坐标中找到k个最接近的点，则Ball树是一个不错的选择。

如果要搜索一个体积，则四叉树（或八叉树）效果更好。

- o9000

---

比将所有内容存储在列表中更节省内存。结构体坐标 { 双精度 x; 双精度 y; 双精度 z; };主函数(){ std::vector<coordinate> 列表; 坐标 a = 坐标(2.123123,2.1231,3.112);列表.push_pack(a); } - Yoko

Answer 2

我听说你要查找的坐标已经与现有结构完全匹配。根据你的空间分布情况，你可以创建一个哈希函数来获取坐标并尝试生成相对独特的内容，然后使用标准哈希映射。大多数现代语言都提供了某种哈希映射实现，因此你只需要为你的坐标提供适当的哈希值即可。

如果你需要查找测试坐标附近的坐标，则可以使用balltree或octree等方法，但这似乎不是你需要的。

- Aiken Drum

---

使用哈希函数时，需要逐位比较它们是否相等。如果查找值是浮点运算的结果，由于精度损失，这可能不成立。如果是这种情况，哈希函数就必须考虑最大误差，并在实际进行哈希之前丢弃最不重要的位。但我认为原帖作者对自己的需求有些困惑。 - o9000

我知道，这就是为什么我将我的答案限定为仅适用于完全匹配的原因。如果想要在某个epsilon范围内进行匹配，从底部删除一些位只会统一一些邻居（在3D坐标的情况下约为八分之一）。使用浮点数更难以可视化，但请考虑接近整数邻居255和256之间的按位差异。我不建议这样做。基于epsilon的搜索需要不同的数据结构。 - Aiken Drum

Answer 3

你可以使用一个 struct：

struct coordinate
{
   double x;
   double y;
   double z;
} points[1000000];

- Rajeev Singh

---

一个小的改进：考虑到他似乎只有7个有效数字，他可能想使用float而不是double。对于3D应用程序来说，这并不是一个罕见的选择... - H. Guijt

你可以自行决定要存储多少精确值！ - Rajeev Singh

那只是一种结构，我正在寻找用于存储3D坐标的数据结构。在这个结构中，我将不得不对特定的坐标集进行暴力搜索，这不是我想要的。 - Yoko