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

12 投票

6 回答

4809 浏览

数据工程师

提问于 2025-04-17 02:48

假设你有一大堆杂乱无章的点，这些点用三维坐标表示，数量从几万到几百万不等。你想要找一个好的算法，来生成一个规则的正方形网格（用户可以定义间距），这个网格要能包住所有的点。这里有一些要求：

网格必须是正方形且规则的
我需要能调整网格的间距（也就是每个小方块的边长），最好只用一个变量就能做到
网格要尽量小，也就是说每个网格中的“块”至少要包含一个杂乱的点，而每个杂乱的点也要被一个“块”包住
算法的返回值应该是网格点的坐标列表

为了更好地说明这个问题，假设在二维空间中，有这样一组点：

如果网格间距是X，算法可能返回的结果就是这些红点的坐标（虚线只是为了说明）:

而如果网格间距是X/2，算法可能返回的结果就是这些红点的坐标（虚线只是为了说明）:

对了，我正在处理的这些杂乱点是大蛋白质分子的原子坐标，类似于你从.pdb文件中得到的数据。

如果能用Python来解决这个问题就最好了，不过伪代码也可以。

补充说明：我觉得我最开始描述的需求可能有点模糊，所以我添加了一些限制条件和图片来澄清。

数据结构网格算法三维坐标点集处理正方形网格间距调整大蛋白质分子坐标列表

6 个回答

你觉得 Voronoi图怎么样？它可以用 O(n log n) 的时间复杂度通过福图恩算法来生成。

我不确定这是否能解决你的问题，但Voronoi图在自然界中非常“自然”。它们在自然界中非常常见。

举个例子（来自维基百科）：

enter image description here

回答于 2025-04-17 由 Python大师

分享举报

我建议你做一个 k-d 树。这个方法比较快，简单，而且容易实现：

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

不过，你可能需要稍微修改一下，以适应你的具体要求。

回答于 2025-04-17 由 Python大师

分享举报

因为你想要的是一个用户指定间距的规则方格网，所以这个方法听起来比较简单。

首先，先遍历一下数据，找出每个维度的最小和最大坐标。然后计算一下，用户指定的间距需要多少步才能覆盖最小和最大之间的距离。

再遍历一次数据，把每个点分配到网格中的一个单元格里，网格的起点是每个坐标的最小值，间距就是你指定的那个（比如说，X_cell = Math.floor((x_i - x_min) / spacing)）。可以用字典或者数组来记录每个单元格里有多少个点。

现在，打印出那些至少有一个点的单元格的坐标。

你还有一些灵活性，我没有尝试去优化：除非最小和最大坐标之间的距离正好是网格间距的整数倍，否则会有一些余地让你移动网格，仍然能包含所有的点。现在网格是从最低点的位置开始的，但可能在最高点之前就结束了，所以你可以在每个维度上稍微向下移动一下。这样做的时候，有些点会从一个单元格移动到另一个单元格，已占用的单元格数量也会变化。

如果你一次只考虑一个维度的移动，可以比较高效地计算出会发生什么。先算出每个点到它所在单元格的最大坐标的距离，然后把这些值排序。当你把网格向下移动时，距离最大坐标最近的点会最先换单元格，你可以按排序的顺序一个一个地处理这些点。如果在这个过程中更新单元格里的点的数量，就能找出哪个移动能最小化已占用单元格的数量。

当然，你还有三个维度需要考虑。你可以一个一个地处理，直到减少单元格的数量。这是一个局部最小值，但不一定是全局最小值。寻找其他局部最小值的一种方法是从一个随机选择的起点重新开始。

回答于 2025-04-17 由 Python大师

分享举报

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

6 个回答

撰写回答