I've been searching for an algorithm to group objects based on neighbours. I've looked at kd trees and quadtrees, but I'm sure someone already had my exact case and knows the exact algorithm I should be using.
I have some blocks, and I need to group them in order to have the least amount of blocks.
Suppose that on the left image all the tiles are 1x1 blocks. I'd like to have an algorithm that would group them so I could have the least amount of blocks possible, that can be scaled, and don't have to be squares (they can be rectangles).
Ungrouped boxes
Example of what the algorithm could return
(note that this may not be the perfect solution, because I didn't check all possibilities)
I'll probably end up creating an array with these blocks, where 1 would be a block and 0 would be nothingness. Something like this:
[0, 1, 0, 0, 1, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 1, 1, 0]
[0, 0, 1, 1, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 0, 0, 0]
The blocks always have an integer scale, no floating values. I don't have any height (yet), so we can consider that everything is flat. I also know that I won't have multiple "islands", all the blocks are all connected.
This is done for performance reasons (this will be running on mobile). If this gets too complicated or too heavy for runtime, I'll figure out another way, I just want to know if there is a simple solution to this case.
Thanks!
