2
$\begingroup$

Motivation: We want to cover a rectangle using smaller, non-overlapping shapes with the same area: the difference between the total area of the shapes and the area of the rectangle should be zero or positive and close to zero as possible.

We want to control the area of the smaller shapes which we will call epsilon. (Note shapes can be anything; i.e., rectangles, polygons, or closed curves as long as the difference total area of the shapes and rectangle is zero or is positive and close as possible to zero and the shapes are non-overlapping).

Edit: The difference in the shapes and rectangles does not have to be zero. For example, if epsilon=.6 and the rectangle we wish to cover is set $A=[-2,2]^2$, we want a minimum of $\lceil 2^2/.6 \rceil=7$ small rectangles covering $A$, where $7\times .6-4=.2$ instead of zero.

Also, note in this answer the shapes are overlapping, despite having the same area.

Attempt:

Using this answer, suppose we have the following code:

clusters = 
  FindClusters[RandomPoint[Rectangle[{-2, -2}, {2, 2}], 35000], 20, 
   Method -> "KMeans"];

Show[{mesh = VoronoiMesh[Mean /@ clusters, {{-2, 2}, {-2, 2}}], 
  Graphics[{{RandomColor[], Point[#]} & /@ clusters}]}]

enter image description here

Note the area of the polygons are not the same:

area = AnnotationValue[{mesh, 2}, MeshCellMeasure]

{0.706412, 0.620505, 0.712833, 0.698375, 0.765174, 0.856666,
0.894983, 0.786204, 0.742506, 0.81401, 0.826056, 0.90378, 0.788876,
0.940046, 0.776065, 0.936281, 0.793973, 0.808283, 0.83067, 0.798302}

Moreover, the shapes overlap:

factor = Sqrt[Max[area]/area];
cover = MapThread[
   CanonicalizeRegion[Scale[#1, #2, #3 ]] &, {MeshPrimitives[mesh, 
     2], factor, AnnotationValue[{mesh, 2}, MeshCellCentroid]}];

Area /@ cover

{0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719,
0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719,
0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719, 0.899719}

Graphics[{Riffle[RandomColor[Length[cover]], cover] }]

enter image description here

Question: How do we control the area of the shapes to be, e.g. epsilon=.6? Note if the area of the rectangle in the code is $2^2=4$, the minimum number of small shapes which should be used is $\lceil 4/.6 \rceil=7$

$\endgroup$
4
  • 1
    $\begingroup$ "Note shapes can be anything" - If they can be anything, then why don't you divide the rectangle into smaller rectangles of equal area? It is always possible to divide rectangle into any number of smaller rectangles of equal area and moreover with exact solution and without overlapping such that difference between areas would be exactly zero. $\endgroup$ Aug 28, 2023 at 20:33
  • $\begingroup$ @azerbajdzan How can the rectangles have the same area and any area so "overcovering" is possible. $\endgroup$
    – Arbuja
    Aug 28, 2023 at 20:36
  • $\begingroup$ @azerbajdzan I added an edit to the top of the post. $\endgroup$
    – Arbuja
    Aug 28, 2023 at 20:44
  • 1
    $\begingroup$ For your example 7*0.6-4=0.2 cover rectangle B of area 7*0.6=4.2 into 7 rectangles of area 0.6, which can be done exactly. Then place this rectangle B over your original rectangle A of area 4 - and you have covering of your original rectangle with smallest possible overcovering. $\endgroup$ Aug 28, 2023 at 20:52

1 Answer 1

3
$\begingroup$

You can have 4 different solutions if the rectangle is divided into 6 smaller rectangle because 6=1*6=2*3=3*2=6*1, in case into 7 only two 7=1*7=7*1.

r = {{0, -1}, {1, 3}};
r = {{-1, -1}, {1, 1}};
eps = 7/10;
a = Area[Rectangle @@ r];
n = Ceiling[a/eps];
dn = Divisors[n];
dim = Transpose[{dn, Reverse[dn]}];
rdim = RandomChoice[dim];
b = n*eps;
nr = r*x /. 
   Solve[b == Times @@ Subtract @@ (r*x), x, PositiveReals][[1]];
nr = # - (Plus @@ nr/2 - Plus @@ r/2) & /@ nr // RootReduce;
Partition[
   Table[i, {i, nr[[1, 1]], nr[[2, 1]], Abs[nr[[1, 1]] - nr[[2, 1]]]/
     rdim[[1]]}], 2, 1] // RootReduce;
Partition[
   Table[i, {i, nr[[1, 2]], nr[[2, 2]], Abs[nr[[1, 2]] - nr[[2, 2]]]/
     rdim[[2]]}], 2, 1] // RootReduce;
Transpose /@ Tuples[{%%, %}];
Graphics[{Rectangle @@ r, EdgeForm[Red], Green, Opacity[0.5], 
  Rectangle @@@ %}]

enter image description here enter image description here enter image description here enter image description here

$\endgroup$
1
  • $\begingroup$ Can you help answer this post? $\endgroup$
    – Arbuja
    Aug 29, 2023 at 19:56

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.