Best approach to fit n rectangles into a screen

General FreeBASIC programming questions.
UEZ
Posts: 518
Joined: May 05, 2017 19:59
Location: Germany

Best approach to fit n rectangles into a screen

During the coding of Corona Infection Simulation I split the screen into 256 rectangle to have a better collision detection performance which seems to work properly.

But during the change of the n rectangles I saw that to solve it properly is not a easy task.

What is the best approach to fit n as equal rectangles as possible into a screen (image)?

Here my version:

Code: Select all

`'Coded by UEZ build 2020-03-29#Define Ceiling(x)   (-((-(x) * 2.0 - 0.5) Shr 1))Type vZone   Dim As Short x1, y1, x2, y2   Dim As Ulong cEnd Type'Original code by Neptilo @ https://math.stackexchange.com/questions/466198/algorithm-to-get-the-maximum-size-of-n-squares-that-fit-into-a-rectangle-with-a'Modified by UEZSub Split(Zones() As vZone, iZones As Ushort, iW As Ushort, iH As Ushort)   Dim As Single ratio = Iif(Frac(Sqr(iZones)) = 0, 1, iW / iH)   Dim As Single ncols_float = Sqr(iZones * ratio), nrows_float = iZones / ncols_float      'Find best option filling the whole height   Dim As Uinteger nrows1 = Ceiling(nrows_float), ncols1 = Ceiling(iZones / nrows1)   While nrows1 * ratio < ncols1      nrows1 += 1      ncols1 = Ceiling(iZones / nrows1)   Wend   Dim As Single cell_size1 = iH / nrows1      'Find best option filling the whole width   Dim As Uinteger ncols2 = Ceiling(ncols_float), nrows2 = Ceiling(iZones / ncols2)   While ncols2 < nrows2 * ratio      ncols2 += 1      nrows2 = Ceiling(iZones / ncols2)   Wend   Dim As Single cell_size2 = iW / ncols2   'Find the best values   Dim As Uinteger nrows, ncols   If cell_size1 < cell_size2 Then      nrows = nrows1      ncols = ncols1   Else      nrows = nrows2      ncols = ncols2   End If      Dim As Uinteger i,j, k, x, y   Dim As Integer dz = iZones - (nrows * ncols), bz = Iif(dz <> 0, 1, 0)   Dim As Single dx = iW / ncols, dy = iH / nrows      For j = 0 To nrows - 1 - bz      For i = 0 To ncols - 1         x = Cuint(i * dx)         Zones(k).x1 = x         Zones(k).x2 = x + dx         Zones(k).y1 = (j Mod nrows) * dy         Zones(k).y2 = Zones(k).y1 + dy         k += 1      Next   Next      If bz Then      ncols = iZones - k      dx = iW / ncols      For i = 0 To ncols - 1         x = Cuint(i * dx)         Zones(k).x1 = x         Zones(k).x2 = x + dx         Zones(k).y1 = (j Mod nrows) * dy         Zones(k).y2 = Zones(k).y1 + dy         k += 1      Next   End IfEnd SubConst As UShort iW = 1024, iH = 768Const As ULong  iBGColor = &hFF000000ScreenRes iW, iH, 32, , 100Dim As Ushort iZones = 33, iDim Shared As vZone Zones(iZones)Split(Zones(), iZones, iW, iH)Randomize , 2For i = 0 To iZones - 1   Zones(i).c = &HFF000000 Or Culng(Rnd() * &hFFFFFF)   '? i & ": " & "x1="&Zones(i).x1, "y1=" & Zones(i).y1, "x2="&Zones(i).x2, "y2=" & Zones(i).y2   Line (Zones(i).x1, Zones(i).y1)-(Zones(i).x2, Zones(i).y2), Zones(i).c, BF   Draw String (Zones(i).x1 + 2, Zones(i).y1 + 2), Str(i + 1), &hFFFFFFFFNextDo    Sleep 10, 1Loop Until Len(InKey())`
Tourist Trap
Posts: 2844
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

UEZ wrote:During the coding of Corona Infection Simulation I split the screen into 256 rectangle to have a better collision detection performance which seems to work properly.

But during the change of the n rectangles I saw that to solve it properly is not a easy task.

What is the best approach to fit n as equal rectangles as possible into a screen (image)?

Hi UEZ,

it's not clear to me. You use a grid or do you pack n different rectangles?
UEZ
Posts: 518
Joined: May 05, 2017 19:59
Location: Germany

Re: Best approach to fit n rectangles into a screen

Tourist Trap wrote:
UEZ wrote:During the coding of Corona Infection Simulation I split the screen into 256 rectangle to have a better collision detection performance which seems to work properly.

But during the change of the n rectangles I saw that to solve it properly is not a easy task.

What is the best approach to fit n as equal rectangles as possible into a screen (image)?

Hi UEZ,

