Diskuze: Rozdělení množiny bodů

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 8:29

Potřeboval bych trochu poradit (spíše postrčit správným směrem) s tvorbou algoritmu na rozložení množiny bodů na podmnožiny splňující určitá pravidla. Potřebuji, aby výsledných množin bylo co nejméně a byly vzestupně seřazené podle počtu bodů. Měl bych nějaké nápady, ale nevím jak zajistit, aby bylo co nejméně podmnožin. A seřazení je ta nejlehčí část.

Pravidla pro podmnožiny:
Podmnožiny se budou zobrazovat na poli LED diod, kde budou svítit ty diody, pro které je pod proudem řádek i sloupec.
-> Podle toho musí vypadat i rozložení bodů v podmnožinách.
-> Podmnožiny se mohou v některých bodech překrývat (jeden bod smí být ve více podmnožinách)

Ukázka na malém poli diod(tečka je zhasnutá a křížek rozsvícená dioda)

Tohle nejde:
.....
...#.
.....
.#...
.....

Tohle jde:
.....
.#.#.
.....
.#.#.
.....

Na obrázku je ukázka rozkladu tří malých obrázků.

Editováno 2.11.2013 8:30

Odpovědět

2.11.2013 8:29

Kolik jazyků umíš, tolikrát jsi programátor.

Panda38

Tvůrce

Panda38:2.11.2013 9:30

Nebyl by i trochu praktičtější popis, ze kterého by byla myšlenka pochopitelnější? :-)

Předpokládám - to se střídají červená a zelená (ne žlutá) LED, ne? Podle toho příkladu by výchozí barevný obrázek měl 7x9 bodů, červených LED 3x5 a zelených 4x4. Jas každé LED se vypočte z obrázku z bodů v matici např. 3x3 rozmístěných kolem místa souřadnice LED. Největší váhu má barva v místě LED, sousedící menší a uhlopříčné ještě menší (vychází se ze stejné barevné složky). Vzhledem k tomu že chybí modrá barva, započítává se s malým podílem i modrá složka - stačí když ostatní LED budou místo modré trochu svítit a mozek si modrou domyslí ze zkušeností (vidí modrou oblohu i když displej modrou vůbec nemá). Kvůli rychlosti je dobře aby se namísto dělení použila celočíselná rotace, na to je dobré zohlednit váhové koeficienty. Např.:

R11 = (r11*8 + (r01+r10+r21+r12)*4 + (r00+r20+r02+r22) + b11*4) >> 5

Není-li četnost LED stejná (např. se používají body 2xzelená, 1xčervená a 1xmodrá), pak se úměrně tomu pro četnější LED použije menší přepočtová matice (nemusí to být čtverec).

Editováno 2.11.2013 9:33

Nahoru Odpovědět

2.11.2013 9:30

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 9:56

Barvy byly na obrázku jen pro znázornění, všechny diody mám červené a napojené na obvod s programovatelnou pamětí. Jde o to, že složitější obrázky nelze zobrazit celé, musí tam rychle problikávat ty podmnožiny (proto jich musí být co nejméně). Které diody mají svítit je vidět jen na prvním obrázku (bílá svítí, černá ne). Jde o to, že u většího počtu "obrázků" je docela složité je rozložit ručně (zvášť když jsou velké)

Nahoru Odpovědět

2.11.2013 9:56

Kolik jazyků umíš, tolikrát jsi programátor.

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 9:56

Double post.

Editováno 2.11.2013 9:57

Nahoru Odpovědět

2.11.2013 9:56

Kolik jazyků umíš, tolikrát jsi programátor.

Panda38

Tvůrce

Panda38:2.11.2013 15:56

Tak snad někdo odpoví kdo pochopil, já jaksi pointu problému nepochopil. (přemapovat obraz s přeskakováním pozic by nebyl problém, to asi nebylo předmětem dotazu)

Nahoru Odpovědět

2.11.2013 15:56

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 16:07

Na jednoduchém poli LED diod lze ovládat pouze sloupce a řádky. Tím pádem nelze zobrazit složitější obrázky, písmena... Já potřebuji tyhle obrázky rozložit na části, které zobrazit jdou.

Nahoru Odpovědět

2.11.2013 16:07

Kolik jazyků umíš, tolikrát jsi programátor.

Jan Vargovský

Tvůrce

