Pāriet uz saturu

Hilberta līkne

Vikipēdijas lapa
pirmie 8 soļi Hilberta līknes izveidei
Pirmās kārtas Hilberta līkne
Pirmās un otrās kārtas Hilberta līknes
Pirmās līdz trešās kārtas Hilberta līknes
Hilberta līkne trīs dimensijās

Hilberta līkne (zināma arī kā Hilberta telpu piepildošā līkne) ir nepārtraukta fraktāļu plakni piepildoša līkne, kuru pirmoreiz aprakstīja vācu matemātiķis Dāvids Hilberts 1891. gadā.[1]

Tā kā tā ir plakni piepildoša, tās Hausdorfa dimensija (pie robežas ) ir .

Eiklīda attālums ir , t.i. tas aug eksponenciāli ar .

Vairākdimensiju datubāzēs ir ietikts izmantot Hilberta kārtu z-kārtas līknes vietā tās labāko lokalitātes saglabāšanas īpašību dēļ. Databāzu algoritmi ar Hilberta kārtību tiek pielietoti [2] [3]

Attēlojums Lindemaijera sistēmā

[labot šo sadaļu | labot pirmkodu]

Lindemaijera sistēmā Hilberta līkni var izteikt kā pārrakstīšanas sistēmu.

Alfabēts : L, R
Konstantes : F, +, −
Aksioma : L
Produkciju likumi:
L → +RF−LFL−FR+
R → −LF+RFR+FL−

Kur F nozīmē "zīmēt uz priekšu", + nozīmē "pagriezties par 90° pa kreisi" un - - "pagriezties par 90° pa labi" ( bruņurupuču grafika).

A. R. Butzs [4] ir izveidojis algoritmu vairākdimensiju Hilberta līknes veidošanai. libHilbert[novecojusi saite] ir C++ bibliotēka, kas izmanto Butza algoritmu vairākām dimensijām.

Šī Java sīklietotne zīmē Hilberta līkni, rekursīvi izsaucot četras metodes:

import java.awt.*;
import java.applet.*;

public class HilbertCurve extends Applet {
    private SimpleGraphics sg=null;
    private int dist0=512, dist=dist0;

    public void init() {
        dist0 = 512;
        resize ( dist0, dist0 );
        sg = new SimpleGraphics(getGraphics());
    }

    public void paint(Graphics g) {
        int level=4;
        dist=dist0;
        for (int i=level;i>0;i--) dist /= 2;
        sg.goToXY ( dist/2, dist/2 );
        HilbertA(level); // start recursion
    }

    private void HilbertA (int level) {
        if (level > 0) {
            HilbertB(level-1);    sg.lineRel(0,dist);
            HilbertA(level-1);    sg.lineRel(dist,0);
            HilbertA(level-1);    sg.lineRel(0,-dist);
            HilbertC(level-1);
        }
    }

    private void HilbertB (int level) {
        if (level > 0) {
            HilbertA(level-1);    sg.lineRel(dist,0);
            HilbertB(level-1);    sg.lineRel(0,dist);
            HilbertB(level-1);    sg.lineRel(-dist,0);
            HilbertD(level-1);
        }
    }

    private void HilbertC (int level) {
        if (level > 0) {
            HilbertD(level-1);    sg.lineRel(-dist,0);
            HilbertC(level-1);    sg.lineRel(0,-dist);
            HilbertC(level-1);    sg.lineRel(dist,0);
            HilbertA(level-1);
        }
    }

    private void HilbertD (int level) {
        if (level > 0) {
            HilbertC(level-1);    sg.lineRel(0,-dist);
            HilbertD(level-1);    sg.lineRel(-dist,0);
            HilbertD(level-1);    sg.lineRel(0,dist);
            HilbertB(level-1);
        }
    }
}

class SimpleGraphics {
    private Graphics g = null;
    private int x = 0, y = 0;    

    public SimpleGraphics(Graphics g) { this.g = g; }
    public void goToXY(int x, int y) { this.x = x;   this.y = y; }

    public void lineRel(int deltaX, int deltaY) {
        g.drawLine ( x, y, x+deltaX, y+deltaY );
        x += deltaX;    y += deltaY;
    }
}

Vēl viena versija, kas realizē attēlojumu Lindenmaijera sistēmā. Kods rakstīts Tuga Turtle valodā.

  def f
    walk 10
  end
  def p
    turn 90
  end
  def m
    turn -90
  end
  def l(n)
    return if n==0
    p; r(n-1); f; m; l(n-1); f; l(n-1); m; f; r(n-1); p
  end
  def r(n)
    return if n==0
    m; l(n-1); f; p; r(n-1); f; r(n-1); p; f; l(n-1); m
  end
  
  l(6)
  1. D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459—460.
  2. J. Lawder, P. King: querying multidimensional data indexed using the Hilbert space filling curve. SIGMOD Record, 30(1); 19-24, 2001.
  3. H. Tropf: US patent application 2004/0177065, an improved description of the European patent EP 03003692.5; it includes also an algorithm for calculating Hilbert values in n dimensions.
  4. A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.