# Filling the space with rectangles

Following up on my previous question, I now seek to fill a matrix $$m \times n$$ with rectangles. Henrik Schumaker had provided some code in his answer to the previous question:

m = 100;
n = 100;
m1 = RandomReal[{0, 1}, {m, n}];
alpha = Pi/4.; (*The angle of the rectangle to the horizontal (vertical).*)
(*direction of first side of the rectangle*)
e1 = {Cos[alpha], Sin[alpha]};
(*e1=RandomPoint[Circle[]]*)
(*direction of the second side of the rectangle*)
e2 = RotationTransform[Pi/2][e1];
(*half the length of the first side of the rectangle*)
halflength1 = 5;(*RandomReal[{1,m/2}];*)
(*half the length of the second side of the rectangle*)
halflength2 = 15;(*RandomReal[{1,n/2}];*)

ogr1 = Ceiling[(halflength1)*Cos[alpha] + (halflength2)*Sin[alpha]];(*constraints on rectangular centers to be full in the matrix.*)
ogr2 = Ceiling[(halflength2)*Cos[alpha] + (halflength1)*Sin[alpha]];


X = (2*halflength1)/Sin[alpha];
center = Table[{ogr1, ogr1 + i*X}, {i, 0, 5}] (*Center positions of horizontally non-overlapping rectangles*)



ccc = Table[
pts = Tuples[{Range[m], Range[n]}];
(*The following vector has a 1 at positions that belong to the \
rectangle;other entries are 0.*)
picker =
Times[UnitStep[halflength1 - Abs[pts.e1 - center[[i]].e1]],
UnitStep[halflength2 - Abs[pts.e2 - center[[i]].e2]]];
(*Pick the coordinates of the points belonging to the rectangle.*)
pattern = Pick[pts, picker, 1];
(*Find axis-aligned bounding box (the orange rectangle)*)
{xspan, yspan} = Span @@@ (MinMax /@ Transpose[pattern]);

(*Use SparseArray to construct the actual matrix.*)
result =
SparseArray[pattern -> Extract[m1, pattern], {m, n}][[xspan,
yspan]];

r1 = Select[Flatten[result], # > 0 &];
r2 = Flatten[Table[Position[m1, r1[[i]]], {i, 1, Length[r1]}], 1];

Rotate[ListPlot[{r2}, PlotRange -> {{0, 101}, {0, 101}},
AspectRatio -> 1, Frame -> True, FrameTicks -> None,
PlotStyle -> {RandomColor[], PointSize -> 0.001},
PlotMarkers -> {\[FilledVerySmallSquare], Tiny}], -Pi/2]
, {i, Length[center]}]
Table[ccc[[i, 1]], {i, 1, Length[ccc]}];
Rotate[Show[%], -Pi/2]



We obtain such a series of rectangles:

The question is. How to define the 'center' set to obtain such a series of rectangles as in this graph? (I made it by hand :)):

So how to fill the matrix with full non-overlapping rectangles with given side lengths and inclination angle alpha.

• It's an interesting problem. Can't you just start packing the $l$ by $w$ rectangles beginning with the first one oriented at the correct angle as close to the upper left corner first. Then compute the running distance $d$ of the next row and pack $\mod(d,l)$ more rectangle, then next $d$ and more mods? I would first start with just the first rectangle placed correctly and then write the mod routine to get just the next row to even see if this is a plausible method.
– josh
Commented May 24, 2022 at 17:22
• <<<Can't you just start packing the l by w rectangles beginning with the first one oriented at the correct angle as close to the upper left corner first. >>>> The first rectangle in the upper left corner is packed as close as possible - if it is higher or more to the left then it will not all fit in the matrix. ...but thanks! Commented May 24, 2022 at 17:41
• Yes, the first one can only go in one place determined by $l,w,\alpha$. Just draw the matrix and programatically place it where it belongs. Can then determine the line between the first and second row. Extend that line to the boundaries and compute it's length $l_2$. Then can do a $\mod(l_2,l)$ to get the number of rectangles for second row. Pack thoes. I would first work on just the first two rows first perhaps in Manipulate environement where you can adjust $l,w,\alpha$ to confirm its working then proceed further. Not suggesting it's easy, just a possible method.
– josh
Commented May 24, 2022 at 17:56
• Please post the complete code. The code can not run. Commented May 25, 2022 at 1:14
• Now code is ok. :) Commented May 25, 2022 at 8:09

This was an interesting problem! I approached this as a lattice and first set out to find the translations that would generate the lattice from the rectangular repeating unit. Below I am using $$15\times5$$ rectangles, rotated by $$30^{\circ}$$, just to have a practical representation (the code that generated this diagram is attached at the end).

I started with a horizontally oriented rectangle with $$long\times short$$ dimensions ($$l\times s$$), whose bottom-left vertex was the origin. I rotated that (RotationTransform) by an angle $$\alpha$$ and then translated the result to the right by $$s \sin\alpha$$ as indicated by trigonometric considerations on the triangle A whose top angle is $$\alpha$$ as well. This generated the gray rectangle in the picture above.

The green rectangle is the next repeating unit, placed according to the problem's requirements. There are infinite pairs of translation operations that will generate this lattice.

• I chose the first one to be horizontal ($$p_3\rightarrow p_7=t_h$$) out of convenience; the shortest second one from $$p_3$$ is then $$p_3\rightarrow p_8 = t_v$$ in the diagram above.
• $$t_h$$ can be calculated directly from inspection of triangle B, so $$t_h = (s\csc \alpha,0)$$.
• The components of $$t_v$$ can be calculated as $$p_8-p_3=(-l \cos \alpha + s \csc \alpha, -l \sin \alpha)$$
unit =
TranslationTransform[{short Sin[alpha], 0}]@
RotationTransform[alpha]@
Rectangle[{0, 0}, {long, short}];

