Best approach to fit n rectangles into a screen

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

Best approach to fit n rectangles into a screen

Post by UEZ »

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 c
End 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 UEZ
Sub 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 If
End Sub

Const As UShort iW = 1024, iH = 768
Const As ULong  iBGColor = &hFF000000

ScreenRes iW, iH, 32, , 100

Dim As Ushort iZones = 33, i
Dim Shared As vZone Zones(iZones)

Split(Zones(), iZones, iW, iH)

Randomize , 2
For 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), &hFFFFFFFF
Next


Do
    Sleep 10, 1
Loop Until Len(InKey())
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

Post by Tourist Trap »

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: 972
Joined: May 05, 2017 19:59
Location: Germany

Re: Best approach to fit n rectangles into a screen

Post by UEZ »

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.
Muttonhead
Posts: 139
Joined: May 28, 2009 20:07

Re: Best approach to fit n rectangles into a screen

Post by Muttonhead »

Code: Select all

screen 19,32

dim as single xbox,ybox,xtile,ytile
dim as integer numtiles,afactor,bfactor,diff,ndiff
numtiles=52

xbox=320
ybox=240

afactor=numtiles
bfactor=1

do
	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 *=2
loop

xtile=xbox/afactor
ytile=ybox/bfactor

line (0,50)-(xbox-1,ybox-1+ 50),&HFF5500,bf
for 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 i
next k

print afactor,bfactor,xtile,ytile

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

Re: Best approach to fit n rectangles into a screen

Post by UEZ »

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.
Muttonhead
Posts: 139
Joined: May 28, 2009 20:07

Re: Best approach to fit n rectangles into a screen

Post by Muttonhead »

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: 2958
Joined: Jun 02, 2015 16:24

Re: Best approach to fit n rectangles into a screen

Post by Tourist Trap »

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 :)
Muttonhead
Posts: 139
Joined: May 28, 2009 20:07

Re: Best approach to fit n rectangles into a screen

Post by Muttonhead »

Code: Select all

screen 19,32

dim as single xbox,ybox,xtile,ytile
dim as integer numtiles,afactor,bfactor,diff,ndiff,Q
numtiles=39

xbox=640
ybox=480

afactor=1
bfactor=numtiles


Q=2
do
	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 +=1
loop until Q=9

xtile=xbox/afactor
ytile=ybox/bfactor

line (0,50)-(xbox-1,ybox-1+ 50),&HFF5500,bf
for 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 i
next k

print numtiles &" = "& afactor &" * "& bfactor

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

Re: Best approach to fit n rectangles into a screen

Post by Tourist Trap »

Code: Select all

'we want R rectangles covering the screen in a most balanced way

const R => 114
const W => 800
const H => 600
screenRes W, H, 32

type RECTANGLE
    as integer  x
    as integer  y
    as integer  index
    as integer  direction
    as integer  horizontalLength
    as integer  verticalLength
    declare sub DrawRectangle()
end type
sub RECTANGLE.DrawRectangle()
    line (THIS.x, THIS.y)-step(THIS.horizontalLength, THIS.verticalLength), rgb(12,45,85)*THIS.index, bf
end sub

sub 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).div2
end sub

dim as integer  divisor1, divisor2
FindMostEvenDivisors(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 indexY
next indexX

? divisor1; "x"; divisor2; "="; R

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

Re: Best approach to fit n rectangles into a screen

Post by paul doe »

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: 972
Joined: May 05, 2017 19:59
Location: Germany

Re: Best approach to fit n rectangles into a screen

Post by UEZ »

@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

Image

I marked the best solutions for 3 and 4.

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

Re: Best approach to fit n rectangles into a screen

Post by Tourist Trap »

[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: 1756
Joined: May 27, 2005 7:15
Location: FRANCE

Re: Best approach to fit n rectangles into a screen

Post by SARG »

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

Re: Best approach to fit n rectangles into a screen

Post by Tourist Trap »

SARG wrote:Mar....ch
Yep, so I need a big coffee!
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Best approach to fit n rectangles into a screen

Post by paul doe »

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 ... ts-part-1/
http://sanchezcuadrado.es/papers/ist201 ... erence.pdf
http://www.squidi.net/three/entry.php?id=167

But notice that, ideally, you don't only want an efficient spatial partitioning method but, for this particular application, you need it to be spatially consistent! Otherwise, you'll lose in checking for adjacencies what you gained in bucketing your entities in the first place...
Post Reply