Hilberta līkne
![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/4/46/Hilbert_curve.gif/220px-Hilbert_curve.gif)
![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Hilbert-Curve-1.png/220px-Hilbert-Curve-1.png)
![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/9/98/Hilbert-Curve-2.png/220px-Hilbert-Curve-2.png)
![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Hilbert-Curve-3.png/220px-Hilbert-Curve-3.png)
![](http://178.128.105.246/content-http-upload.wikimedia.org/wikipedia/commons/thumb/6/67/Hilbert512.gif/220px-Hilbert512.gif)
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).
Datorprogramma
[labot šo sadaļu | labot pirmkodu]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)
Atsauces
[labot šo sadaļu | labot pirmkodu]- ↑ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459—460.
- ↑ J. Lawder, P. King: querying multidimensional data indexed using the Hilbert space filling curve. SIGMOD Record, 30(1); 19-24, 2001.
- ↑ 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.
- ↑ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.
![]() |
Vikikrātuvē par šo tēmu ir pieejami multivides faili. Skatīt: Hilbert curve |