5
$\begingroup$

I have been struggling with the following problem.

Given:

  • the coordinates of a bunch of boxes/rectangles (in the form {xmin,ymin,xmax,ymax}) aligned with the x-y axes (not rotated rectangle)
  • the overall image size (assuming it square for simplicity)
  • a tile size (where the tiles are squares)

I'm trying to find the minimal number of tiles (NOT ROTATED) that can be used to cover all the boxes, where the "tiles" are simply some squares that don't need to be on a grid, but can be placed anywhere to cover the boxes.

A simpler approach that I have been using so far is to slice the full image in tiles, and check what tiles overlap with the boxes. This obviously isn't the optimal number of tiles, because (for example) a box could end up being in between two tiles, even though it might be contained in a single tiles.

EDIT: as pointed out by @flinty in the comment, this might be a NP-hard problem, so it doesn't necessarily have to be the optimal solution (minimum number of tiles), but it might as well a better solution respect to my simple approach :)

Here some example data that I have been using to play with:

b0 = {{40,5,50,15}};
b1 = {{5,5,11,11}};
b2 = {{20,20,25,36}};
b3 = {{60,25,83,39}};
b4 = {{10,60,25,75}};
b5 = {{12,77,26,80}};
b6 = {{27,68,35,76}};
b7 = {{62,65,80,80}};
b8 = {{72,70,79,84}};
b9 = {{58,68,66,88}};

imgSize = 100;
tileSize = 10;
imageCoords={{0,0,imgSize,imgSize}};

tilesWithBoxes={{0, 0}, {0, 1}, {0, 3}, {0, 4}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 5}, {2, 6}, {2, 7}, {2, 8}, {3, 1}, {3, 2}, {3, 5}, {3, 6}, {3, 7}, {3, 8}, {5, 0}, {5, 1}, {5, 2}, {6, 0}, {6, 1}, {6, 2}, {6, 3}, {6, 5}, {6, 6}, {6, 7}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, {7, 5}, {7, 6}, {7, 7}, {8, 5}, {8, 6}, {8, 7}};

