Diskuze: Algoritmus: společné oblastni ve 2D poli
V předchozím kvízu, Online test znalostí JavaScript, jsme si ověřili nabyté zkušenosti z kurzu.

Tvůrce

Zobrazeno 6 zpráv z 6.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
V předchozím kvízu, Online test znalostí JavaScript, jsme si ověřili nabyté zkušenosti z kurzu.
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.