我正在做一个项目，我需要能够从在方便点计算的大量（可能数百万到数十亿点）值集合中插入 3-D 框中任意点的标量潜在值（大致随机且均匀分布）不在规则网格上。我将计算轨迹并在沿轨迹的点处插入此势能的值，因此我的查询将始终位于最近使用的点附近的点。
在这方面没有太多背景知识的情况下，我最初的想法是将已知点放入 kd 树中，并在每次需要插入值时访问该树。另一种方法是对点进行排序和分箱，然后使用它们将值插入到矩形网格上，然后根据需要从常规网格中插入。
是否有其他更专业的数据结构和插值方法可能对这项任务有用？
我有一些使用插值流场信息进行粒子轨迹模拟的经验。在我们的案例中，我们需要使用单个时间相关流来模拟大量粒子的运动。因此，我们必须在轨迹期间执行复杂的插值（位置和时间）。
我们的结论是，在笛卡尔网格上映射流量信息更具成本效益。然后，使用整数运算和粒子位置，我们可以快速找到粒子在网格内的位置。之后，我们将使用三线性插值来获得粒子位置的流动特性。这是迄今为止最稳健、最有效的方法。此外（我发现这很重要）它可以很容易地在分布式内存环境（MPI）中并行化，因为您只需要分解笛卡尔网格（并确保粒子信息的正确传输）。由于我们必须加载大量数据，分布式内存并行是必不可少的。
我们为什么要使用笛卡尔映射的总结：
您可能会遇到的一些问题：