Καμπύλη Χίλμπερτ

Η καμπύλη Χίλμπερτ (επίσης γνωστή ως καμπύλη πλήρωσης χώρου Χίλμπερτ) είναι μια συνεχής κλασματική καμπύλη πλήρωσης χώρου που περιγράφηκε για πρώτη φορά από τον Γερμανό μαθηματικό Ντάβιντ Χίλμπερτ το 1891,D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460. ως παραλλαγή των καμπυλών πλήρωσης χώρου του Πεάνο που ανακαλύφθηκαν από τον Τζουζέπε Πεάνο το 1890G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160..

Επειδή είναι χωροπληρωτική, η διάσταση Χάουσντορφ της είναι 2 (ακριβώς, η εικόνα της είναι το μοναδιαίο τετράγωνο, του οποίου η διάσταση είναι 2 σε οποιονδήποτε ορισμό της διάστασης- η γραφική της παράσταση είναι ένα συμπαγές σύνολο ομοιομορφικό με το κλειστό μοναδιαίο διάστημα, με διάσταση Χάουσντορφ 2).

Η καμπύλη Χίλμπερτ κατασκευάζεται ως όριο γραμμικών καμπυλών. Το μήκος της thς καμπύλης είναι , δηλαδή το μήκος αυξάνεται εκθετικά με το , παρόλο που κάθε καμπύλη περιέχεται σε ένα τετράγωνο με εμβαδόν .

Εικόνες

Εφαρμογές και αλγόριθμοι χαρτογράφησης
Τόσο η πραγματική καμπύλη Χίλμπερτ όσο και οι διακριτές προσεγγίσεις της είναι χρήσιμες επειδή δίνουν μια αντιστοιχία μεταξύ του 1D χώρου και του 2D χώρου που διατηρεί αρκετά καλά την τοπικότητα., πράγμα που σημαίνει ότι δύο σημεία δεδομένων που βρίσκονται κοντά το ένα στο άλλο στον μονοδιάστατο χώρο βρίσκονται επίσης κοντά το ένα στο άλλο μετά την αναδίπλωση. Το αντίστροφο δεν ισχύει πάντα.

Λόγω αυτής της ιδιότητας τοπικότητας, η καμπύλη Χίλμπερτ χρησιμοποιείται ευρέως στην πληροφορική. Για παράδειγμα, το εύρος των διευθύνσεων IP που χρησιμοποιούνται από υπολογιστές μπορεί να αναπαρασταθεί σε μια εικόνα χρησιμοποιώντας την καμπύλη Χίλμπερτ. Ο κώδικας που παράγει την εικόνα πρέπει να μεταβεί από 2D σε 1D για να βρει το χρώμα κάθε εικονοστοιχείου και η καμπύλη Χίλμπερτ χρησιμοποιείται μερικές φορές επειδή διατηρεί τις διευθύνσεις IP κοντά μεταξύ τους στην εικόνα. Η ιδιότητα της τοπικότητας της καμπύλης Χίλμπερτ έχει επίσης χρησιμοποιηθεί για τον σχεδιασμό αλγορίθμων για την εξερεύνηση περιοχών από κινητά ρομπότ.

