Καμπύλη Σιερπίνσκι

Δείτε επίσης το Χαλί του Σιερπίνσκι

Η καμπύλη Σιεπίνσκι είναι μια αναδρομικά ορισμένη ακολουθία συνεχόμενων κλειστών επίπεδων μορφοκλασματικών καμπυλών που ανακάλυψε ο Βάτσλαβ Σιεπίνσκι^[1], οι οποίες στο όριο $n\to \infty$ γεμίζουν πλήρως το μοναδιαίο τετράγωνο: κατά συνέπεια, η οριακή καμπύλη τους, που ονομάζεται επίσης καμπύλη Σιεπίνσκι, αποτελεί παράδειγμα καμπύλης που γεμίζει τον χώρο.

Επειδή η καμπύλη Σερπιένσκι είναι χωροταξική, η Διάσταση Χάουσντορφ (στο όριο $n\to \infty$ ) είναι $2$ .
Το ευκλείδειο μήκος της $n$ ^th καμπύλης επανάληψης $S_{n}$ είναι

l_{n}={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \over 2^{n}},

Αυτό σημαίνει ότι αυξάνεται εκθετικά με το $n$ πέρα από κάθε όριο, ενώ το όριο για $n\to \infty$ του εμβαδού που περικλείεται από το $S_{n}$ είναι $5/12\,$ αυτό του τετραγώνου (στην ευκλείδεια μετρική).

Καμπύλη Σιερπίνσκι ("τετράγωνη νιφάδα χιονιού του Σιερπίνσκι")^[2]) πρώτης τάξεως

Χρήσεις της καμπύλης[Επεξεργασία | επεξεργασία κώδικα]

Η καμπύλη Σιερπίνσκι είναι χρήσιμη σε διάφορες πρακτικές εφαρμογές, επειδή είναι πιο συμμετρική από άλλες καμπύλες πλήρωσης χώρου που έχουν μελετηθεί ευρύτερα. Παραδείγματος χάριν, έχει χρησιμοποιείται ως βάση για την ταχεία κατασκευή μιας προσεγγιστικής λύσης του προβλήματος του πλανόδιου πωλητή (το οποίο ζητά τη συντομότερη ακολουθία ενός δεδομένου συνόλου σημείων): Η ευρετική μέθοδος είναι απλώς να επισκεφθούμε τα σημεία με την ίδια σειρά που εμφανίζονται στην καμπύλη Σερπίνσκι^[4] : Στη συνέχεια, πρέπει να ταξινομηθούν οι τιμές. Η ιδέα αυτή χρησιμοποιήθηκε για την κατασκευή συστημάτων δρομολόγησης για εμπορικά οχήματα που βασίζονται μόνο σε αρχεία καρτών Rolodex^[5].

Μια καμπύλη πλήρωσης χώρου είναι ένας συνεχής χάρτης του μοναδιαίου διαστήματος σε ένα μοναδιαίο τετράγωνο και έτσι μια (ψευδο)αντίστροφη απεικονίζει το μοναδιαίο τετράγωνο στο μοναδιαίο διάστημα. Ένας τρόπος κατασκευής μιας ψευδοαντίστροφης είναι ο εξής. Η κάτω αριστερή γωνία (0, 0) του μοναδιαίου τετραγώνου αντιστοιχεί στο 0,0 (και 1,0). Η πάνω αριστερή γωνία (0, 1) πρέπει τότε να αντιστοιχεί στο 0,25, η πάνω δεξιά γωνία (1, 1) στο 0,50 και η κάτω δεξιά γωνία (1, 0) στο 0,75. Ο αντίστροφος χάρτης των εσωτερικών σημείων υπολογίζεται εκμεταλλευόμενος την αναδρομική δομή της καμπύλης.

