Diskuze: Algoritmus: společné oblastni ve 2D poli

Tvůrce

Zobrazeno 6 zpráv z 6.
Tak jsem přišel na řešení s celkem pěknou náročností (maximálně O(M2 N2)). Napsal jsem třídu v JavaSCriptu, která s tímto algoritmem pracuje. Má několik závislostí na mých dalších třídách. Jsou to <strong>dge.Rectangle</strong> (podobná třída, jako je třeba Rectangle z Javy nebo ze C#, jen je implementovaný jako Immutable Object) a <strong>dge.CollisionMap</strong>, což je vlastně 2D pole s několika metodami navíc pro lepší manipulaci. Samotná třída je napsána po vzoru Johna Resiga (http://ejohn.org/…inheritance/)
Algoritmus hledá obdélník od levého horního rohu. Pro každý bod se snaží rozšířit základ (Rectangle 1x1) dolů, vpravo a po diagonále. Ukládá si obsah jednotlivých nalezených oblastí, který pak porovnává a vybere ten největší (pro každý bod pole).
Třída má jednoduché rozhraní. V konstruktoru požaduje 2D pole (v mém
případě objekt typu dge.CollisionMap, lze to ale celkem snadno upravit).
Metoda next() najde největší obdélník v poli a odstraní ho ze zásobníku
(kopie pole). Pokud již žádný obdélník v poli není, vrátí 0. Tohle
konkrétní pole zabralo 7 iterací algoritmu (pro každý obdélník složitost
max. O( M2 N2)) Čím větší oblasti se ve 2D poli
nachází, tím logicky méně krát se musí algoritmus (resp. metoda .next())
provést. U tohohle pole zrovna zbyly 2 samostatné oblasti 1x1. Takové oblasti
by mohl algoritmus klidně ignorovat a zpracovávat je až později s
vykreslením a algoritmus by se tak mohl provést jen 5x, ale to už se mi
nechtělo implementovat
Animace ještě ukazuje průběh algoritmu. V JavaScriptu jde celkem rychle.
Třída MaxRectangle: http://www.itnetwork.cz/dev-lighter/33
Díky Nebyla to zrovna
sranda. Lámal jsem si nad tím hlavu dva dny. Když jsem to hledal na
internetu, našel jsem dokonce méně náročné řešení, než tady ukazuji,
ale to se mi nepovedlo implementovat, protože to vysvětlení bylo strašně
nejasné. Jsem ale rád, že mám alespoň tohle. Můžu spustit jen jednou a
výsledky zapsat do cache třeba nebo JSON a už to nemusím znovu generovat
ale pro pole o velikosti
42*11 zpracování webkitu trvalo nějakých 15ms
EDIT: někdy se pokusím odstranit ty závislosti a napíšu o tom sem,
protože o tom nikde nic není Teď je to vysvětlení a kód pro ostatní asi celkem nepoužitelné.
Takže tohle je taková brute-force? Prostě to zkouší pokládat obdélníky kam jdou a pak vybere největší a vymázne ho?
Tak trochu Akorát při
tom rozšiřování se to snaží rozšiřovat, jen když to má smysl, takže
tam nemusím znova procházet všechna pole.
Zobrazeno 6 zpráv z 6.