Σε έναν αλγόριθμο που ονομάζεται Riemersma dithering, η φωτογραφία σε κλίμακα του γκρι μπορεί να μετατραπεί σε ασπρόμαυρη εικόνα με χρήση κατωφλίου, με το ποσό που απομένει από κάθε εικονοστοιχείο να προστίθεται στο επόμενο εικονοστοιχείο κατά μήκος της καμπύλης Χίλμπερτ. Ο κώδικας για να γίνει αυτό θα αντιστοιχούσε από 1D σε 2D, και η καμπύλη Χίλμπερτ χρησιμοποιείται μερικές φορές επειδή δεν δημιουργεί τα ενοχλητικά μοτίβα που θα ήταν ορατά στο μάτι αν η σειρά ήταν απλά από αριστερά προς τα δεξιά σε κάθε σειρά εικονοστοιχείων. οι καμπύλες Χίλμπερτ σε υψηλότερες διαστάσεις αποτελούν μια περίπτωση γενίκευσης των κωδίκων του γκρι (Gray), και χρησιμοποιούνται μερικές φορές για παρόμοιους σκοπούς, για παρόμοιους λόγους. Για πολυδιάστατες βάσεις δεδομένων, έχει προταθεί να χρησιμοποιείται η τάξη Χίλμπερτ αντί της τάξης Ζ, επειδή έχει καλύτερη συμπεριφορά διατήρησης της τοπικότητας. Για παράδειγμα, οι καμπύλες Χίλμπερτ έχουν χρησιμοποιηθεί για τη συμπίεση και επιτάχυνση των ευρετηρίων R-treeI. Kamel, C. Faloutsos, Hilbert R-tree: An improved R-tree using fractals, in: Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994, pp. 500–509. (βλέπε δέντρο Χίλμπερτ R-tree). Έχουν επίσης χρησιμοποιηθεί για να βοηθήσουν στη συμπίεση αποθηκών δεδομένων.

Λαμβάνοντας υπόψιν την ποικιλομορφία των εφαρμογών, είναι χρήσιμο να υπάρχουν αλγόριθμοι που μπορούν να δημιουργήσουν αντιστοιχίες και προς τις δύο κατευθύνσεις. Σε πολλές γλώσσες, αυτοί οι αλγόριθμοι είναι πιο αποδοτικοί αν υλοποιούνται με χρήση επανάληψης αντί για αναδρομή. Ο ακόλουθος κώδικας C εκτελεί αντιστοίχιση δύο κατευθύνσεων, χρησιμοποιώντας επανάληψη και πράξεις bit αντί για αναδρομή. Υποθέτει ένα τετράγωνο χωρισμένο σε n επί n  κελιά, για n  μια δύναμη του 2, με ακέραιες συντεταγμένες, με (0,0) στην κάτω αριστερή γωνία, (n − 1, n − 1) στην πάνω δεξιά γωνία, και μια απόσταση d που ξεκινά από το 0 στην κάτω αριστερή γωνία και φτάνει μέχρι το  στην κάτω δεξιά γωνία. Αυτό είναι διαφορετικό από το κινούμενο σχέδιο που παρουσιάστηκε παραπάνω, όπου η καμπύλη ξεκινάει στην επάνω αριστερή γωνία και καταλήγει στην επάνω δεξιά γωνία.

//convert (x,y) to d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s=n/2; s>0; s/=2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(n, &x, &y, rx, ry);
    }
    return d;
}

//convert d to (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s=1; s<n; s*=2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

//rotate/flip a quadrant appropriately
void rot(int n, int *x, int *y, int rx, int ry) {
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }

        //Swap x and y
        int t  = *x;
        *x = *y;
        *y = t;
    }
}

Αυτές χρησιμοποιούν τις συμβάσεις της C: το σύμβολο & είναι ένα bitwise AND, το σύμβολο ^ είναι ένα bitwise XOR, το += είναι ο τελεστής πρόσθεσης/ανάθεσης (x += y είναι ισοδύναμο με x = x + y) και το /= είναι ο τελεστής διαίρεσης/ανάθεσης. Ο χειρισμός των booleans στη C σημαίνει ότι στο xy2d, η μεταβλητή rx τίθεται σε 0 ή 1 για να ταιριάζει με το bit s του x, και ομοίως για το ry.

Η συνάρτηση xy2d λειτουργεί από πάνω προς τα κάτω, ξεκινώντας με τα πιο σημαντικά bits των x και y και χτίζοντας πρώτα τα πιο σημαντικά bits του d. Η συνάρτηση d2xy λειτουργεί με την αντίθετη σειρά, ξεκινώντας με τα λιγότερο σημαντικά bits του d και αναπτύσσοντας τα x και y ξεκινώντας από τα λιγότερο σημαντικά bits. Και οι δύο συναρτήσεις χρησιμοποιούν τη συνάρτηση rotation για την κατάλληλη περιστροφή και αναστροφή του συστήματος συντεταγμένων (x,y).

