python - 将网格放置在一组无序点上的算法

Question

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

1. 网格要方正正正
2. 我需要能够调整网格间距(其中一个正方形的边长)，最好使用单个变量
3. 我想要一个最小尺寸的网格，即网格中的每个“ block ”都应该至少包含一个无序点，并且每个无序点都应该包含在一个“ block ”中
4. 算法的返回值应该是网格点的坐标列表

给定这组点，以二维方式进行说明:

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

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

对于任何感兴趣的人，我正在处理的无序点是大蛋白质分子的原子坐标，就像您可以从 .pdb 文件中得到的一样。

Python 是解决方案的首选，尽管伪代码也不错。

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

Answer 1

我建议你做一个 k-d tree .它快速、简单且易于实现:

和维基百科代码:

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

不过，您必须稍微修改它以适应您的限制。