Graphics[
Join[ ({
     EdgeForm[{Thick}], 
     FaceForm[], 
     Rectangle[{#\[LeftDoubleBracket]1,1〛,#\[LeftDoubleBracket]1,2〛},{#\[LeftDoubleBracket]1,3〛,#\[LeftDoubleBracket]1,4〛}]
   } & /@ {b0,b1,b2,b3,b4,b5,b6,b7,b8,b9}),
   
   ({
     EdgeForm[{Thick,Red}], 
     FaceForm[], 
     Rectangle[{#\[LeftDoubleBracket]1,1〛,#\[LeftDoubleBracket]1,2〛},{#\[LeftDoubleBracket]1,3〛,#\[LeftDoubleBracket]1,4〛}]
   } & /@ {imageCoords}),
   
   ({
     EdgeForm[{Thick,Green,Opacity[0.1]}], 
     FaceForm[], 
     Rectangle[{#\[LeftDoubleBracket]1〛,#\[LeftDoubleBracket]2〛},{#\[LeftDoubleBracket]1〛+tileSize,#\[LeftDoubleBracket]2〛+tileSize}]
   } & /@ Tuples[Range[0,imgSize-tileSize,tileSize],2]),
   
   ({
     EdgeForm[{Thick,Purple,Opacity[0.1]}], 
     FaceForm[{Purple,Opacity[0.3]}], 
     Rectangle[{#\[LeftDoubleBracket]2〛*tileSize,#\[LeftDoubleBracket]1〛*tileSize},{#\[LeftDoubleBracket]2〛*tileSize+tileSize,#\[LeftDoubleBracket]1〛*tileSize+tileSize}]
   } & /@ tilesWithBoxes)
   ]
]

Example of the simpler (sub-optimal) approach, where the image is fully tiled (green lines) and overlap is checked against the boxes (purple tiles): from the image is clear that a more clever choice of tiles can be done to reduce the overall number.

enter image description here

ps. apologies for the ugly code, my Mathematica is a bit rusty nowadays :(

$\endgroup$
2
  • 2
    $\begingroup$ Finding the minimum number looks like an NP-Hard problem to me (like rectangle packing), at least if you want a generic solution, so realistically you will only get an algorithm that gives you a good solution. $\endgroup$
    – flinty
    Commented Nov 29, 2023 at 12:31
  • $\begingroup$ @flinty yeah goo point, good solution would absolutely work as well :) I edited the original post as well $\endgroup$
    – Fraccalo
    Commented Nov 29, 2023 at 13:08

2 Answers 2

5
$\begingroup$

Represent the grid as an array of pixels, 1 if filled, 0 otherwise. Then use MorphologicalComponents to separate out the individual pieces so we can process them individually.

Focusing on just a single piece, my crude algorithm here first starts with one rectangle per pixel. So for example the lower left piece has 13 pixels, so we put them in groups. In this example there are 13 groups each containing a single pixel. We randomly select a group and another group and ask if they can be merged. They can be merged if they form a rectangle i.e the bounding box area is the same as the total number of pixels in the group. When a merge occurs, the two original groups are removed and a new merged group is added.

We continue this way, merging groups until a certain number of innerIterations passes. In an outer loop, we repeat this procedure outerIterations many times and find the solution with the smallest number of groups (rectangles).

For display, there are some caveats around moving from the image coordinate system to rectangles to be aware of, so I've commented those.

Remove["Global`*"];

bboxArea[t_] := (1 - Subtract @@ MinMax[t[[All, 1]]])*
  (1 - Subtract @@ MinMax[t[[All, 2]]])

grow[candidate_, t_] :=
 With[{combined = Join[candidate, t]},
  Return@If[
    bboxArea[combined] - Length[combined] == 0,
    combined, {}
    ]
  ]

innerOptimization[img_, iterations_] := Module[{
    tiles = RandomSample[List /@ Position[img, 1]], candidate, g},
   Do[
    candidate = RandomChoice[tiles];
    Do[
     g = grow[candidate, t];
     If[g != {},
      tiles = DeleteCases[tiles, t | candidate];
      AppendTo[tiles, g];
      Break[];
      ];
     , {t, DeleteCases[tiles, candidate]}
     ];
    , {iterations}];
   Return[tiles];
   ];

outerOptimization[img_, innerIterations_, outerIterations_] := Module[{
   bestTiles = List /@ Position[img, 1], result},
  Do[
   result = innerOptimization[img, innerIterations];
   If[Length[result] <= Length[bestTiles], bestTiles = result];
   , {outerIterations}];
  Return[bestTiles]
  ]

(* Note: we add {-1,0} here to both coordinates due to rect needing to fill at least 1 square *)
posToBBs[tiles_] := 
 Table[Rectangle @@ 
   Transpose@{MinMax[t[[All, 2]]] - {1, 0}, 
     MinMax[t[[All, 1]]] - {1, 0}}, {t, tiles}]

img = {
   {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 1, 1, 1, 0, 0},
   {1, 1, 1, 1, 0, 1, 1, 1, 0, 0},
   {1, 1, 1, 1, 0, 1, 1, 1, 0, 0},
   {1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
   {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
   {0, 1, 1, 0, 0, 1, 1, 1, 1, 0},
   {0, 1, 1, 0, 0, 1, 1, 1, 1, 0},
   {1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
   {1, 1, 0, 1, 1, 0, 0, 0, 0, 0}
   };

SeedRandom[123];

(* Note: we reverse the image here due to graphics and image having different coordinate systems *)
mpc = MorphologicalComponents[Reverse@img, CornerNeighbors -> False];
selc[m_, c_] := Map[Boole[# == c] &, m, {2}]

rectMap = AssociationMap[
   posToBBs@outerOptimization[selc[mpc, #], 100, 10] &
   , Range[Max[mpc]]];

Show[{Colorize[Reverse@mpc],
  Graphics[{EdgeForm[{Black, Thick}], FaceForm[None], 
    Riffle[EdgeForm /@ RandomColor[Max[mpc]], Values[rectMap]]}]
  }]

rectangles

For some larger shapes, this doesn't perform that well though even after a very high number of iterations. For example a img = DiskMatrix[6], because it gets stuck with a lot of rectangles it cannot combine and there is no way to split them. A better approach for this kind of shape would be to grow a rectangle out greedily, and spawn new rectangles when the current one cannot be extended further.

enter image description here


Update:

Here's a greedy method that grows rectangles by adding the pixels along the side that adds the greatest number of new pixels. It performs much better on the disk example:

growSide[tile_, side_] :=
 With[{
   mmRow = MinMax[tile[[All, 1]]], mmCol = MinMax[tile[[All, 2]]]},
  (* Grows a tile along the specified side *)
  Switch[side,
   "N", {mmRow[[1]] - 1, #} & /@ (Range @@ mmCol),
   "S", {mmRow[[2]] + 1, #} & /@ (Range @@ mmCol),
   "E", {#, mmCol[[2]] + 1} & /@ (Range @@ mmRow),
   "W", {#, mmCol[[1]] - 1} & /@ (Range @@ mmRow)
   ]
  ]
grow[pixelPositions_, tile_] := Module[{newPixels, curTile = tile},
  Until[newPixels == {},
   (* Try to grow the tile, 
   finding the side that gives us the most new pixels, 
   until we cannot *)
   newPixels = growSide[curTile, #] & /@ {"N", "E", "S", "W"};
   newPixels = 
    If[ContainsAll[pixelPositions, #], #, {}] & /@ newPixels;
   newPixels = First[MaximalBy[newPixels, Length]];
   If[newPixels != {}, curTile = Union[curTile, newPixels]];
   ];
  Return[curTile];
  ]

(*Note:we add {-1,0} here to both coordinates due to rect needing to fill at least 1 square*)
posToBBs[tiles_] := 
 Table[Rectangle @@ 
   Transpose@{MinMax[t[[All, 2]]] - {1, 0}, 
     MinMax[t[[All, 1]]] - {1, 0}}, {t, tiles}]

(* start off with 1 pixel per tile *)
computeRects[img_] := 
 Module[{t, pos = RandomSample@Position[img, 1]},
  posToBBs[Reap[While[pos != {},
      t = grow[pos, {RandomChoice[pos]}];
      Sow[t];
      pos = Complement[pos, t];
      ]][[2, 1]]]
  ]


img = DiskMatrix[{9, 9}, 20];

(*Note:we reverse the image here due to graphics and image having different coordinate systems*)
mpc = MorphologicalComponents[Reverse@img, CornerNeighbors -> False];
selc[m_, c_] := Map[Boole[# == c] &, m, {2}]

rectMap = 
  AssociationMap[computeRects[selc[mpc, #]] &, Range[Max[mpc]]];

Show[{Colorize[Reverse@mpc], 
  Graphics[{EdgeForm[{Black, Thick}], FaceForm[None], 
    Riffle[EdgeForm /@ RandomColor[Max[mpc]], Values[rectMap]]}]}]

enter image description here

Here's a test case with more interesting shapes:

SeedRandom[1];
img = Dilation[Rasterize[Graphics[
        GeometricTransformation[RandomPolygon[8], 
           TranslationTransform[#]] & /@ 
         RandomVariate[NormalDistribution[0, .75], {8, 2}]
        ], RasterSize -> {128, 128}] // ColorNegate // Binarize, 1] //
    ImageData;

enter image description here

$\endgroup$
1
$\begingroup$

Maybe I'm not understanding the question but it seems that you can determine the tiles that cover each individual rectangle and then get a unique list of the tiles that would then cover all rectangles.

tileSize = 10;
nx = 10; (* Grid size *)
ny = 10;
rectangles = {b0, b1, b2, b3, b4, b5, b6, b7, b8, b9};

(* Gives the list of tile indices that covers a individual rectangle *)
indices[tileSize_, rectangle_] := Module[{x0, x1, y0, y1},
  x0 = Floor[rectangle[[1, 1]]/tileSize];
  x1 = Ceiling[rectangle[[1, 3]]/tileSize] - 1;
  y0 = Floor[rectangle[[1, 2]]/tileSize];
  y1 = Ceiling[rectangle[[1, 4]]/tileSize] - 1;
  Flatten[Table[{i, j}, {i, x0, x1}, {j, y0, y1}], 1]
  ]

(* Get the unique list of covering tiles *)
c = Flatten[indices[tileSize, #] & /@ rectangles, 1] // DeleteDuplicates;

(* Minimum number of covering tiles *)
Length[c]
(* 29 *)

(* Generate graphics *)
(* Grid *)
grid = Graphics[({EdgeForm[{Thick, Green, Opacity[0.1]}], FaceForm[],
  Rectangle[{#[[1]], #[[2]]}, {#[[1]] + tileSize, #[[2]] + tileSize}]} &
  /@ Tuples[Range[0, imgSize - tileSize, tileSize], 2])];

(* Red border *)
border = Graphics[({EdgeForm[{Thick, Red}], FaceForm[], 
  Rectangle[{#[[1, 1]], #[[1, 2]]}, {#[[1, 3]], #[[1, 4]]}]} & /@ {imageCoords})];

(* Individual rectangles *)
rect = Graphics[({EdgeForm[{Thick}], FaceForm[], 
  Rectangle[{#[[1, 1]], #[[1, 2]]}, {#[[1, 3]], #[[1, 4]]}]} & /@  rectangles)];

(* Covering tiles *)
tiles = Graphics[Table[{FaceForm[{Purple, Opacity[0.3]}], 
     Rectangle[tileSize c[[i]], tileSize (c[[i]] + 1)]}, {i, Length[c]}]];

(* Show results *)
Show[grid, border, tiles, rect, PlotRangeClipping -> False]

Covered rectangles

$\endgroup$
6
  • $\begingroup$ thanks for your answer, probably I haven't been clear enough in my question, apologies for that. I think that your answer is in line with my "simpler approach" described in my original post: just tile the full image and check which tiles have at least a portion of a box in them. This is not the "optimal" solution though, where with optimal I mean the least number of tiles to cover all the boxes. In you image, for example, the bottom left box belongs to 4 different tiles, however the optimal solution would be a single tile, because that box is small enough to be contained by a single tile $\endgroup$
    – Fraccalo
    Commented Dec 1, 2023 at 9:43
  • $\begingroup$ hope my comment clarified a bit what I mean, if not feel free to ask for more details and I'll do my best to fill in any gap :) $\endgroup$
    – Fraccalo
    Commented Dec 1, 2023 at 9:43
  • $\begingroup$ I suspected that I must have not answered what is in your head given @flinty 's answer (which I still can't see how that answer is related to your 3 bullet points - but that's because I'm slow). So the fixed-sized squares (with a single size?) are NOT on a grid and can be placed anywhere? Can they be rotated? Same for the rectangles? So, yes, I think you need to give a more restricted description of what you're trying to solve. $\endgroup$
    – JimB
    Commented Dec 1, 2023 at 16:22
  • $\begingroup$ And should I assume that the tiles can't overlap? $\endgroup$
    – JimB
    Commented Dec 1, 2023 at 17:31
  • $\begingroup$ I'll try to improve the description soon, in the meantime to answer your question: I don't think that an overlapping of the tiles really makes a difference in the minimum number of tiles needed. This is because, if for example a box is large 1.5x the tile size, then you need minimum 2 tiles to cover its width, and you can either overlap them to cover exactly the box width without any excess, or you could put the tiles side by side and you would capture some "background" other than the box, but it's still 2 tiles. $\endgroup$
    – Fraccalo
    Commented Dec 2, 2023 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.