快速找到点云的 3D 边界

Question

我有一个名为 Point 的 class，它保存每个点的 x、y 和 z 值。它还具有其他属性，例如“类别”字符串。

另一个名为 Map 的 class 在列表中保留对所有 Point 对象的引用。我目前有大约 150 个这样的 Point 对象。

地图 class 通过使用简单的范围数据class:

跟踪其所有点对象的 3D 范围

@dataclass
class Extents:
    min_x: int
    max_x: int
    min_y: int
    max_y: int
    min_z: int
    max_z: int

在我的 GUI 中（我通过 PySide6 使用 Qt），一个控件在按类别为所有点着色之间切换，这是非常快的（0.002 秒）和按 z 值着色，这足够慢单击控件时会很明显（0.2 秒）。

速度很慢，因为对于绘制的每个点对象，代码都会检查地图的最小和最大范围，以便将颜色输出缩放到所有点的当前 z 范围。

@property
def extents(self) -> Extents:
    if self.size == 0:
        return Extents(0, 0, 0, 0, 0, 0)
    else:
        return Extents(
            min(point.x for point in self.points),
            max(point.x for point in self.points),
            min(point.y for point in self.points),
            max(point.y for point in self.points),
            min(point.z for point in self.points),
            max(point.z for point in self.points)
        )

我考虑过将 Extents 缓存在一个实例变量中（在 Map 中）并仅在场景发生变化时修改它，但情况更糟，因为每当 GUI 中发生修改时，应用程序计算最小值和最大值。

我可以添加一个只检查 z 值的属性。这应该会减少 60% 的时间，但我想知道是否有更好的方法。看起来这么简单的问题肯定已经处理过上千次了。

编辑：

在遍历整个点列表之前缓存 min/max 值可将执行时间缩短至 0.1 秒。更好，但在 GUI 中仍然很明显。
添加一个只有 returns z 值的特殊属性将其降低到 0.014，这要好得多。

不过，我仍然想知道最有效的方法是什么。有时我可能需要 150 多个对象。

Answer 1

第一个问题是，在上面的代码中，您实际上是在重新创建和遍历列表 6 次，而不是像这样一次性完成：

min_x,min_y,min_z,max_x,max_y,max_z=0,0,0,points[0].x, points[0].y,points[0].z
for point in points:
    max_x = point.x if point.x > max_x else max_x
    max_y = point.y if point.y > max_y else max_y
    max_z = point.z if point.z > max_z else max_z
    min_x = point.x if point.x < min_x else min_x
    min_y = point.y if point.y < min_y else min_y
    min_z = point.z if point.z < min_z else min_z

还有一些其他更好的方法可以解决这个问题。例如，如果你只想知道每个轴的 min/max 你可以只保留一个排序列表；或为 3 个轴中的每一个构建一维 KD 树。

综上所述，对一组 3d 点进行 min/max 搜索绝不会运行超过线性时间。

快速找到点云的 3D 边界

Quickly finding 3D bounds of point cloud

python

3d

integer-arithmetic