Mortonův rozklad

Mortonův rozklad dvourozměrné matice 8×8

Mortonův rozklad (Morton scan order, Z-order) je křivka, která udává lineární pořadí průchodu vícerozměrným prostorem. Jinými slovy mapuje vícerozměrný prostor do jednorozměrného. Poprvé ji v roce 1966 představil zaměstnanec kanadské IBM Guy M. Morton. Své užití má například při indexování vícerozměrných dat (pak je možné použít algoritmy pro indexování dat jednorozměrných) nebo při implementaci průchodu stromem koeficientů vzniklých vlnkovou transformací (viz algoritmus SPIHT). Algoritmy výpočtu této křivky využívají jejího rekurzivního charakteru.

Rekurzivní výpočet

void ezw_xy(int level, int x, int y, int n)
{
        if (0 == level) {
                echo(0, 0, n);
                return;
        }
 
        if (level > 1) {
                ezw_xy(level‐1, 2*(x  ), 2*(y  ), n);
                ezw_xy(level‐1, 2*(x+1), 2*(y  ), n);
                ezw_xy(level‐1, 2*(x  ), 2*(y+1), n);
                ezw_xy(level‐1, 2*(x+1), 2*(y+1), n);
                return;
        }
 
        echo(x  , y  , n);
        echo(x+1, y  , n);
        echo(x  , y+1, n);
        echo(x+1, y+1, n);
}
 
void ezw(int level)
{
        ezw_xy(level, 0, 0, 1<<level);
}
 
// pro matici 8×8
ezw(log2(8));

Související články

• Hilbertova křivka