用于将网格放置在无序点集上的算法

Question

给定一组大的(数万到数百万)无序点表示为3D笛卡尔向量,用于制作包含所有点的常规方形网格(用户定义的间距)的好算法是什么？一些限制:

1. 网格需要是正方形和规则的
2. 我需要能够调整网格间距(其中一个方格的边长),理想情况下是单个变量
3. 我想要一个最小尺寸的网格,即网格中的每个"块"应至少包含一个无序点,并且每个无序点都应包含在"块"中
4. 算法的返回值应该是网格点的坐标列表

为了说明2D,给出了这一点:

对于某些网格间距X,算法的一个可能的返回值将是这些红点的坐标(虚线仅用于说明目的):

对于网格间距X/2,算法的一个可能的返回值是这些红点的坐标(虚线仅用于说明目的):

对于任何感兴趣的人来说,我正在使用的无序点是大蛋白分子的原子坐标,就像你可以从.pdb文件中得到的那样.

Python是解决方案的首选,尽管伪代码也很好.

编辑:我认为我对我所需要的第一次描述可能有点模糊,所以我添加了一些约束和图像以澄清事情.

Answer 1

我建议你做一棵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

但是，您必须对其稍加修改以适应您的约束。

Answer 2

因为您要求用户指定间距的规则方形网格，所以听起来一个相当简单的方法应该可行。

首先通过数据计算出每个维度的最小和最大坐标。计算出覆盖最大值和最小值之间的距离所需的用户指定间距的步数。

再次传递数据，将每个点分配给网格中的一个单元格，使用每个坐标最小值处有一个点和指定间距的网格（例如 X_cell = Math.floor((x_i - x_min) / 间距） ）。使用字典或数组记录每个单元格中的点数。

现在打印出其中至少有一个点的单元格的坐标。

你确实有一些我没有尝试优化的自由度：除非最小和最大坐标之间的距离是网格间距的精确倍数，否则会有一些倾斜，允许你滑动网格并仍然包含它所有点：目前网格从最低点的位置开始，但它可能在最高点之前结束，因此您有空间在每个维度上将其向下移动一点。当您执行此操作时，某些点将从单元格移动到单元格，并且占用的单元格数量也会发生变化。

如果您一次只考虑一个维度的移动，您可以相当有效地计算出将会发生什么。计算出该维度中每个点与其单元格该维度中的最大坐标之间的距离，然后对这些值进行排序。当您向下移动网格时，与其最大坐标距离最小的点将首先交换单元格，您可以通过按排序顺序遍历这些点来逐个迭代它们。如果您在执行此操作时更新单元格中的点数，您可以计算出哪个班次使占用单元格的数量最小化。

当然，您需要担心三个方面。你可以一次处理一个，直到细胞数量减少。这是局部最小值，但可能不是全局最小值。寻找其他局部最小值的一种方法是从随机选择的起点重新开始。