Ακολουθεί μια συνάρτηση κωδικοποιημένη σε Java που υπολογίζει τη σχετική θέση οποιουδήποτε σημείου της καμπύλης Σιερπίνσκι (δηλαδή μια ψευδο-αντίστροφη τιμή). Δέχεται ως είσοδο τις συντεταγμένες του σημείου (x,y) που πρόκειται να αντιστραφεί, και τις γωνίες ενός περιβάλλoντος ορθού ισοσκελούς τριγώνου (ax, ay), (bx, by), και (cx, cy). (Το μοναδιαίο τετράγωνο είναι η ένωση δύο τέτοιων τριγώνων.) Οι υπόλοιπες παράμετροι καθορίζουν το επίπεδο ακρίβειας με το οποίο πρέπει να υπολογιστεί η αντιστροφή.

    static long sierp_pt2code( double ax, double ay, double bx, double by, double cx, double cy,
        int currentLevel, int maxLevel, long code, double x, double y ) 
    {
        if (currentLevel <= maxLevel) {
            currentLevel++;
            if ((sqr(x-ax) + sqr(y-ay)) < (sqr(x-cx) + sqr(y-cy))) {
                code = sierp_pt2code( ax, ay, (ax+cx)/2.0, (ay+cy)/2.0, bx, by,
                    currentLevel, maxLevel, 2 * code + 0, x, y );
            }
            else {
                code = sierp_pt2code( bx, by, (ax+cx)/2.0, (ay+cy)/2.0, cx, cy,
                    currentLevel, maxLevel, 2 * code + 1, x, y );
            }
        }
        return code;    
    }

Απεικόνιση του συστήματος Λιντενμάγιερ[Επεξεργασία | επεξεργασία κώδικα]

Η καμπύλη Σιερπίνσκι μπορεί να εκφραστεί με ένα σύστημα επανεγγραφής Σύστημα-L).

Αλφάβητο: F, G, X

Σταθερές: F, G, +, &minus,

Αξίωμα: F−−XF−−F−−XF

'Κανόνες παραγωγής:

X → XF+G+XF−−F−−XF+G+X

Γωνία: 45

Εδώ, τόσο το F όσο και το G σημαίνουν "τραβήξτε προς τα εμπρός", το + σημαίνει "στρίψτε αριστερά κατά 45°", και το − σημαίνει "στρίψτε δεξιά κατά 45°" (βλέπε γραφικά χελώνας^[6]). Η καμπύλη συνήθως σχεδιάζεται με διαφορετικά μήκη για τα F και G.

Η τετραγωνική καμπύλη Σιερπίνσκι μπορεί να εκφραστεί με παρόμοιο τρόπο:

Αλφάβητο: F, X

Σταθερές: F, +, &minus,

Αξίωμα: F+XF+F+XF

'Κανόνες παραγωγής:

X → XF−F+F−XF+F+XF−F+F−X

Γωνία: 90

Καμπύλη βέλους[Επεξεργασία | επεξεργασία κώδικα]

Η καμπύλη βέλους του Σιερπίνσκι σχεδιάζει ένα ισόπλευρο τρίγωνο με τριγωνικές οπές σε ίσα διαστήματα. Μπορεί να περιγραφεί με δύο κανόνες παραγωγής υποκατάστασης: (A → B-A-B) και (B → A+B+A). Τα Α και Β επαναλαμβάνονται και στο κάτω μέρος κάνουν το ίδιο πράγμα - σχεδιάζουν μια γραμμή. Συν και μείον (+ και -) σημαίνουν στροφή κατά 60 μοίρες είτε αριστερά είτε δεξιά. Το καταληκτικό σημείο της καμπύλης Σιερπίνσκι με βέλη είναι πάντα το ίδιο με την προϋπόθεση ότι επαναλαμβάνετε έναν άρτιο αριθμό φορών και μειώνετε το μήκος της γραμμής στο μισό σε κάθε επανάληψη. Εάν ανατρέξετε σε περιττό βάθος (η σειρά είναι περιττή) τότε καταλήγετε να στρίψετε 60 μοίρες, σε διαφορετικό σημείο του τριγώνου.

Μια εναλλακτική στένωση δίνεται στο άρθρο για την καμπύλη Ντε Ραμ: χρησιμοποιείται η ίδια τεχνική με τις καμπύλες Ντε Ραμ, αλλά αντί για δυαδικό ανάπτυγμα (βάση 2), χρησιμοποιείται τριπλό ανάπτυγμα (βάση 3).

