How to find the largest cuboid inside a set of points in 3D?

Hi, there,

I have two sets of points, show in the pictures. I want to find the the largest rectangular prism and cube inside point cloud, and the rectangular prism do not need to be aligned with the frame axis, . Is there any hints for this question? I searched in matlab answers, but found nothing. I only find Maximum Inscribed Circle Problem related to this.

Thanks

Kasen

Answer 1

[John D'Errico]

Can a corner of the cube stick out between some of those points? If that is acceptable, you NEED to say so, because it would completely change the necessary solution. I assume when you say couboid that you mean a rectangular prism, where the side lengths need not be all the same. Must this object be aligned with the axes? Again, you NEED to say, else the problem changes completely, and how you would solve it.

If a corner cannot exceed the convex hull of your point cloud, then I would start by computing the convex hull. Now you will need to work with that. I would probably suggest a genetic algorithm to perform the search, where the two corners will lie on the convex hull. You can define a cube in several ways. If the cube/cuboid must be aligned with the axes, then you need only specify the coordinates of two opposite corners of the cube to completely define it. If it is a true cube you are searching for, then you can reduce the degrees of freedom yet again.

Anyway, my suggestion here is you should use a genetic algorithm, bounded by the convex hull.

If the corners of the cube can stick out between points in the cloud, then the problem becomes significantly more difficult, since then any search will get stuck far more easily.

As I said though, there is simply too much unsaid to know much more.

[J.H]

Thanks for the reply.

Sorry for the unclear discription. I need to find the largest rectangular prism with all corner inside the point cloud and the rectangular prism do not need to be aligned with the frame axis,

Would you please provide more detailed hints? Such as how to find convex hull, what should be searched via genetic algorithm. Is there any matlab functions I can use? I have no idea on splitting this problem.

Thanks

Kasen