Jan Vargovský:2.11.2013 16:22

Takže můžeš rozsvítit vždycky jen diody ve sloupci / řádku ?

EDIT: jo aha, napsal si to post předemnou. No tak pak si jen projedeš první v řádcích a zapamatuješ si souřadnice. To samé uděláš klidně i pro sloupce, porovnáš co je lepší(rychlejší ?) pro zobrazení a to použiješ.

Editováno 2.11.2013 16:25

Nahoru Odpovědět

2.11.2013 16:22

Jan Vargovský

Tvůrce

Jan Vargovský:2.11.2013 16:27

Už jsem nestihl edit ... Ale pak nechápu jak můžeš zobrazit tu čtverečkovou síť v posledním obrázku.

Nahoru Odpovědět

2.11.2013 16:27

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 17:36

Poslední obrázek se rozdělí na dvě části. Když zapneš každý druhý řádek a každý druhý sloupec dopadne to takhle:

0 1 0 1 0 1
1 . # . # . #
0 . . . . . .
1 . # . # . #
0 . . . . . .

1. # . # . #

Nahoru Odpovědět

2.11.2013 17:36

Kolik jazyků umíš, tolikrát jsi programátor.

Panda38

Tvůrce

Panda38:2.11.2013 17:42

Nemáš doufám na mysli multiplex.

Nahoru Odpovědět

2.11.2013 17:42

Panda38

Tvůrce

Panda38:2.11.2013 17:51

... mám obavu že máš. To se takhle ale neřeší, nic se neskupinkuje, jen se jede po řádcích nebo sloupcích v pravidelných časových krocích a rozsvěcují se příslušné LED.

Nahoru Odpovědět

2.11.2013 17:51

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 18:02

Nevím co myslíš tím multiplexem.

Nahoru Odpovědět

2.11.2013 18:02

Kolik jazyků umíš, tolikrát jsi programátor.

Neaktivní uživatel

Člen

Neaktivní uživatel:2.11.2013 18:04

že by http://cs.wikipedia.org/…C3%A1n%C3%AD ??

Nahoru Odpovědět

2.11.2013 18:04

Neaktivní uživatelský účet

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 18:37

https://dl.dropboxusercontent.com/…367/LED.html Tady je ukázka vytvoření písmene A na poli diod o rozměrech 3x5. První dva obrázky ukazují střídající se části "obrázku" a třetí ukazuje vzhled při vysoké rychlosti blikání.

Nahoru Odpovědět

2.11.2013 18:37

Kolik jazyků umíš, tolikrát jsi programátor.

jargry

Člen

jargry:2.11.2013 19:33

Myslím si, že se jedná o sloupcový multiplexer. Jak psal Panda38 nic se neskupinkuje, pošle se signál postupně po jednom na všechny sloupce + odpovídající řádky. Na tomto principu fungovala jehličková tiskárna.

Nahoru Odpovědět

2.11.2013 19:33

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 20:02

Já potřebuju těch částí co nejméně, u toho pole diod mám malou paměť, takže dávat to tam po jednotlivých bodech/čarách nemůžu.

Nahoru Odpovědět

2.11.2013 20:02

Kolik jazyků umíš, tolikrát jsi programátor.

Panda38

Tvůrce

Panda38:2.11.2013 20:05

Multiplexovaný displej používá matici LED organizovaných do řádků a sloupců. Přepíná se vždy v každém okamžiku jen jeden sloupec
(nebo řádek) a v něm se zapnou příslušné LEDky = multiplex (tedy cyklické přepínání sloupců). V tom případě je realizace jednoduchá, nic není třeba skupinkovat. Skupinkování by Ti nic nepřineslo, naopak je velmi nepraktické z hlediska svítivosti LED (tj. středního proudu jimi tekoucího). Časování by bylo závislé na počtu skupin - v jedné chvíli by trvale svítily všechny LED (např. kdyby se rozsvítilo vše, tj. jedna skupina), jindy bys přepínal postupně všechny sloupce (šikmá čára, která by nešla skupinkovat) a to by se projevilo na různé svítivosti. LEDky jsou napájené určitým proudem - a ten proud bývá stanoven pro multiplexovaný režim, kdy např. pro matici 5x7 svítí každá LED jen 1/7 času (proto je proud 7x větší než by byl ve statickém režimu). To znamená - že při skupinkování by v jedné chvíli displej svítil příliš jasně a v jiné téměř vůbec. Dokonce při malém počtu skupin bys LEDky odpálil příliš velkým proudem. Proto zapomeň na skupinkování a přepínej cyklicky po jednom.

