| Autor | Zpráva | ||
|---|---|---|---|
| Witiko Profil |
#1 · Zasláno: 14. 10. 2010, 17:17:36 · Upravil/a: Witiko
Otázka je čiře programovacího rázu, nicméně hodlám řešení použít v javascriptovém scriptu, takže zde není zcela chybně.
Mám uložená data o tabulce libovolné velikosti. Pro účely příkladu řekněme, že je mám uložené v dvourozměrném poli, jež obsahuje X dalších polí představujících řádky z nichž každé obsahuje X hodnot true / false, které symbolizují vyplněné / nevyplněné políčko. Snažím se vytvořit funkci, která by: 1) Shromáždila veškeré uzavřené tvary (viz. tvar uprostřed ilustračního obrázku nahoře) - toto samotné by šlo nejspíš udělat pomocí projetí cyklem po řádcích a sloupcích a vybíráním všech buněk mezi lichou a sudou vyplněnou buňkou (bylo by posunuté o série vyplněných buněk). Připravenost na diagonály (v ukázkovém obrázku nejsou) není nutná, leč pro generičnost funkce by byla vítaná (asi by stačilo kontrolovat do SW, NW, SE, NE od dané buňky pro kontrolu, jde-li jen o vrcholek) 2) a) Buď brala okraje pole jako skutečné okraje a tvary utvořené kolem nich brala jako uzavřené (viz. tvary kolem rohů na ilustračním obrázku nahoře) b) Nebo by brala okraje jako průchozí a v případě tvaru u okraje by kontrolovala, je-li uzavřený z druhé strany. (viz. neuzavřený tvar napravo obrázku) Zda by se funkce chovala podle a nebo b by se určilo argumentem. Funkce by navracela množinu veškerých uzavřených (červených) buněk. Nechci hotové řešení, nevyžaduji ani script, stačilo by pouze logické nakopnutí nebo schéma. |
||
| Nox Profil |
#2 · Zasláno: 14. 10. 2010, 17:26:36
A co ti teda není jasné? Mj. na řádku může být lichý počet okrajových buněk... momentálně mě nenapadá co s tím v rastrovém podání
|
||
| Witiko Profil |
#3 · Zasláno: 14. 10. 2010, 17:31:54 · Upravil/a: Witiko
Nox:
Co se týče logických úvah, obvykle nemám problém. Nicméně tohle je o obrazovotvornosti a já mám problém to v tom tak nějak vidět. Bod 1 bych snad ještě i nějak ubastlil viz. popis navrhované logiky v postu [#1] odstavec 1, u 2a nějak nevidím efektivní způsob, jak kontrolovat, že je tvar uzavřený kolem okraje a u 2b nevidím jak na to vůbec. Vím, co chci, ale nenapadá mě, jak to vyřešit pomocí nějakého rozumného scriptu. Jinak připraveností na diagonály myslím něco takovéhleho: 
|
||
| Chamurappi Profil |
#4 · Zasláno: 14. 10. 2010, 18:11:51
Reaguji na Witika:
Nejsnazší postup: Určíš si bod uvnitř a vše, co s ním sousedí, vybarvíš. Dále vybarvíš vše, co sousedí se sousedy a se sousedy sousedů atd. — dokud nenarazíš na hranici. Žádná velká věda. Potíž je pak jen v tom, určit co je venku a co uvnitř… a co nepovažuješ za uzavřený obrazec. |
||
| Witiko Profil |
#5 · Zasláno: 14. 10. 2010, 18:19:17 · Upravil/a: Witiko
Chamurappi:
J, to by byl Raycasting. Ale na to, abych to aplikoval potřebuju vědět, kam body umístit, což vyžaduje předchozí znalost pozice tvarů. Já bych potřeboval provést test celého pole. |
||
| _es Profil |
#6 · Zasláno: 14. 10. 2010, 18:26:49
Witiko:
„Já bych potřeboval provést test celého pole.“ Myslíš algoritmus, ktorý prejde celé pole a na koniec znázorní jednotlivé spojité tvary? |
||
| Witiko Profil |
#7 · Zasláno: 14. 10. 2010, 18:46:56
_es:
Prakticky ano, viz post [#1]. |
||
| _es Profil |
#8 · Zasláno: 14. 10. 2010, 19:19:49
Witiko:
Toto: █░░ ░█░ ░░█ |
||
| Witiko Profil |
#9 · Zasláno: 14. 10. 2010, 19:50:50 · Upravil/a: Witiko
_es:
Pokud je █ vyplněná buňka, pak se nejedná o tvar, ale o případné ohraničení tvaru. Jako tvar beru to, co je na ukázkových obrázcích nahoře červeně. Řekněme, že funkci zavolám s tímto polem: funkce([ [0,0,0,1,0,0,0], [0,0,1,0,1,0,0], [0,1,0,0,0,1,0], [0,0,1,0,1,0,0], [0,0,0,1,0,0,0] ]) Měla by navrátit: [ [0,0,0,0,0,0,0], [0,0,0,1,0,0,0], [0,0,1,1,1,0,0], [0,0,0,1,0,0,0], [0,0,0,0,0,0,0] ] Řekněme, že funkci zavolám s tímto polem, kdy se ohraničení dotýká i okrajů: funkce([ [0,0,0,1,0,0,0], [0,0,1,0,1,0,0], [0,1,0,0,0,1,0], [1,0,0,0,0,0,1], [0,1,0,0,0,1,0], [0,0,1,0,1,0,0], [0,0,0,1,0,0,0] ]) V případě 2a i 2b by měla navrátit: [ [1,1,1,0,1,1,1], [1,1,0,1,0,1,1], [1,0,1,1,1,0,1], [0,1,1,1,1,1,0], [1,0,1,1,1,0,1], [1,1,0,1,0,1,1], [1,1,1,0,1,1,1] ] Řekněme, že funkci zavolám s tímto polem, kdy se ohraničení dotýká i okrajů: funkce([ [0,0,1,0,1,0,0], [0,0,1,1,1,0,0], [0,0,0,0,0,0,0] ]) V případě 2a by měla navrátit: [ [0,0,0,1,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0] ] V případě 2b by měla navrátit: [ [0,0,0,0,0,0,0], [0,0,0,0,0,0,0], [0,0,0,0,0,0,0] ] |
||
| _es Profil |
#10 · Zasláno: 14. 10. 2010, 20:09:10 · Upravil/a: _es
Witiko:
„pak se nejedná o tvar, ale o případné ohraničení tvaru. Jako tvar beru to, co je na ukázkových obrázcích nahoře červeně.“ To ti teda nerozumiem, ohraničenie akého tvaru? „Pro účely příkladu řekněme, že je mám uložené v dvourozměrném poli, jež obsahuje X dalších polí představujících řádky z nichž každé obsahuje X hodnot true / false, které symbolizují vyplněné / nevyplněné políčko.“ Tie šedé políčka sú teda true alebo false, teda vyplnené alebo nevyplnené a červené sú aké?
Pre účely tej analýzy musíš predsa najprv definovať spojitosť, teda či tie bunky v [#8] sú alebo nie sú spojené. A logicky by mala každá vyplnené bunka patriť do nejakého tvaru, osamotená bunka je potom čo? Ďalej nechápem, načo to komplikuješ nejakými ohraničeniami, veď stačí algoritmus, ktorý každú vyplnenú bunku zaradí do nejakého tvaru a na konci vypíše zoznam tvarov a ktoré bunky do nich patria, ďalšie veci sa už z toho odvodia ľahko. Podľa toho posledného príspevku, ktorý si dopísal neskôr, chceš niečo ako vypĺňanie dutín v tvaroch? |
||
| Witiko Profil |
#11 · Zasláno: 14. 10. 2010, 20:16:11 · Upravil/a: Witiko
_es:
Bunky v [#8] sú spojené. Šedé sú true, jedná sa o orámovanie. Biele sú false, jedná sa o prázdny priestor. Červené sú to, čo by som chcel aby funkcia vrátila - sumu bodov vnútri uzavretých tvarov. „A logicky by mala každá vyplnené bunka patriť do nejakého tvaru, osamotená bunka je potom čo?“ Osamotená bunka je osamotená bunka, bunky tvorí uzavretý tvar len ak sú pospájané tak, že by som po nich mohol jazdiť donekonečna dookola. Bunky, ktoré neuzatvárajú žiadny tvar ma nezaujímajú. Za tvar sa berie, ak je medzi šedými bunkami orámovania voľné miesto, to miesto je potom vnútro uzavretého tvaru. Dve bunky vedľa seba logicky žiadny tvar netvorí, pretože sa nenachádza nič medzi nimi. Logiku veci pomocou js Arrays rozpisujem tu: [#9] Úvodný obrázok to myslím tiež ilustruje celkom jasne. Ak poznáš hru "Dobývanie územia" , tak to by bol ukážkový príklad použitia tejto funkcie. Hrá sa to na papieri ako piškvorky a keď svojimi políčkami ohraničíš nejakú oblasť, dostaneš bodové ohodnotenie na základe toho, koľko jednotiek si obkľúčil. Pre kontrolu, či došlo k obkľúčenie a následnému získaniu obkľúčených buniek by bola práve táto funkcia ako stavaná. |
||
| _es Profil |
#12 · Zasláno: 14. 10. 2010, 20:56:24 · Upravil/a: _es
Witiko:
„Červené jsou to, co bych chtěl aby funkce navrátila - sumu bodů uvnitř uzavřených tvarů.“ Takže červené sú na začiatku tiež false?
Ten prvý príspevok je písaný dosť nejednoznačne. Pojem uzavretý tvar je dosť nejednoznačný, takýto tvar je aký?: ░░░░░░ ░░░█░░ ░░░█░░ ░░█░█░ ░░░█░░ ░░░█░░ ░░░░░░ Rozdeľ si to do viac krokov: 1) Rozdelenie tých šedých políčok do tvarov, teda všeobecných tvarov, aj jedna osamotená bunka alebo len dve bunky vedľa seba sú tvar. 2) Potom ten istý algoritmus, len nebudeš považovať políčka, spojené len diagonálou, za spojené, použiješ na biele políčka, z neho budeš mať tvary: všetky dutiny a žiadny, jeden alebo viac tvarov navyše - to sú tie políčka, čo majú zostať biele. Možno sa tieto dva kroky dajú dať aj do jedného cyklu. 3) Priradíš správne tvary-dutiny k šedým tvarom. Pri takej hre, po každom ťahu, by nebolo treba robiť úplne všetko od začiatku, ale by sa zanalyzovali len tie tvary, ktoré by to teoreticky mohlo ovplyvniť a v pamäti by sa stále udržovali všetky tvary - aj zo šedých aj z bielych políčok. Namiesto termínu tvar je asi lepšie používať termín (spojitá) oblasť. |
||
| Witiko Profil |
#13 · Zasláno: 14. 10. 2010, 21:24:44 · Upravil/a: Witiko
_es:
„takýto tvar je aký?“ Uzavretý, funkcia by navrátila jeho výplň: ░░░░░░ ░░░░░░ ░░░░░░ ░░░█░░ ░░░░░░ ░░░░░░ ░░░░░░ „a žiadny, jeden alebo viac tvarov navyše - to sú tie políčka, čo majú zostať biele.“ „Zaradíš každý tvar-dutinu k nejakému šedému tvaru.“ Len neviem podľa čoho definujem príslušnosť "biele" spojitej oblasti k "šedej" spojité oblasti. Nejaké "biele" mi možno budú prebývať, ale, a možno som čo sa týka predstavivosti natvrdlý, neviem ako spoznám ktorý "biely" tvar sa nachádza v akom "šedivom" tvaru; vo scriptu samozrejme, očami to vidím. :D To bol základný problém, ktorému som čelil už od samého začiatku. |
||
| _es Profil |
#14 · Zasláno: 14. 10. 2010, 21:33:22 · Upravil/a: _es
Witiko:
„Len neviem podľa čoho definujem príslušnosť "biele" spojitej oblasti k "šedej spojité oblasti". Nejaké "biele" mi možno budú bývať, ale, a možno som čo sa týka predstavivosti natvrdlý, neviem ako spoznám ktorý "biely" tvar sa nachádza v akom "šedivom" tvaru.“ Biela oblasť musí susediť s šedou oblasťou v ktorom sa má nachádzať. Ďalej budeš zisťovať, s koľkým oblasťami susedí. Dutina samozrejme nemôže susediť s viacerými šedými oblasťami. „Uzavretý, funkcia by navrátila jeho výplň:“ Ale tam je dutina v tej oblasti len jedna bunka. (Aha, už si to opravil.) |
||
| Witiko Profil |
#15 · Zasláno: 14. 10. 2010, 22:08:04 · Upravil/a: Witiko
_es:
„Biela oblasť musí susediť s šedou oblasťou v ktorom sa má nachádzať. Ďalej budeš zisťovať, s koľkým oblasťami susedí. Dutina samozrejme nemôže susediť s viacerými šedými oblasťami.“ To sa mi nejako nezdá, ta biela oblasť okolo v tvojom príklade: ░░░░░░ ░░░█░░ ░░░█░░ ░░█░█░ ░░░█░░ ░░░█░░ ░░░░░░ Susedí so šedým tvarom uprostred, susedí len s jedným tvarom ale rovnako sa nejedná o jeho výplň. |
||
| _es Profil |
#16 · Zasláno: 14. 10. 2010, 22:14:38
Witiko:
„To sa mi nejako nezdá, ta biela oblasť okolo v tvojom príklade:“ No, pri len jednom tvare to platiť nemusí. Ak tam budú šedé oblasti dve, tak už to platiť bude. Treba lepšie premyslieť také hraničné prípady a ako identifikovať tie "zostávajúce" biele oblasti. |
||
| Witiko Profil |
#17 · Zasláno: 14. 10. 2010, 22:22:48 · Upravil/a: Witiko
_es:
Ok, vďaka, to znie logicky. Len to zdá sa bude celkom dosť rekurzívná funkcie - najprv vyhľadávania všetkých susediacich "šedých" bodov, potom u testovanie ku ktorej "sivé" oblasti daná "biela" oblasť patrí budem musieť prechádzať u každého "bieleho" bodu poľa všetkých "šedých" tvarov a testovať susedstva bunku po bunke. Inak tohle rieši aj 2b, kedy som chcel, aby sa tvary tvorili aj "skrze steny", tzn.: ░█░█░░ ░░░░░░ ░░█░░░ ░░░░░░ █░░░░█ ░░░░░░ ░█░░█░ -> █░░░░█ █░░░░█ ░░░░░░ ░░░░░░ ░░░░░░ ░░░░░░ ░░░░░░ Stačí testovať susedstvie aj cez okraje. Len možno bude potrebné úplne vyňať ako tvary tvary cez stenu neuzatvorené (viď. vrchný tvar, ktorý by na základe tebou opísanej logiky bol tiež "dutina vnútri tvaru"). A naopak cez stenu uzavreté tvary brát ako jeden tvar. U 2a (branie okraje poľa ako steny) by ani nemalo byť potrebné čokoľvek moc upravovať, to by malo na základe tebou predložený logiky fungovať "natívne". ░█░█░░ ░░█░░░ ░░█░░░ ░░░░░░ █░░░░█ ░░░░░░ ░█░░█░ -> █░░░░█ █░░░░█ ░░░░░░ ░░░░░░ ░░░░░░ ░░░░░░ ░░░░░░ |
||
|
Časová prodleva: 14 let
|
|||
0