Diskuze: Algoritmus: společné oblastni ve 2D poli
Tvůrce
Zobrazeno 6 zpráv z 6.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
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.