For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap.

So the challenge is simply: given a two dimensional area $a$ (topLeft: int, topRight: int, width: int, height:int), a number of squares required $n$ and a size for each square $s$: generate a list $L$ of $|L|=n$ squares in $a$ where the following condition holds. $$\forall q,r \in L , q \neq r \implies \textrm{no_overlap}(q,r) \land \textrm{inside}(q,a) $$ where no_overlap is a function that checks if square $q$ and $r$ do not overlap given the size $s$ and inside(q,a) checks if square $q$ is completely inside the area $a$.

I tried coming up with a solution myself but the only thing I can find is to brute force generating a square, check if there is overlap and if not ,add it to $L$. But as one might see, this algorithm could theoretically run forever. I would need something which is guaranteed to work in a finite time and preferably be of a complexity of at most $\mathcal{O}(n^2)$. So I thought to myself, maybe I could share this with other people around the world and see what clever ideas they have in mind. I most certainly find it an interesing theoretical question to ask. The practical reason is for a Unity 3D (game) project I am making.

EDIT: This would be a possible solution graphically illustrated for $n=7$ enter image description here

  • $\begingroup$ (Doesn't this look $height*width$ choose $n$?) $\endgroup$
    – greybeard
    Dec 25 '20 at 18:35
  • $\begingroup$ Why can't you just generate squares $(0,0,s,s)$, $(0, s, s, 2s)$, $\ldots$, $(0, ks, s, (k+1) s)$, $(s, 0, 2s, s)$, $(s, s, 2s, 2s)$, $\ldots$. $\endgroup$
    – user114966
    Dec 25 '20 at 19:04
  • $\begingroup$ Are we allowed to rotate the squares inside the area $a$? So that we can efficiently use the space... $\endgroup$ Dec 25 '20 at 20:22
  • $\begingroup$ Assuming $s$ integral too, I thought rotation doesn't me anywhere. But there are square numbers that are sums of two squares and three orientations for rectangles that size. $\endgroup$
    – greybeard
    Dec 26 '20 at 8:58
  • 1
    $\begingroup$ @Inuyashayagami yes the rotation of the squares is of no concern $\endgroup$ Dec 26 '20 at 10:31

You could perhaps use a 2 dimensional k-d tree to store the set of free positions $(x, y)$ where the left upper corner of a new square could be chosen without overlapping the existing squares. Each node of the tree covers a region in the area $a$ and you can decorate this node with this region's coordinate and the number of free positions that it contains. At the top of the tree, you can read the total number of available slots and simply choose a random number to get the index of that slot. By walking downwards in the tree, you can find which slot corresponds to this random number, then update the tree accordingly to add a new square.

My intuition is that the amount of data contained in the tree is approximately proportional to the number $k$ of squares already chosen and that the addition of a new square should be proportional to $\log k$ on average.

Edit: I wrote a working implementation in python 3 by using a tree structure. I'm not sure about the performance for large $n$ but it could already be measured experimentally. I didn't make any effort to balance the tree but as new squares are chosen randomly, this randomness should balance the tree on average.

Here is a link to the program. I don't know if I can paste it in this post. It chooses randomly at most 10 squares that don't touch each other. Here is an example output enter image description here

  • $\begingroup$ Interesting theory, but $a$ is continious so there could actually be infinite free spaces but you answer would be an acutal solution to my practical problem $\endgroup$ Dec 27 '20 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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