Autor Zpráva
Jozin
Profil
Zdravím,

mám takový menší problém, chtěl bych napsat script na rozložení objektů na plátně tak, aby se ušetřilo co nejvíce místa, hledal jsem nějaký algoritmus, ale zasekl jsem se na tom, že nevím, pod čím to hledat.

Moje otázka tedy je: "Jak by se to dalo udělat případně pod čím takovou věc hledat?", za každou odpověď předem děkuji,

Jozin.
Keeehi
Profil
Jakých objektů na jakém plátně?

Možná chceš udělat něco podobného této koláži.
Jozin
Profil
Jde o různé trojúhelníky kruhy a obdélníky, plátno je ve skutečnosti paleta plechová nebo dřevěná a z ní se budou tyto objekty vyřezávat, jde o to, aby se to udělalo tak, aby bylo co nejméně odpadu...
Keeehi
Profil
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.
Jozin
Profil
Keeehi:
ad 1. velikosti mohou být kdykoli jiné (zadává uživatel), tvary jsou tři, které jsem uvedl
ad 2. poměry mezi velikostmi se nedají určit, určí se až z toho, jaké rozměry zadá uživatel, vždy ale vím, že mám kruh, obdélník nebo pravoúhlý trojúhelník
ad 3. kusů je pokaždé jiný počet
ad 4. přesnost jsem nijak nedostal zadanou, jen se to má vygenerovat a myslím, že když už se to generuje, mělo by se to vygenerovat optimálně, takže nemusí to být naprosto nejlepší řešení, ale takové, které lze v reálném čase vypočítat... co jsem se koukal na výřezy, tak průměrný počet vyřezávaných objektů je něco okolo 20-ti
as 5. ano to by samozřejmě šlo, ale beru to jako nouzové řešení, když tento problém nevyřeším.

co se týče zaměření, je pravda, že to nehodlám dělat v PHP nebo .NET, ale dalo by se... nicméně jsem myslel, že v "Jak něco udělat?" může být cokoli. Jinak děkuji za reakce.
Keeehi
Profil
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?

K jedné straně:      Do obdélníku do rohu:
_____________        _____________
|xxxxxxxxxxx|        |xxx|       |
|-----------|        |xxx|       |
|           |        |xxx|       |
|           |        |---        |
|           |        |           |
|           |        |           |
|           |        |           |
-------------        -------------
Jozin
Profil
- plotna je stejná z obou stran, takže se převrátit dá, ikdyby nebyla, tak se dá otočit...
- objekty by měli být naskládány tak, aby bylo zapotřebí co nejméně řezů a bylo co nejméně odpadu, v případě k jedné straně, jak jsi napsal by byla mnohem výhodnější, zbyla by celá plotna bez horního pásu, naopak v řešení do obdélníku do rohu, by vznikl zub a musela by se celá plotna řezat 2x... v případě, že by však byly na výšku do konce plotny nebo i na šířku, pak jsou obě řešení správné a vybral bych asi tu první možnost, ale to by záleželo, kterou možnost by algoritmus sestavil první...
Keeehi
Profil
Ú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í.
_es
Profil
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.
Jozin
Profil
Keeehi:
Děkuji za "teorii" a materiál, asi to tak nějak udělám

_es:
nehledal jsem hotové řešení, ale spíš materiál zabývající se optimalizací uspořádání těch objektů, stačilo mi teoreticky, algoritmus jako takový už nějak udělám.
Co se týče materiálu vs. uživatel. Uživatel mi zadá jen rozměry palety a zvětšení rámečku, například aby dva objekty na sebe nebyly nalepeny tak, že při řezání budou menší nebo deformované (u kruhu).
Z jedné tabule se vyřezávají všechny typy tvarů, ne vždy, ale musím to předpokládat, protože čas od času to tak je...
Použití staré tabule je možné, při vstupu jen uživatel zadá jiné rozměry.

Děkuji za reakce a už bych tento topic prohlásil za uzavřený,
Jozin,

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: