0

I have a 3D numpy array with 1's and 0's where the 1's represent a shape. I want to write a program in python that determines the largest cube that can be inscribed in the shape. I have seen this (Create largest volume inscribed 3D box that will fit within array of points) answer but it essentially recommends brute force, so I was wondering if there was any algorithm for this that is potentially faster?

Also, I need this algorithm so that I can determine the lowest resolution at which this shape can be made out. So, if there is not faster method to find the largest inscribed box, is there potentially another angle I could approach this resolution problem that is faster?

Thomas
  • 43
  • 1
  • 7
  • 1
    Can the cube be rotated in any direction? Is there only one shape of 1 values or multiple ones? Is this shape convex or concave? How big is the dataset? Please edit the question with the additional informations. – Jérôme Richard Aug 21 '21 at 22:24
  • 1
    I presume the box is a rectangular parallelepiped, right? Is it axis-aligned? – Mark Lavin Aug 21 '21 at 22:24
  • 1
    @JérômeRichard The box cannot be rotated and is axis aligned. – Thomas Aug 21 '21 at 22:43
  • @MarkLavin The box is a cube, as in all 90 degree angles and the same length for all 3 dimensions. – Thomas Aug 21 '21 at 22:43
  • 1
    The fact that it's an axis-aligned cube allows for taking the following approach: Perform a 3D morphological erosion using structuring elements from 3x3 => a lot x a lot. The largest radius at which the result of the erosion is non-empty will then indicate the radius (half-diameter) of the largest inscribed cube, which can be placed at any non-zero voxel in the erosion result. For more information, google "3d mathematical morphology". – Mark Lavin Aug 21 '21 at 23:59
  • 1
    You could try to use the optimizer of scipy to find a pretty good solution to the problem but probably not the optimal one. It should not be too slow because there is only 4 parameters. It may be interesting use mipmapping to find an approximate initial result and then improve it iteratively (in order to make the overall algorithm faster). Note that this should also works to improve the speed of the method proposed by @MarkLavin. – Jérôme Richard Aug 22 '21 at 00:23
  • @MarkLavin To clarify, are you suggesting increasing the size of the structuring element until you get the largest structuring element that returns a non empty output? – Thomas Aug 22 '21 at 01:08
  • 1
    Because you're looking for a cube (equal side lengths), this can be solved optimally in time linear in the matrix size using dynamic programming: For each x, y, z in increasing order, if input[x,y,z] is 1, set dp[x,y,z] to 1+min(dp[x-1,y,z], dp[x,y-1,z], dp[x,y,z-1]), otherwise set it to 0. Afterwards, dp[x,y,z] will be the side length of the largest cube with bottom-right-front corner at (x, y, z), so the largest value in dp[] will correspond to the largest cube. – j_random_hacker Aug 22 '21 at 07:04
  • Do you have any additional assumptions about the shape? In particular, is it convex? – Stef Aug 22 '21 at 10:32
  • @Thomas, sorry this was unclear (including to me). You want to do a succession of 3x3 erosions which should have the same effect as a 3x3, then starting from original a 5x5, etc. One potential benefit of this approach is that it should be more efficient to do in Tensorflow with GPUs. – Mark Lavin Aug 22 '21 at 15:30
  • @MarkLavin why not decreasing the size of the structuring element until you get the first structuring element that returns a non empty output ? I am trying to figure out the proble but keep asking which should be the starting point of the first cube – pippo1980 Aug 22 '21 at 18:20
  • Yes, I think that'll work, but since you'll be doing erosions with larger structuring elements, I think it'll take longer. Just to clarify, what I was suggesting is something like "x=input image, r = 0; while ( sum( x ) > 0; x = x.erode(3x3),r+=1". – Mark Lavin Aug 22 '21 at 18:35
  • @MarkLavin sorry, somertimes I can be as hard as a brick. Wont the starting point of first 3X3 have influence on the largest cube obtained ? – pippo1980 Aug 22 '21 at 18:38
  • 1
    You start with the original point cloud and do a 3x3 erosion, which operates on all points at the same time; there is no "starting point" per se. – Mark Lavin Aug 22 '21 at 18:40
  • @Stef Unfortunately no – Thomas Aug 23 '21 at 22:24

0 Answers0