Οι δύο αλγόριθμοι χαρτογράφησης λειτουργούν με παρόμοιο τρόπο.  Ολόκληρο το τετράγωνο θεωρείται ότι αποτελείται από 4 περιοχές, διατεταγμένες 2 προς 2. Κάθε περιοχή αποτελείται από 4 μικρότερες περιοχές, και ούτω καθεξής, για έναν αριθμό επιπέδων.  Στο επίπεδο s, κάθε περιοχή αποτελείται από s επί s κελιά.  Υπάρχει ένας μόνο βρόχος FOR που επαναλαμβάνει τα επίπεδα.  Σε κάθε επανάληψη, ένα ποσό προστίθεται στο d ή στα x και y, που καθορίζεται από το σε ποια από τις 4 περιοχές βρίσκεται στο τρέχον επίπεδο.  Η τρέχουσα περιοχή από τις 4 είναι (rx,ry), όπου rx και ry είναι το καθένα 0 ή 1.  Έτσι καταναλώνει 2 bits εισόδου, (είτε 2 από το d είτε από 1 το καθένα από τα x και y), και παράγει δύο bits εξόδου.  Καλεί επίσης τη συνάρτηση περιστροφής, έτσι ώστε τα (x,y) να είναι κατάλληλα για το επόμενο επίπεδο, στην επόμενη επανάληψη.  Για το xy2d, ξεκινάει από το ανώτερο επίπεδο ολόκληρου του τετραγώνου, και κατεβαίνει μέχρι το κατώτερο επίπεδο των μεμονωμένων κελιών.  Για το d2xy, ξεκινάει από το κατώτερο επίπεδο με τα κελιά, και εργάζεται προς τα πάνω για να συμπεριλάβει ολόκληρο το τετράγωνο.

Υπάρχει η δυνατότητα να υλοποιηθούν αποτελεσματικά οι καμπύλες Χίλμπερτ ακόμη και όταν ο χώρος δεδομένων δεν σχηματίζει τετράγωνο..Επιπλέον, υπάρχουν αρκετές πιθανές γενικεύσεις των καμπυλών Χίλμπερτ σε υψηλότερες διαστάσειςH. J. Haverkort, F. van Walderveen, Four-dimensional Hilbert curves for R-trees, in: Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments, 2009, pp. 63–73..

Αναπαράσταση ως σύστημα Λιντενμάγιερ
Αλφάβητο : A, B
Σταθερές : F + -
Αξίωμα : A
Κανόνες παραγωγής:
 A → +BF−AFA−FB+
 B → −AF+BFB+FA−

Εδώ, το "F" σημαίνει "σχεδίαση προς τα εμπρός", το "+" σημαίνει "στροφή αριστερά 90°", το "-" σημαίνει "στροφή δεξιά 90°" (βλ. γραφικά χελώνας) και τα "A" και "B" αγνοούνται κατά τη σχεδίαση.

Άλλες υλοποιήσεις
Το Graphics Gems IIVoorhies, Douglas: Space-Filling Curves and a Measure of Coherence, pp. 26–30, Graphics Gems II.  συζητά τη συνοχή των καμπυλών Χίλμπερτ και παρέχει υλοποίηση.

Η καμπύλη Χίλμπερτ χρησιμοποιείται συνήθως μεταξύ της απόδοσης εικόνων ή βίντεο. Κοινά προγράμματα όπως το Μπλέντερ και το Σινεμά 4D χρησιμοποιούν την καμπύλη Χίλμπερτ για την ανίχνευση των αντικειμένων και την απόδοση της σκηνής.

 Δείτε επίσης 
Καμπύλη Πεάνο
Καμπύλη πλήρωσης χώρου
Αναδρομή
Σύνολο Μάντελμπροτ
Σύνολο Julia
Οικοδομήσιμο Σύμπαν

Βιβλιογραφία 



Παραπομπές




Κατηγορία:Φράκταλ
Κατηγορία:Μαθηματική λογική
Κατηγορία:Καμπύλες