给定一大组（数万到数百万）表示为 3D 笛卡尔向量的无序点，有什么好的算法可以制作一个包含所有点的规则方形网格（用户定义的间距）？一些限制：
为了在 2D 中说明，给定这组点：
对于某些网格间距 X，算法的一个可能返回值将是这些红点的坐标（虚线仅用于说明目的）：
对于网格间距 X/2，算法的一个可能返回值是这些红点的坐标（虚线仅用于说明目的）：
对于任何感兴趣的人，我正在处理的无序点是大蛋白质分子的原子坐标，就像你可以从 .pdb 文件中得到的一样。
Python 是解决方案的首选，尽管伪代码也很好。
编辑：我认为我对我需要的第一个描述可能有点模糊，所以我添加了一些约束和图像以澄清事情。
我建议你制作一棵kd 树。它快速、简单且易于实现：
和维基百科代码：
class Node: pass
def kdtree(point_list, depth=0):
if not point_list:
return
# Select axis based on depth so that axis cycles through all valid values
k = len(point_list[0]) # assumes all points have the same dimension
axis = depth % k
# Sort point list and choose median as pivot element
point_list.sort(key=lambda point: point[axis])
median = len(point_list) // 2 # choose median
# Create node and construct subtrees
node = Node()
node.location = point_list[median]
node.left_child = kdtree(point_list[:median], depth + 1)
node.right_child = kdtree(point_list[median + 1:], depth + 1)
return node
但是，您必须稍微修改它以适应您的约束。
因为您要求用户指定间距的规则方形网格，所以听起来应该是一种相当简单的方法。
首先通过数据来计算每个维度中的最小和最大坐标。计算出覆盖最大和最小距离所需的用户指定间距的步数。
再次传递数据以将每个点分配给网格中的一个单元格，使用一个点位于每个坐标的最小值和指定间距的网格（例如 X_cell = Math.floor((x_i - x_min) / 间距） ）。使用字典或数组来记录每个单元格中的点数。
现在打印出至少有一个点的单元格的坐标。
你确实有一些我没有尝试优化的自由：除非最小和最大坐标之间的距离是网格间距的精确倍数，否则会有一些斜率允许你滑动网格并仍然包含它所有点：目前网格从最低点的位置开始，但它可能在最高点之前结束，所以你有空间在每个维度上向下移动一点。当你这样做时，一些点会从一个单元格移动到另一个单元格，并且占用的单元格的数量会发生变化。
如果您一次只考虑一个维度的移动，您可以合理有效地计算出会发生什么。计算出每个点在该维度中的距离与其单元格的该维度中的最大坐标之间的距离，然后对这些值进行排序。当您向下移动网格时，与其最大坐标距离最小的点将首先交换单元格，您可以通过按排序顺序移动这些点来逐个遍历这些点。如果您在执行此操作时更新单元格中的点数，您可以计算出哪个班次使占用的单元格数量最小化。
当然，您需要担心三个方面。您可以一次处理一个，直到您减少单元格的数量。这是局部最小值，但可能不是全局最小值。寻找其他局部最小值的一种方法是从随机选择的起点重新开始。
找到一个包含所有点的最小面积正方形。反复将每个方格细分为 4 个子方格（因此从 1 到 4 到 16 到 64 到……）。在其中一个方格变空之前停止。不难证明，生成的网格最多比最优解粗四倍（关键见解：一个空方格保证包含任何网格中的至少一个方格，至少两倍细）。
可能通过引入随机平移可以减少该常数。
我有二维网格聚类的经验，并在 C# 代码中实现了一个示例。 http://kunuk.wordpress.com/2011/09/15/clustering-grid-cluster/
这可以处理步骤处理步骤 1、2 和 4。您必须修改代码并将其更新到 3D 空间。希望这能给你一些想法。
代码在 O(m*n) 中运行，其中 m 是网格数，n 是点数。
