Hilberta līkne

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt
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  n \rightarrow \infty ) ir  2 .

Eiklīda attālums  H_n ir  2^n - {1 \over 2^n} , t.i. tas aug eksponenciāli ar  n .

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ā[izmainīt š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).

Datorprogramma[izmainīt šo sadaļu | labot pirmkodu]

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

Šis 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ēlijumu 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)

Atsauces[izmainīt šo sadaļu | labot pirmkodu]

  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.

Skatīt arī[izmainīt šo sadaļu | labot pirmkodu]