{p1, p2, p4, p3} = PolygonCoordinates[unit];

(* Translate this unit horizontally to give a repeat unit *)
translated = TranslationTransform[{short/Sin[alpha], 0}]@ unit;
{p5, p6, p8, p7} = PolygonCoordinates[translated];

(* Obtain symbolic expressions for the simplest translations *)
th = p7 - p3
tv = p8 - p3

(* Out:
{short Csc[alpha], 0}
{-long Cos[alpha] + short Csc[alpha], -long Sin[alpha]}
*)


With that in hand, I did the following:

• Defined a rectangular container region with arbitrary size, and chose an arbitrarily-sized repeating unit, and a random angle ($$35^{\circ}$$) below.
• Moved the repeating unit to the top of that region.
• Applied the lattice translations found above repeatedly in each direction, to cover the region. Rather than doing a lot of tedious modular math, I generated the minimum extra rows of rectangles in the "horizontal" direction that would cover the whole region, then removed the extra repeats that fell outside of the region.
• Styled the results with random colors, and plot!
regionWidth = 140; regionHeight = 60;
region = Rectangle[{0, 0}, {regionWidth, regionHeight}];

short = 5; long = 15; alpha = 35 Degree;

{unitWidth, unitHeight} = CoordinateBounds[unit][[All, 2]];

topUnit = TranslationTransform[{0, regionHeight - unitHeight}][unit];

ClearAll[selector]
selector[poly_] := Module[{cbP = CoordinateBoundingBox[poly]},
And @@ Flatten@{Thread[cbP[[1]] >= {0, 0}], Thread[cbP[[2]] <= {regionWidth, regionHeight}]}
]

candidates = Flatten@
Table[
TranslationTransform[h th + v tv][topUnit],
{h, Floor[regionHeight/tv[[2]]], regionWidth/th[[1]]},
{v, 0, -regionHeight/tv[[2]]}
];

within = Select[candidates, selector];

Graphics[{
EdgeForm[Black],
{Opacity[0.2, Blue], region},
Transpose@{RandomColor[Length[#]], #} &[within]
},
AxesOrigin -> {0, 0}, Axes -> True, ImageSize -> Large,
AspectRatio -> Automatic
]


Below are some initial definitions in symbolic form, and the code that generated the diagram at the top of this answer:

(*======================
CODE FOR THE DIAGRAM
========================*)
(* Introduce explicit values, for the plot *)
short = 5; long = 15; alpha = 30 Degree;
Graphics[{
EdgeForm[Black], PointSize[0.02],
GrayLevel[0.8], unit,
Darker@Green, translated,
Black, Point@p3, Blue, Point@p7, Red, Point@p8,
Black, Arrow[{p3, p8}], Black, Arrow[{p3, p7}],

Inset[Style[Subscript["p", #1], 18, Bold], #2] &,
{
{1, 2, 3, 4, 5, 6, 7, 8},
{p1 + {0.2, 0.9}, p2 + {-0.8, 0.3}, p3 + {0.2, 0.9}, p4 + {0.9, -0.1},
p5 + {0.2, 0.9}, p6 + {-0.8, 0.3}, p7 + {0.2, 0.9}, p8 + {0.9, -0.1}}
}],

Inset[Style["A", 18, Bold], {0.9, 1.7}],
Inset[Style["B", 18, Bold], {17.5, 10.2}],

Inset[Style["\!$$\*SubscriptBox[\(t$$, $$h$$]\)", 20], {18, 12.5}],
Inset[Style["\!$$\*SubscriptBox[\(t$$, $$v$$]\)", 20], {11, 9}],

Inset[Style["\[Angle]\[Alpha] = " <> ToString[alpha[[1]]] <> "\[Degree]", FontSize -> Scaled[0.05]], {4, 0.7}, Scaled[{0, 1/2}]],
Inset[Style["\[Alpha]", FontSize -> Scaled[0.04]], {21.3, 11.4}, Scaled[{1, 1/2}]],
Inset[Style["\[Alpha]", FontSize -> Scaled[0.03]], {0.6, 3.1}, Scaled[{1, 1/2}]]
},
AxesOrigin -> {0, 0}, Axes -> True, ImageSize -> Large,
AspectRatio -> Automatic
]

• Thanks @MarcoB. Good job! But I need the centers ('center' set in my code) of the rectangles packed in a m x n matrix. How do I extract them? Commented Jun 2, 2022 at 4:57
• @ralph You can use RegionCentroid /@ within, with the definition of within from the code above, i.e. the list of rectangles within the region. Commented Jun 2, 2022 at 14:47
• It seems that e.g. for such parameters the code does not determine all rectangles: (Bottom right corner) regionWidth = 100; regionHeight = 100; short = 5; long = 15; alpha = 35 Degree; Am I right? Commented Jun 2, 2022 at 18:17
• @ralph that may well be for some values of alpha, in which case you would want to expand the range of h in the table that generates candidates. I've done my best to automate the boundaries, but it's rather complicated to cover any possible angle. Hand adjustment will work though. Commented Jun 5, 2022 at 2:14
• @ralph If you think my answer was useful and it properly addressed your problem, I would be grateful if you would consider formally accepting it by checking the gray check mark to its side. Commented Jun 13, 2022 at 1:34