2D packing algoritmust keresek

chatgpt mit mond?

Vagy félreértek valamit, vagy a feladat a jelen, általános formájában nem megoldható.

A leírt lefedéshez szerintem teljesülnie kellene annak a  kényszerfeltételnek a "referencia téglalap" és a lefedendő téglalap oldalarányai között, hogy azok hányadosa kötelezően egész. (Tehát nem kell az oldalaránynak is azonosnak lennie, de páronként a hányados egész kell legyen.)

(Disclaimer: csupán természetes intelligenciával rendelkezem, tehát nem vagyok tévedhetetlen, és még soha nem mertem kipróbálni a bagolyfőzelék receptjét.)

Szerk.: tévedtem. Elég, ha kellően kis számokkal kifejezhető racionális szám a hányadosuk. Szóval kellene valamilyen "granularitási fokot" megállapítani, ami a kérdéses felhasználás esetén nyilván az "egy pixel" kell legyen. 

Szerk. 2: Tehát azt a szót kerestem, hogy "legnagyobb közös osztó"... Az kell hogy legyen nekik, és nem lehet túl kicsi. Na, megyek, csinálok inkább egy jó vidrapörköltet.

Lehet benéztem a feladatot, de nekem első körben x,y prímfelbontása lenne a kiindulópontom, majd lnko.

Ps.: Benéztem. Én csak felosztottam. ;)

az nem egy megoldas, hogy az alap teglalap Ax*Ay, ekkor n x(Ax * Ay/n) egymas alatt szepen, matrix-szeru is, ki is tolti az alap A dolgot. 

Warhol? :))

Az nem megoldás, hogy erre a < 50 esetre kézzel készítesz elrendezéseket? Tudom, ez nem tudományos...

Akkor lehet lefedni teljesen a játékteret, ha az is egybevágó. Ez ugye nem feltétlen lesz egybevágó a monitoroddal, ezért vagy jobb szélen, vagy alul lesz fekete csík oldalaránytól függően.

(Szerk: itt volt egy marhaság, javítva)

Ha a monitorod mérete pixelben X*Y, a referencia képed oldalaránya 'r' (oldalai a,b és így b=r*a), akkor az egybevágó játéktér mérete:

Xm = X if r * X < Y else Y / r

Ym = Y if Y / r < X else X * r

Ezt hézagmentesen lefedni egybevágó téglalapokkal négyezetesen lehet (1x1, 2x2, 3x3...)

Ebben a referenciakép a bal felső sarokban szintén csak akkor lesz egybevágó, ha négyzetesen foglal el helyet. Innentől kezdve ideális fedés ezekben az esetekben lehetséges:

Board: 2x2, Index: 1x1, n = 3
Board: 3x3, Index: 1x1, n = 8
Board: 3x3, Index: 2x2, n = 5
Board: 4x4, Index: 1x1, n = 15
Board: 4x4, Index: 2x2, n = 12
Board: 4x4, Index: 3x3, n = 7
Board: 5x5, Index: 1x1, n = 24
Board: 5x5, Index: 2x2, n = 21
Board: 5x5, Index: 3x3, n = 16
Board: 5x5, Index: 4x4, n = 9
Board: 6x6, Index: 1x1, n = 35
Board: 6x6, Index: 2x2, n = 32
Board: 6x6, Index: 3x3, n = 27
Board: 6x6, Index: 4x4, n = 20
Board: 6x6, Index: 5x5, n = 11
Board: 7x7, Index: 1x1, n = 48
Board: 7x7, Index: 2x2, n = 45
Board: 7x7, Index: 3x3, n = 40
Board: 7x7, Index: 4x4, n = 33
Board: 7x7, Index: 5x5, n = 24
Board: 7x7, Index: 6x6, n = 13
Board: 8x8, Index: 4x4, n = 48
Board: 8x8, Index: 5x5, n = 39
Board: 8x8, Index: 6x6, n = 28
Board: 8x8, Index: 7x7, n = 15
Board: 9x9, Index: 6x6, n = 45
Board: 9x9, Index: 7x7, n = 32
Board: 9x9, Index: 8x8, n = 17
Board: 10x10, Index: 8x8, n = 36
Board: 10x10, Index: 9x9, n = 19
Board: 11x11, Index: 9x9, n = 40
Board: 11x11, Index: 10x10, n = 21
Board: 12x12, Index: 10x10, n = 44
Board: 12x12, Index: 11x11, n = 23
Board: 13x13, Index: 11x11, n = 48
Board: 13x13, Index: 12x12, n = 25
Board: 14x14, Index: 13x13, n = 27
Board: 15x15, Index: 14x14, n = 29
Board: 16x16, Index: 15x15, n = 31
Board: 17x17, Index: 16x16, n = 33
Board: 18x18, Index: 17x17, n = 35
Board: 19x19, Index: 18x18, n = 37
Board: 20x20, Index: 19x19, n = 39
Board: 21x21, Index: 20x20, n = 41
Board: 22x22, Index: 21x21, n = 43
Board: 23x23, Index: 22x22, n = 45
Board: 24x24, Index: 23x23, n = 47
Board: 25x25, Index: 24x24, n = 49

for board in range(2, 101):
    for index in range(1, board):
        if(board * board - index * index < 50):
            print(f"Board: {board}x{board}, Index: {index}x{index}, n = {board * board - index * index}")

Általános megoldást nem ismerek, Google OR Tools-ba megpróbálnám felvenni a constraint-eket, aztán lesni mit hoz ki belőle.