[Python] How to dynamically partition a 2D array into boxes based on inverse area density?

Context: I have a 2D array (size N x M), let's call it U, where each cell contains a non-negative value K ≥ 0 representing a "density" at that point. I want to algorithmically divide the array into rectangular "boxes" such that dense areas get smaller boxes and sparse areas get larger boxes, balancing total representation. Let's call the N x M array of scalar values of these boxes W.

Example 1:

U =

1 , 1 , 1
1 , 8 , 1
1 , 1 , 1


Here, density is fairly uniform, so the optimal output is 9 individual 1×1 boxes, so we get

W =

1 , 1 , 1
1 , 1 , 1
1 , 1 , 1


Example 2:

U =

1 , 1 , 1
1 , 72, 1
1 , 1 , 1


Here, the center has high density. The center should get a small box, but the rest could be grouped into larger areas, so we get

W =

9 , 9 , 9
9 , 1 , 9
9 , 9 , 9


Example 3:

U =

1 , 1 , 1 , 1 , 1
1 , 72, 72, 72 ,1
1 , 72, 72, 72 ,1
1 , 72, 72, 72 ,1
1 , 1 , 1 , 1 , 1


In this case, the 3x3 center block has high density, while the surrounding ring has low density. The goal is to dynamically identify and box that 3×3 region separately, assigning a proportionally smaller weight (or higher resolution) to it.

My goal: Automatically find the optimal box size (and region) for denser clusters.

Balance each box's size inversely with the average density inside it.

Minimize oversegmentation and avoid box overlaps.

What I’ve tried: A basic sliding window to compute local averages.

Subtracting each cell's density from the global mean as a naïve “weight.”

But I’m stuck on how to dynamically grow or shrink box sizes and how to identify the boundaries where density shifts enough to warrant a new box.

Desired outcome: An algorithm or method that returns a set of non-overlapping rectangular boxes (with positions and sizes), where the sum of the densities in each box is roughly equal—or at least where denser regions are covered by finer boxes and sparser regions by coarser ones.

Edit 1

Question: Also, it's not clear to me why the dimensionality of the "boxes" array is the same as the original array

Answer: It's because every cell in the original array U will have a corresponding number of "boxes" assigned to it. Maybe it's easier if I give the output in the form of a picture:



Edit 2

Question: How many boxes should be in the output? Are you attempting to minimize the number of boxes, minimize weight error, or both? If both, how do you balance those?

I'm try to normalize things so contiguous areas with high densities get less weight than other areas with low density.

Continue reading...