it's not clear to me. You use a grid or do you pack n different rectangles?

If you change in line 75 the variable iZones then you will see that the partition of the zones is different. For example if you set iZones = 13 then you will have 3 rows each 4 rectangles but the last row is only on rectangle.
So the question is how to organize these 13 rectangles that it fit as equal rectangles as possible.

Of course it depends on the image resolution and the amount of zones how the partition will be created.

For quadratic iZones value you will get best partition constellations.
Posts: 127
Joined: May 28, 2009 20:07

Re: Best approach to fit n rectangles into a screen

Code: Select all

`screen 19,32dim as single xbox,ybox,xtile,ytiledim as integer numtiles,afactor,bfactor,diff,ndiffnumtiles=52xbox=320ybox=240afactor=numtilesbfactor=1do   if (afactor mod 2) then exit do      diff=abs(afactor-bfactor)   ndiff=abs(afactor/2 - bfactor*2)   if ndiff>=diff then exit do      afactor /=2   bfactor *=2loopxtile=xbox/afactorytile=ybox/bfactorline (0,50)-(xbox-1,ybox-1+ 50),&HFF5500,bffor k as integer=0 to bfactor-1    for i as integer=0 to afactor-1          line(i*xtile,k*ytile + 50)-(i*xtile + xtile-1,k*ytile + ytile-1 + 50),&HFFFF00,b   next inext kprint afactor,bfactor,xtile,ytilesleep`

but maybe I didn't understand the topic
ps:odd tile numbers could still be optimized
Mutton
UEZ
Posts: 518
Joined: May 05, 2017 19:59
Location: Germany

Re: Best approach to fit n rectangles into a screen

Well, let me try to explain it:

Let say you have an image with a defined width and height and you want to partition this image into n grid zones whereas the grid zones should have as equal rectangles size as possible.

For example your image size is 99x99 and you want to have 9 grid zones then you will have 9 grid zones each with a dimension of 33x33.

But if you want to have 11 grid zones how should the grid zones resized that you will have 11 grid zones which covers the complete image and have as equal grid sizes as possible?

@Muttonhead: yes, your zones are at least correct but it produces stripes e.g. for 17 tiles. The result should be more quadratic rather than stripes as it is in my example.

The background is that I want to partition the image into zones to bundle a group of pixel for collision check within each grid zone to avoid unnecessary checks for pixel which are "far away" from each other.
Posts: 127
Joined: May 28, 2009 20:07

Re: Best approach to fit n rectangles into a screen

remember, 13,11,17..... are prime numbers. in these cases are stripes only possible.
Mutton
Last edited by Muttonhead on Mar 29, 2020 22:00, edited 2 times in total.
Tourist Trap
Posts: 2844
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

UEZ wrote:Of course it depends on the image resolution and the amount of zones how the partition will be created.

Ok thanks.
As I understand it now, there is one first most obvious configuration, the regular grid.
In this case, let's the screen have a rectangle area of NxM, then we want to cover it by r rectangles of pxq dimensions, stacked in the way of a grid.
So we have pX = N, and qY = M, and r = XY.
Then if for example, r = 21, X may well be 3, and Y = 7. So the dimension p is equal to N/3, and q = M/7. N and M given by the screen dimensions.
But that's worst if we want r = 13 small grid rectangles. Then X = 1 and Y = 13, or reversly, is the unique match (not a balanced stuff).

If we don't stick at the grid configuration, then what is left can be something like:
Sum(Ai) = NxM with N, M the sides of the screen area;
Min(Ai – Aj) for all i, j, where some Ai is the area of one of the small rectangles.

In the case of the grid Ai - Aj = 0 all the time, so it's the perfect case, but it fails giving something balanced for case like prime numbers for instance (as pointed out by Muttonhead above!).
Maybe we still can have such a good deal by rotating some rectangles, but I'm not sure how to do that.
And maybe also we can have more complex configurations that globally give a good compromise, but this also, I don't know about.

Of course all of that doesn't help that much. I just try to make it clear in my head... I 'm curious to see if someone knows a trick to solve this :)
Posts: 127
Joined: May 28, 2009 20:07

Re: Best approach to fit n rectangles into a screen

Code: Select all

`screen 19,32dim as single xbox,ybox,xtile,ytiledim as integer numtiles,afactor,bfactor,diff,ndiff,Qnumtiles=39xbox=640ybox=480afactor=1bfactor=numtilesQ=2do   do      if (bfactor mod Q) then exit do            diff=abs(afactor-bfactor)      ndiff=abs(afactor*Q - bfactor/Q)      if ndiff>=diff then exit do            afactor *=Q      bfactor /=Q   loop   Q +=1loop until Q=9xtile=xbox/afactorytile=ybox/bfactorline (0,50)-(xbox-1,ybox-1+ 50),&HFF5500,bffor k as integer=0 to bfactor-1    for i as integer=0 to afactor-1          line(i*xtile,k*ytile + 50)-(i*xtile + xtile-1,k*ytile + ytile-1 + 50),&HFFFF00,b   next inext kprint numtiles &" = "& afactor &" * "& bfactorsleep`

