如何即时索引附近的 3D 点？
How to index nearby 3D points on the fly?
在物理模拟（例如 n 体系统）中，有时需要跟踪哪些粒子（3D 中的点 space）足够近以在某些情况下相互作用（在某些截止距离 d 内）一种指数。但是，粒子可以四处移动，因此有必要更新索引，最好是在运行时更新，而无需完全重新计算。此外，为了提高计算相互作用的效率，有必要以图块的形式保留相互作用粒子的列表：图块是一个固定大小的数组（例如 32x32），其中行和列是粒子，几乎每个行粒子都很接近足以与几乎每个列粒子交互（并且阵列跟踪哪些粒子实际交互）。
可以使用什么算法来执行此操作？
这里有更详细的问题描述：
初始构造：给定一个 3D 点列表 space（大约几千到几百万，存储为浮点数组），生成一个图块列表固定大小 (NxN)，其中每个图块有两个点列表（N 行点和 N 列点），以及一个布尔数组 NxN，它描述是否应计算每个行和列粒子之间的相互作用，以及：
一个。 distance(p1,p2) < d 的每一对点 p1,p2 在至少一个图块中找到并标记为正在计算（没有丢失交互），并且
b。如果任何一对点在一个以上的图块中，它只被标记为在最多一个图块中的布尔数组中计算（没有重复），
并且如果可能，tile 的数量也相对较少（但这不如能够有效地更新 tile 重要）
更新步骤：如果点的位置略有变化（远小于d），以最快的方式更新图块列表，以便他们仍然满足相同的条件a和b（此步骤重复多次）
可以保留任何有助于此的必要数据结构，例如每个图块的边界框，或像四叉树这样的空间索引。计算每个更新步骤的所有粒子成对距离可能太慢了（在任何情况下，我们只关心靠近的粒子，因此我们可以仅通过沿单个维度排序来跳过大多数可能的距离对）。此外，保持所有粒子位置的完整（四叉树或类似）索引可能太慢。另一方面，在某种规则的网格上构建瓷砖非常好。 3D 中每单位体积的粒子密度 space 大致恒定，因此可以从（基本上）固定大小的边界框构建图块。
举个典型的scale/properties这类问题的例子，假设有100万个粒子，排列成random packing个直径为1个单位的球体组成一个立方体尺寸大约为 100x100x100。假设截止距离为 5 个单位，因此通常每个粒子会与 (2*5)**3 或 ~1000 个左右的其他粒子相互作用。磁贴大小为 32x32。大约有 1e+9 个相互作用的粒子对，因此最小可能的图块数是 ~1e+6。现在假设每次位置改变时，粒子都会在随机方向上移动大约 0.0001 个单位的距离，但总是以这样的方式移动，即它们与任何其他粒子至少相距 1 个单位，并且每单位体积的粒子的典型密度保持不变相同的。通常会有数百万个这样的位置更新步骤。由于移动，每一步新创建的交互对的数量是（信封背面）(10**2 * 6 * 0.0001 / 10**3) * 1e+9 = 60000，因此原则上可以通过将 60000 个粒子在其原始图块中标记为非交互来处理一个更新步骤，并且添加最多 60000 个新图块（大部分是空的 - 每对新相互作用的粒子一个）。这将很快达到大多数图块为空的程度，因此绝对有必要经常以某种方式 combine/merge 图块 - 但是如果不完全重建图块列表如何做到这一点？
P.S。描述这与典型的空间索引（例如八叉树）场景有何不同可能很有用：我们只关心将靠近的点分组到图块中，而不是查找哪些点在任意边界框中或哪些点最接近查询点 - 更接近于对查询和 b 进行聚类。 space 中点的密度非常恒定，c。索引必须经常更新，但大多数移动都是微小的
我建议使用以下算法。例如，我们有 1x1x1 的立方体，截止距离为 0.001
- 让我们选择三个基本锚点：(0,0,0) (0,1,0) (1,0,0)
- 将大小为 1000 ( 1 / 0.001) 的数组与每个锚点相关联
- 在每个规则点中添加三个数字。我们将在这些字段中存储给定点和每个锚点之间的距离
- 同时这个距离会作为锚点内部数组的索引。例如。 0.4324 表示索引 432.
- 让我们将点集存储在每三个数组中
- 每次更新点时计算规则点与每个锚点的距离
- 更新期间在数组中的集合之间移动点
给定的结构会给你一个简单的方法来找到所有更近的点：它是三个集合之间的交集。我们根据点和锚点之间的距离来选择这些集合。
简单来说就是三个球体的交集。如果你想擦除这个交叉点的角，可能你需要对结果应用额外的过滤。
不确定我的推理是否合理，但我有一个想法：
将您的 space 分成一个 3d 立方体网格，像这样在三个维度上：
立方体的边长为 d。然后执行以下操作：
- 将所有点分配给包含它们的所有立方体；这很快，因为您可以仅从它们的坐标
导出一个点的立方体
- 现在检查以下内容：
- 将立方体左上角的所有点标记为碰撞；它们相距不到
d。此外，space 中的每个“四分之一立方体”只是一个立方体的左上四分之一，因此您不会检查同一对立方体两次。
- 检查
(p, q) 类型的碰撞，其中 p 是左上四分位数中的一个点，q 是 不[=51= 中的一个点] 在左上四分位数。这样，您将最多再次检查每两个点之间的碰撞一次，因为每对分位数恰好检查一次。
由于每对点要么在同一个四分位数中，要么在相邻的四分位数中，它们将由第一个或第二个算法检查。此外，由于点大致均匀分布，您的运行时间远小于 n^2（n=无点）；总的来说，它是 k^2（k = 每个四分位数没有点，这似乎是近似恒定的）。
在更新步骤中，您只需检查：
- 如果一个点穿过一个框的边界，这应该很快，因为您一次可以查看一个坐标，并且框的边界是
d/2 的简单倍数
- 如上所述检查点的碰撞
要创建图块，请将 space 分成第二个（非重叠）立方体网格，其宽度已选择 s.t。落入给定立方体的两个几乎相互作用的粒子之间的平均中心数小于瓷砖的宽度（即 32）。由于每个粒子预计会与 300-500 个粒子相互作用，因此宽度将比 d.
小得多
然后，在检查步骤 1 和 2 中的相互作用时，根据相互作用中心的坐标将粒子相互作用分配给这些新立方体。为每个立方体分配一个图块，并在图块中标记分配给该立方体的相互作用粒子。可视化：
进一步的优化可能是考虑一个点在立方体中最近邻居的距离，并从中得出至少需要多少更新步骤才能改变该点的碰撞状态；然后在这么多步骤中忽略这一点。
考虑使用 Barnes-Hut 算法或类似算法。 2D 模拟将使用四叉树数据结构来存储粒子，而 3D 模拟将使用八叉树。
使用树结构的好处是它存储粒子的方式是通过遍历树可以快速找到附近的粒子，而远处的粒子在可以忽略的遍历路径中。
维基百科对算法有很好的描述：
巴恩斯小屋树
在三维 n 体模拟中，Barnes–Hut 算法递归地将 n 体分组，将它们存储在八叉树（或二维模拟中的四叉树）中。这棵树中的每个节点代表三维 space 的一个区域。最上面的节点代表整个 space，它的八个子节点代表 space 的八个八分圆。 space 被递归地细分为八分圆，直到每个细分包含 0 或 1 个物体（某些区域在其所有八分圆中都没有物体）。八叉树中有两种类型的节点：内部节点和外部节点。外部节点没有子节点，并且为空或表示单个主体。每个内部节点代表其下方的一组物体，并存储其所有子物体的质心和总质量。
在物理模拟（例如 n 体系统）中，有时需要跟踪哪些粒子（3D 中的点 space）足够近以在某些情况下相互作用（在某些截止距离 d 内）一种指数。但是，粒子可以四处移动，因此有必要更新索引，最好是在运行时更新，而无需完全重新计算。此外，为了提高计算相互作用的效率，有必要以图块的形式保留相互作用粒子的列表：图块是一个固定大小的数组（例如 32x32），其中行和列是粒子，几乎每个行粒子都很接近足以与几乎每个列粒子交互（并且阵列跟踪哪些粒子实际交互）。
可以使用什么算法来执行此操作？
这里有更详细的问题描述：
初始构造：给定一个 3D 点列表 space（大约几千到几百万，存储为浮点数组），生成一个图块列表固定大小 (NxN)，其中每个图块有两个点列表（N 行点和 N 列点），以及一个布尔数组 NxN，它描述是否应计算每个行和列粒子之间的相互作用，以及：
一个。 distance(p1,p2) < d 的每一对点 p1,p2 在至少一个图块中找到并标记为正在计算（没有丢失交互），并且
b。如果任何一对点在一个以上的图块中，它只被标记为在最多一个图块中的布尔数组中计算（没有重复），
并且如果可能，tile 的数量也相对较少（但这不如能够有效地更新 tile 重要）
更新步骤：如果点的位置略有变化（远小于d），以最快的方式更新图块列表，以便他们仍然满足相同的条件a和b（此步骤重复多次）
可以保留任何有助于此的必要数据结构，例如每个图块的边界框，或像四叉树这样的空间索引。计算每个更新步骤的所有粒子成对距离可能太慢了（在任何情况下，我们只关心靠近的粒子，因此我们可以仅通过沿单个维度排序来跳过大多数可能的距离对）。此外，保持所有粒子位置的完整（四叉树或类似）索引可能太慢。另一方面，在某种规则的网格上构建瓷砖非常好。 3D 中每单位体积的粒子密度 space 大致恒定，因此可以从（基本上）固定大小的边界框构建图块。
举个典型的scale/properties这类问题的例子，假设有100万个粒子，排列成random packing个直径为1个单位的球体组成一个立方体尺寸大约为 100x100x100。假设截止距离为 5 个单位，因此通常每个粒子会与 (2*5)**3 或 ~1000 个左右的其他粒子相互作用。磁贴大小为 32x32。大约有 1e+9 个相互作用的粒子对，因此最小可能的图块数是 ~1e+6。现在假设每次位置改变时，粒子都会在随机方向上移动大约 0.0001 个单位的距离，但总是以这样的方式移动，即它们与任何其他粒子至少相距 1 个单位，并且每单位体积的粒子的典型密度保持不变相同的。通常会有数百万个这样的位置更新步骤。由于移动，每一步新创建的交互对的数量是（信封背面）(10**2 * 6 * 0.0001 / 10**3) * 1e+9 = 60000，因此原则上可以通过将 60000 个粒子在其原始图块中标记为非交互来处理一个更新步骤，并且添加最多 60000 个新图块（大部分是空的 - 每对新相互作用的粒子一个）。这将很快达到大多数图块为空的程度，因此绝对有必要经常以某种方式 combine/merge 图块 - 但是如果不完全重建图块列表如何做到这一点？
P.S。描述这与典型的空间索引（例如八叉树）场景有何不同可能很有用：我们只关心将靠近的点分组到图块中，而不是查找哪些点在任意边界框中或哪些点最接近查询点 - 更接近于对查询和 b 进行聚类。 space 中点的密度非常恒定，c。索引必须经常更新，但大多数移动都是微小的
我建议使用以下算法。例如，我们有 1x1x1 的立方体，截止距离为 0.001
- 让我们选择三个基本锚点：(0,0,0) (0,1,0) (1,0,0)
- 将大小为 1000 ( 1 / 0.001) 的数组与每个锚点相关联
- 在每个规则点中添加三个数字。我们将在这些字段中存储给定点和每个锚点之间的距离
- 同时这个距离会作为锚点内部数组的索引。例如。 0.4324 表示索引 432.
- 让我们将点集存储在每三个数组中
- 每次更新点时计算规则点与每个锚点的距离
- 更新期间在数组中的集合之间移动点
给定的结构会给你一个简单的方法来找到所有更近的点：它是三个集合之间的交集。我们根据点和锚点之间的距离来选择这些集合。
简单来说就是三个球体的交集。如果你想擦除这个交叉点的角，可能你需要对结果应用额外的过滤。
不确定我的推理是否合理，但我有一个想法：
将您的 space 分成一个 3d 立方体网格，像这样在三个维度上：
立方体的边长为 d。然后执行以下操作：
- 将所有点分配给包含它们的所有立方体；这很快，因为您可以仅从它们的坐标 导出一个点的立方体
- 现在检查以下内容：
- 将立方体左上角的所有点标记为碰撞；它们相距不到
d。此外，space 中的每个“四分之一立方体”只是一个立方体的左上四分之一，因此您不会检查同一对立方体两次。 - 检查
(p, q)类型的碰撞，其中p是左上四分位数中的一个点，q是 不[=51= 中的一个点] 在左上四分位数。这样，您将最多再次检查每两个点之间的碰撞一次，因为每对分位数恰好检查一次。
- 将立方体左上角的所有点标记为碰撞；它们相距不到
由于每对点要么在同一个四分位数中，要么在相邻的四分位数中，它们将由第一个或第二个算法检查。此外，由于点大致均匀分布，您的运行时间远小于 n^2（n=无点）；总的来说，它是 k^2（k = 每个四分位数没有点，这似乎是近似恒定的）。
在更新步骤中，您只需检查：
- 如果一个点穿过一个框的边界，这应该很快，因为您一次可以查看一个坐标，并且框的边界是
d/2 的简单倍数
- 如上所述检查点的碰撞
要创建图块，请将 space 分成第二个（非重叠）立方体网格，其宽度已选择 s.t。落入给定立方体的两个几乎相互作用的粒子之间的平均中心数小于瓷砖的宽度（即 32）。由于每个粒子预计会与 300-500 个粒子相互作用，因此宽度将比 d.
然后，在检查步骤 1 和 2 中的相互作用时，根据相互作用中心的坐标将粒子相互作用分配给这些新立方体。为每个立方体分配一个图块，并在图块中标记分配给该立方体的相互作用粒子。可视化：
进一步的优化可能是考虑一个点在立方体中最近邻居的距离，并从中得出至少需要多少更新步骤才能改变该点的碰撞状态；然后在这么多步骤中忽略这一点。
考虑使用 Barnes-Hut 算法或类似算法。 2D 模拟将使用四叉树数据结构来存储粒子，而 3D 模拟将使用八叉树。
使用树结构的好处是它存储粒子的方式是通过遍历树可以快速找到附近的粒子，而远处的粒子在可以忽略的遍历路径中。
维基百科对算法有很好的描述： 巴恩斯小屋树 在三维 n 体模拟中，Barnes–Hut 算法递归地将 n 体分组，将它们存储在八叉树（或二维模拟中的四叉树）中。这棵树中的每个节点代表三维 space 的一个区域。最上面的节点代表整个 space，它的八个子节点代表 space 的八个八分圆。 space 被递归地细分为八分圆，直到每个细分包含 0 或 1 个物体（某些区域在其所有八分圆中都没有物体）。八叉树中有两种类型的节点：内部节点和外部节点。外部节点没有子节点，并且为空或表示单个主体。每个内部节点代表其下方的一组物体，并存储其所有子物体的质心和总质量。