分割大量的3D点数据

Question

我需要对一大批三维点进行分区（使用C++）。这些点以二进制浮点数组的形式存储在硬盘上，文件通常大于10GB。我需要将数据分成小一些的子集，每个子集的大小都小于1GB。由于我需要对数据执行某些算法（例如对象检测），因此子集中的点仍应具有相同的邻域。

我想我可以使用KD-Tree进行分区。但是如果我无法将所有点加载到RAM中，该如何有效地构造KD-Tree？也许我可以将文件映射为虚拟内存。然后，我可以保存属于一个段的每个三维点的指针并将其存储在KD-Tree的节点中。这样行得通吗？还有其他的想法吗？

感谢您的帮助。希望您能理解这个问题 :D

- blasalat

---

将您的任务分成块（每个块大约一百万个点），对其进行分区并将其写入文件，然后重复此过程并附加剩余的块 - 假设您的数据是随机分布的，则应该可以得到拆分平面的良好初始猜测 - 否则，您需要最初采样代表性数量以获得相同的行为。 - BeyelerStudios

静态结构，如网格或八叉树更容易实现。此外，您可以采用基于流的方法，在其中沿某个方向对点进行排序并按此顺序处理它们。邻近的点将在流中非常接近。 - Nico Schertler

你可以将点分成重叠的邻域，使其足够小以便于计算。 - user2249683

为了更好地了解我的工作内容：我有一份来自飞机的大型三维数据。我计划在这个点云中检测物体。但是计算所有东西需要很长时间，所以我想并行处理。为此，我需要将点云分割成大小相似的段。@AlexandruBarbarosie，我使用的数据集已经被减少了。如果我再次减少它们，详细程度就不足以执行任务。 - blasalat

你能对数据的范围和分布做出任何假设吗？还是需要去发现它们？换句话说，你能否说：“我知道它适合这个大小的盒子，并且我将把东西保存到以下重叠的盒子中。”然后从那里开始。 - btilly

Answer 1

你需要一个离线算法来计算（近似）中位数。给定一个大文件，找到它的中位数，然后将其分成两个较小的文件。应用此过程递归地沿着不同的维度得到k-d树（当较小的文件开始适合内存时，就不必再麻烦离线算法了）。

为了近似计算大文件的中位数，使用蓄水池抽样来获取一个大但在内存中的样本，然后运行一个内部中位数查找算法。或者，对于精确的中位数，计算（例如）近似的第45和55个百分位数，然后进行另一次传递以提取它们之间的数据点并精确计算中位数（除非样本异常不随机，在这种情况下请重试）。详细信息请参见Motwani-Raghavan随机算法书。

- David Eisenstat