CODEWITHSUNDEEP
python3dinteger-arithmetic
Cirrocumulus
Cirrocumulus

Reputation: 630

Quickly finding 3D bounds of point cloud

I have a class called Point which holds x, y and z values for each point. It also has other attributes, e.g. a "category" string.

Another class called Map keeps a reference to all of the Point object, in a list. I currently have around 150 of those Point objects.

The Map class keeps track of the 3D extents of all its Point objects by using a simple Extents dataclass:

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

In my GUI (I'm using Qt via PySide6), a control switches between coloring all the Point by category, which is very fast (0.002 seconds) and coloring them by z value, which is slow enough to be noticeable when clicking the control (0.2 seconds).

It's slow because for each Point object drawn, the code checks the minimum and maximum extents of the Map in order to scale the color output to the current z range of all the Points.

@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)
        )

I thought of caching the Extents in an instance variable (inside the Map) and modifying it only when the scene changes, but it's even worse because whenever there's a modification in the GUI there's a noticeable lag while the app calculates the min and max values.

I could add a property which only checks the z values. This should cut the time by 60 percent but I wonder if there's a better way. It seems like such a simple problem which has surely been dealt with a thousand times before.

EDIT:

I'm still wondering what's the most efficient way of doing this, though. I might need a lot more than 150 objects at some point.

Upvotes: 0

Views: 1187

Answers (1)

BTables
BTables

Reputation: 4833

One of the first issues is that in the above code you're actually recreating and iterating over a list 6 times instead of doing it in a single pass like this:

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

There are a few other better approaches to solving this problem. For example, if you just want to always know the min/max of ever axis you can just keep a sorted list; or construct a 1d KD-Tree for each of the 3 axes.

All of that being said, doing a min/max search over a group of 3d points should never run in anything more than linear time.

Upvotes: 1

Related Questions