Po drátě 4: Řešení úlohy č. 12

Jak praví zadání, klasický způsob ukládání obrázku po řádcích je nuda. Existují zajímavější způsoby, například křivky pokrývající plochu. Taková křivka prochází bez přerušení každým bodem roviny. To je v počítačové grafice trošku jednodušší, protože máme konečný počet bodů, takže můžeme pokrýt plochu třeba křivkou tam-zpátky-tam-zpátky. Ale proč nepoužít něco obecnějšího.

Hilbertova křivka je jedna z nejjednodušších křivek pokrývajících plochu. Má nějaký základní tvar (písmeno U) a způsob, jak tenhle základní tvar rozdělit pomocí menších základních tvarů. V obrázku je nakreslena křivka po šesti krocích. K vyřešení je třeba křivku "dokončit" až na úroveň pixelů a ty pak podle té křivky uložit do nového obrázku tradičně zleva doprava, aby to nějaký prohlížeč dokázal zobrazit.

Výsledek vypadá takhle:

Vzorové řešení například takhle v pythonu (modul hilbert, který umí pracovat s Hilbertovou křivkou libovolné dimenze, ke stažení odsud):

from PIL import Image
import hilbert

i = Image.open('/tmp/hilbert.png')
o = Image.new('RGB', (512,512))

for x in xrange(512):
   for y in xrange(512):
       p = hilbert.int_to_Hilbert(x + 512 * y,2)
       px = i.getpixel((p[1], p[0]))
       o.putpixel((x,y), px)

o.save('/tmp/out.png')

Ostatně, i když nemáte po ruce ten správný modul, Hilbertovu křivku vygenerujete snadno:

int x=0, y=0, dx=0, dy=1;
#define R(r) do { int dx0=dx, dy0=dy; dx=-(r)*dy0; dy=(r)*dx0; } while(0)

void step(void)
{
  // Zpracuje pixel o souřadnicích (x,y)
  x += dx;
  y += dy;
}

void hilbert(int deg, int rot)
{
  if (!deg--)
    return;
  R(-rot);
  hilbert(deg, -rot);
  step();
  R(rot);
  hilbert(deg, rot);
  step();
  hilbert(deg, rot);
  R(rot);
  step();
  hilbert(deg, -rot);
  R(-rot);
}

Komentář

Původně úloha vypadala zcela jinak. Dostali byste pouze zcela nesmyslný obrázek jménem "hilbert.pcx" s komentářem "better compression through different scanline". Museli byste pak přijít na to, že scanline je Hilbertova křivka, a po převedení obrázku do "viditelné" podoby byste zjistili, že obrázek s Hilbertem je opravdu asi o 300 bajtů menší. (Například u GIFu už je komprese horší. Zřejmě jsou dobré důvody, proč se Hilbertova křivka jako scanline nepoužívá.)

Velmi záhy jsme si řekli, že to by bylo opravdu příliš drsné, a tak vzniklo tohle.

Úlohu vyrobil matějčík, ukázková řešení dodali Michal Čihař a Martin Mareš.