Κώδικας[Επεξεργασία | επεξεργασία κώδικα]

Δεδομένων των συναρτήσεων σχεδίασης Με δεδομένες τις συναρτήσεις σχεδίασης void draw_line(double distance); και void turn(int angle_in_degrees);, ο κώδικας για τη σχεδίαση μιας (κατά προσέγγιση) καμπύλης βέλους Σιερπίνσκι έχει ως εξής:

void sierpinski_arrowhead_curve(unsigned order, double length)
{
    // If order is even we can just draw the curve.
    if ( 0 == (order & 1) ) {
        curve(order, length, +60);
    }
    else /* order is odd */ {
        turn( +60);
        curve(order, length, -60);
    }
}

void curve(unsigned order, double length, int angle)
{
    if ( 0 == order ) {
        draw_line(length);
    } else {
        curve(order - 1, length / 2, -angle);
        turn(angle);
        curve(order - 1, length / 2, angle);
        turn(angle);
        curve(order - 1, length / 2, -angle);
    }
}

Απεικόνιση ως σύστημα Λιντενμάγιερ[Επεξεργασία | επεξεργασία κώδικα]

Η καμπύλη βέλους του Σιερπίνσκι μπορεί να εκφράζεται με ένα σύστημα επανεγγραφής Σύστημα-L).

Αλφάβητο: X, Y

Σταθερές: F, +, &minus,

Αξίωμα: XF

'Κανόνες παραγωγής:

X → YF + XF + Y

Y → XF − YF − X

Εδώ, το F σημαίνει "τραβήξτε μπροστά", το + σημαίνει "στρίψτε αριστερά 60°", και το − σημαίνει "στρίψτε δεξιά 60°" (βλέπε γραφικά χελώνας).

Βιβλιογραφία[Επεξεργασία | επεξεργασία κώδικα]

Peitgen, H.-O.· Jürgens, H.· Saupe, D. (2013). Chaos and Fractals: New Frontiers of Science. Springer. ISBN 978-1-4757-4740-9.
Stevens, Roger T. (1989). Fractal Programming in C. M&T Books. ISBN 978-1-55851-037-1.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

↑ «Wacław Sierpiński - Biography». Maths History (στα Αγγλικά). Ανακτήθηκε στις 26 Δεκεμβρίου 2023.
↑ Weisstein, Eric W., "Sierpiński Curve" από το MathWorld.
↑ Dickau, Robert M. (1996/7)"Two-dimensional L-systems", Robert's Math Figures. MathForum.org. Retrieved 21 January 2019.
↑ Platzman, Loren K.; Bartholdi, John J. III (1989). «Spacefilling curves and the planar traveling salesman problem». Journal of the Association for Computing Machinery 36 (4): 719–737. doi:10.1145/76359.76361.
↑ Bartholdi, John J. III. «Some combinatorial applications of spacefilling curves». Georgia Institute of Technology. Αρχειοθετήθηκε από το πρωτότυπο στις 3 Αυγούστου 2012.
↑ «Turtle Geometry in Computer Graphics and Computer Aided Design» (PDF).

[1] «Wacław Sierpiński - Biography». Maths History (στα Αγγλικά). Ανακτήθηκε στις 26 Δεκεμβρίου 2023.

[2] Weisstein, Eric W., "Sierpiński Curve" από το MathWorld.

[3] Dickau, Robert M. (1996/7)"Two-dimensional L-systems", Robert's Math Figures. MathForum.org. Retrieved 21 January 2019.

[Platzman89-4] Platzman, Loren K.; Bartholdi, John J. III (1989). «Spacefilling curves and the planar traveling salesman problem». Journal of the Association for Computing Machinery 36 (4): 719–737. doi:10.1145/76359.76361.

[BartholdiURL-5] Bartholdi, John J. III. «Some combinatorial applications of spacefilling curves». Georgia Institute of Technology. Αρχειοθετήθηκε από το πρωτότυπο στις 3 Αυγούστου 2012.

[6] «Turtle Geometry in Computer Graphics and Computer Aided Design» (PDF).

[1]

[2]

[3]

[4]

[5]

[6]