Optimalizace rozložení objektů na plátně

Jakých objektů na jakém plátně?

Možná chceš udělat něco podobného této koláži.

Jozin:
No sice to s tvorbou webu vůbec nesouvisí, ale budiž.

1. Kolik je tak rozdílných tvarů velikostí? (jeden trojůheník je jako druhý nebo každý trojůhelník má jiný rozměr)
2. Jaké jsou poměry mezi velikostmi?
3. Kolik je kusů?
4. Jak moc to musí být přesné? (musí se vždy najít nejoptimálnější řešení, nebo stačí algoritmus, který najde dobré rozložení i když ne to optimální (liší se třeba od sebe o 3%))
- takovéto výpočty bývají často náročné, proto je výhodnější (někdy dokonce nutné) povolit nějakou toleranci. Tím se ale výpočet může i mnohonásobně zrychlit.

5. Nešlo by to udělat ručně? Člověk na rozdíl od počítače pozná, že tudy asi cesta nepovede a proto nemusí testovat slepé uličky.

Ještě doplňující otázky:
- je ten plech/dřevo z obou stran stejný? Ptám se kvůli těm trojůhelníkům, jestli by se dali v řípadě potřeby převrátit.
- Pokud je ta plocha mnohem větší, než z ní vyřezávané objekty (plocha objektů je třeba zabere třeba 25% plochy), jak se mají objekty naskládat?

Úlohu bych si jednodušil tak, že bych pracoval jen s obdélníky. Dejme tomu, že máme mnoho kružnic o stejném poloměru a máme jimi vyplnit plochu. Buď je budeme řadit v čtvercovém rozložení nebo do trojůhelníku. Trojúhelnkové rozložení je nejlepší, avšak výsledný tvar, avšak čtvercové rozložení nemá "odpadovou plochu" o moc větší. Jenže my nebude mít stejné kruhy a trojúhelníkové rozložení moc dělat nejde. Šla by sice vytvářet jakási kytka z kružnic seřazených od největší po nejmenší zatočená do spirály, jenže výsledný tvar by nebyl nic moc. Pokud ale každé kružnici "opíšeme" čtverec, tak bychom vlastně používali čtvercové rozložení, které není o moc horší, ale se čtverci se nám bude lépe pracovat. Proto bych z každé kružnice vytvořil čtverec o straně poloměru kružnice. Tímto jsme se zbavili kružnic.
Něco podobného provedeme i s trojúhelníky. Pokud bychom měli 2 shodné trojúhelníky, mohli bychom je dát k sobě tak, aby se z nich vytvořil obdélník, který by měl strany rovné odvěsnám. Jelikož 2 shodné trojúhelníky mít nebudeme, musíme vybrat vždy ty nejpodobnější (podobné délky stran) a vytvoříme z nich obdélník o stranách které budou rovny 2 nejdelším ze 4 odvěsen trojúhelníků.
Tímto jsme si problém zjednodušili jen na práci s obdélníky. No a jak zabalit různé obdélníky do co nejmenšího prostoru doporučuje wiki tuto stránku. Což nám vlastně vytvoří ten druhý případ "Do obdélníku do rohu".
Pokud bychom se chtěli dostat té první variantě, mám k tomu taky několik nápadů, ale bylo by to na dlouhé rozepisování a ani ty nápady nemám ničím podloženy. Tím myslím relevantní zdroje, případně nějaké vlastní testy či výpočty. Na to totiž nemám čas. Pokud byste měl zájem, mohu vám své nápady sem napsat a vy si je otestujete s jakou úspěšností vybírají řešení.

Jozin:
Ide o zložitý matematický problém a asi nenájdeš hotové riešenie, ktoré by si si len upravil.
Každý užívateľ to má vyrezané z rovnakého materiálu?
A ak áno, alebo je tých materiálov len niekoľko, nebude jednoduchšie z jedných tabulí rezať len trojuholníky, z iných len obdĺžniky a z ďalších kruhy? A výrobca by vždy posúdil, či sa dá ešte použiť nejaká stará tabuľa na vyrezanie tvaru.