NOVINKA - Online rekvalifikační kurz Python programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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.

Aktivity
Avatar
Drahomír Hanák
Tvůrce
Avatar
Drahomír Hanák:6.12.2012 19:43

Zdravím,
řeším problém v JavaScriptu. Mám 2D pole, podle kterého vykresluji čtverce na plátno (pokud je pole[x][y] == 1, vykreslím čtverec na pozici [x, y]). Je ale dost neefektivní vykreslovat každé políčko pole, protože někdy dohromady dávají větší obdélník (resp. čtverec). Jak ale tuhle větší oblast v poli efektivně najít a vykreslit? Neznáte nějaký algoritmus?

Příklad pole:

[
   [1,1,1,1,1,1],
   [1,0,0,1,1,1],
   [1,0,0,1,1,1],
   [1,0,0,0,0,1],
   [0,0,1,0,1,1],
   [0,0,1,1,1,1]
]

Přiložený obrázek ještě ukazuje, o co se snažím.
Děkuji za každou radu.

 
Odpovědět
6.12.2012 19:43
Avatar
Drahomír Hanák
Tvůrce
Avatar
Drahomír Hanák:7.12.2012 21:29

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.Rec­tangle</stron­g> (podobná třída, jako je třeba Rectangle z Javy nebo ze C#, jen je implementovaný jako Immutable Object) a <strong>dge.Co­llisionMap</stron­g>, 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 :P

Animace ještě ukazuje průběh algoritmu. V JavaScriptu jde celkem rychle.

Třída MaxRectangle: http://www.itnetwork.cz/dev-lighter/33

 
Nahoru Odpovědět
7.12.2012 21:29
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Drahomír Hanák
David Hartinger:7.12.2012 22:01

Ty jsi ďábel ]:>

Nahoru Odpovědět
7.12.2012 22:01
New kid back on the block with a R.I.P
Avatar
Drahomír Hanák
Tvůrce
Avatar
Odpovídá na David Hartinger
Drahomír Hanák:7.12.2012 22:14

Díky :D 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é.

Editováno 7.12.2012 22:16
 
Nahoru Odpovědět
7.12.2012 22:14
Avatar
David Hartinger
Vlastník
Avatar
Odpovídá na Drahomír Hanák
David Hartinger:7.12.2012 22:19

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?

Nahoru Odpovědět
7.12.2012 22:19
New kid back on the block with a R.I.P
Avatar
Drahomír Hanák
Tvůrce
Avatar
Odpovídá na David Hartinger
Drahomír Hanák:7.12.2012 22:32

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.

 
Nahoru Odpovědět
7.12.2012 22:32
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.