with better "odd tilenumber handling"
Mutton
Tourist Trap
Posts: 2844
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

Code: Select all

`'we want R rectangles covering the screen in a most balanced wayconst R => 114const W => 800const H => 600screenRes W, H, 32type RECTANGLE    as integer  x    as integer  y    as integer  index    as integer  direction    as integer  horizontalLength    as integer  verticalLength    declare sub DrawRectangle()end typesub RECTANGLE.DrawRectangle()    line (THIS.x, THIS.y)-step(THIS.horizontalLength, THIS.verticalLength), rgb(12,45,85)*THIS.index, bfend subsub FindMostEvenDivisors(byval InNum as integer, byref OutDiv1 as integer,  byref OutDiv2 as integer)     type P        as integer div1        as integer div2        as integer delta    end type    dim as P array(any)    for div as integer = 1 to InNum        if (InNum mod div)=0 then            redim preserve array(uBound(array) + 1)            array(uBound(array)).div1 = div            array(uBound(array)).div2 = InNum\div            array(uBound(array)).delta = abs(div - InNum\div)        end if    next div    dim as integer min = 1e+9    dim as integer minIndex = -1    for index as integer = lBound(array) to uBound(array)        if array(index).delta<min then            min = array(index).delta            minIndex = index        end if    next index    OutDiv1 = array(minIndex).div1    OutDiv2 = array(minIndex).div2end subdim as integer  divisor1, divisor2FindMostEvenDivisors(R, divisor1, divisor2)dim as RECTANGLE    array(R - 1)for indexX as integer = 1 to divisor1    for indexY as integer = 1 to divisor2        array(indexX * indexY - 1).x  =  (indexX - 1)*(W/divisor1)        array(indexX * indexY - 1).y          =  (indexY - 1)*(H/divisor2)        array(indexX * indexY - 1).index      =  indexX * indexY - 1        array(indexX * indexY - 1).direction  =  0        array(indexX * indexY - 1).horizontalLength   =  (W/divisor1)        array(indexX * indexY - 1).verticalLength     =  (H/divisor2)        array(indexX * indexY - 1).DrawRectangle()    next indexYnext indexX? divisor1; "x"; divisor2; "="; RgetKey()`

Doing same as everyone, but with some room left for later trying to play with rearrangement of the rectangles.
paul doe
Posts: 1175
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Best approach to fit n rectangles into a screen

UEZ wrote:...
The background is that I want to partition the image into zones to bundle a group of pixel for collision check within each grid zone to avoid unnecessary checks for pixel which are "far away" from each other.

Isn't this just a specialized quadtree? Or you can also use spatial hashing...
UEZ
Posts: 518
Joined: May 05, 2017 19:59
Location: Germany

Re: Best approach to fit n rectangles into a screen

@Tourist Trap, Muttonhead: your solution creates stripes, for example using 13 grid zones. As already mentioned the objective is to create similarly sized square-like grid zones. Otherwise you have to check pixels on two ends with each other.

@paul doe: I'm not sure if it the same thing what I'm looking for but spatial hashing sounds promising...

Here an image for grid zones 1, 2, 3 and 4

I marked the best solutions for 3 and 4.

A good solution for 5 grid zones might look this way:
Tourist Trap
Posts: 2844
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

[quote="UEZ"]
A good solution for 5 grid zones might look this way/quote]
Yes it's what I'm looking for. Still having to figure out how do that.

Has someone noticed that the forum tells Mar. 30/03, while this is Monday?
SARG
Posts: 1036
Joined: May 27, 2005 7:15
Location: FRANCE

Re: Best approach to fit n rectangles into a screen

Mar....ch
Tourist Trap
Posts: 2844
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

SARG wrote:Mar....ch

Yep, so I need a big coffee!
paul doe
Posts: 1175
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Best approach to fit n rectangles into a screen

UEZ wrote:...
@paul doe: I'm not sure if it the same thing what I'm looking for but spatial hashing sounds promising...

Both quadtrees and spatial hashes are fine, but SH tends to overperform quadtrees for a large margin, until they eventually catch up (we're talking tens of millions of entities here). And, if the space is known in advance (and it's static ie it doesn't dynamically grow), they can be as simple to implement as a two-dimensional array, with the 'hash' just being the coordinates for each bucket.
UEZ wrote:...
Here an image for grid zones 1, 2, 3 and 4
...

Turns out that somebody has already solved the same problem: UI layouters. These could prove handy:

https://croisant.net/blog/2016-02-24-ui-layout-constraints-part-1/