Nahoru Odpovědět

2.11.2013 20:05

Panda38

Tvůrce

Panda38:2.11.2013 20:09

Malá paměť nemůže být problém. Jestli nepoužíváš grafiku tak nepotřebuješ paměť pro grafický displej. Přerušení od časovače v každém kroku vezme znak z textové paměti, podívá se do ROM paměti generátoru znaků a odtud vezme jeden sloupeček LED diod. Při příštím přerušení vezme další sloupeček. Nepotřebuje žádnou zvláštní RAM.

Nahoru Odpovědět

2.11.2013 20:09

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 20:14

Změny ve svítivosti jsou patrné jen u velkých počtů diod. A spálit se nemohou díky ochranným odporům. Do paměti, kterou v tom obvodu mám nastavuji jednotlivé kroky (při zobrazování po jednom je to krok za každou diodu). S pouhými 2 čítači toho víc nezvládnu a do paměti se vejde jen určitý počet kroků (myslím že 256 * 8 "animací").

Editováno 2.11.2013 20:16

Nahoru Odpovědět

2.11.2013 20:14

Kolik jazyků umíš, tolikrát jsi programátor.

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:2.11.2013 20:36

A je to jedinná paměť v obvodu.

Nahoru Odpovědět

2.11.2013 20:36

Kolik jazyků umíš, tolikrát jsi programátor.

Panda38

Tvůrce

Panda38:2.11.2013 21:32

Dost nešťastné řešení.

Tak třeba takto (jistě to není moc optimální): Nejdříve najít při jaké kombinaci řádků a sloupců se obslouží co nejvíce rozsvícených LED - projít všechny kombinace řádků (tj. tady 512) a pro každou kombinaci vyhledat sloupce které splňují rozsvícení (tj. data_sloupce_obrázku AND řádky == řádky), odtud spočítat počet LED a najít tak nejlepší kombinaci. Obsloužené LED z obrazu odmazat a hledat další kombinaci s největším počtem LED, atd. až se najdou všechny kroky.

Nahoru Odpovědět

2.11.2013 21:32

Zdeněk Pavlátka

Tvůrce

Zdeněk Pavlátka:3.11.2013 7:49

Jenom mi prosím poraď, jak projít všechny kombinace(jestli to jde i jinak než pomocí cyklu)

Nahoru Odpovědět

3.11.2013 7:49

Kolik jazyků umíš, tolikrát jsi programátor.

Panda38

Tvůrce

Panda38:3.11.2013 10:23

Nejde jinak než cyklem. Něco jako:

#define ROWS 9 // pocet linek
#define COLS (7*8) // pocet sloupecku - napr. 8 pozic po 7 sloupeccich
int radky,sloupec, lednum, led0, ledbest, i;
unsigned char sloupce[COLS/8]; // stradac masky sloupcu
unsigned char sloupce_best[COLS/8]; // nejlepsi maska sloupcu

ledbest=-1;

// cyklus pres vsechny kombinace radku
for (radky=0; radky<(1<<ROWS); radky++)
{
  // spocteni bitu "1" v masce radku
  led0=0;
  for (i=0; i<ROWS; i++) if (radky & (1<<i)) led0++;

  // vymazani stradace sloupecku
  memset(sloupce, 0, COLS/8);
  lednum=0;

  // cyklus pres sloupce
  for (sloupec=0; sloupec<COLS; sloupec++)
  {
    // sloupecek vyhovuje, pridani k stradaci masky
    if ((pic[sloupec] & radky) == radky)
    {
      sloupce[sloupec/8] |= (1 << (sloupec & 7));
      lednum += led0;
    }
  }

  // nalezena lepsi kombinace
  if (lednum > ledbest)
  {
    ledbest = lednum;
    memcpy(sloupce_best; sloupce, COLS/8);
  }
}

// pokud je ledbest=0, konec cyklu, jinak pridani do seznamu animaci, odecteni LED od obrazku a hledani dalsi kombinace

Nahoru Odpovědět

3.11.2013 10:23

Nejčastěji vyhledáváné

Diskuze: Rozdělení množiny bodů