Fractals in C

[npapak]

Θελω να κανω ενα fractal σε C με την βοηθεια αναδρομης, αλλα εχω ενα προβήμα.

 

Ο αλγοριθμος του fractal ειναι ο εξης:

 

1.Παρε ενα μαυρο τετραγωνο, χωρισε το σε 4 ισα τετραγωνα και και κανε το κατω αριστερα τετραγωνο ασπρο.

 

2.Επανελαβε τη διαδικασια για ολα τα νεα τετραγωνα μεχρι να φτασεις στο σημειο να μην μπορεις να χωρισεις τα νεα τετραγωνα.

 

(Κανω επισυναψη τα 3 πρωτα βηματα για να γινει πιο κατανοητο)

 

Η ερωτηση μου ειναι 8α πρεπει να αναδρομικα την συναρτηση για καθε τετραγωνο ξεχωριστα?

 

Ευχαριστω.

 

Υ.Γ. : Ολα γινονται σε πινακα ακαιρεων που με καταληλο κωδικα μετατρεπωνται σε ασπρομαυρη εικονα.

 

Ευχαριστω προκαταβολικα.

[macabre_sunsets]

Μπορείς να δώσεις τον πίνακα των ακεραίων? Ή δεν είναι κάτι στάνταρ? Από πού παίρνεις το αρχικό τετράγωνο?

[npapak]

Αρχικα δινω το μεγεθος του πινκα που πρεπει να ειναι δυναμη του 2 και τον γεμιζω με 0 (το 0 αναπαριστα το μαυρο). Μετα καλω την συναρτηση για να αρχισει να κατεσκεθαζεται το fractal.

[PCharon]

Πολύ εύκολο. Μπορώ να το φτιάξω υπό τύπου screensaver (κάποια στιγμή που θα 'χω όρεξη να παίξω!). Είχα φτιάξει κι άλλα παλιότερα αλλά είχα ξεμείνει από ιδέες, χα. Thanks για την ιδέα λοιπόν!

[parsifal]

Η ερωτηση μου ειναι 8α πρεπει να αναδρομικα την συναρτηση για καθε τετραγωνο ξεχωριστα?

 

Αν κατάλαβα καλά το πρόβλημα, η αναδρομική συνάρτηση που θα πρέπει να φτιάξεις θα καλείται στην main μία μόνο φορά, με όρισμα ολόκληρο τον πίνακα.

 

Εντός της συνάρτησης τώρα: θα πρέπει αυτή να σπάζει τον πίνακα που έχει λάβει ως όρισμα σε 4 υποπίνακες και να καλεί τον εαυτό της μία φορά για κάθε έναν από τους υποπίνακες, άρα τέσσερις φορές. Δηλαδή συνολικά όταν κοιτάς τον τελειωμένο κώδικα, θα φαίνεται να καλείται η συνάρτηση 5 φορές.

[npapak]

Ακριβως...

 

Οτι εχω δοκιμασει δεν δουλεπσε ετσι οπως περιμενα.

 

Λοιπον εχετε καμια ιδεα?

[bilco]

Για να γλυτώσουμε κάμποση δουλειά πρέπει να παρατηρήσουμε ότι κάθε φορά τα 3 από τα 4 τετράγωνα είναι ίδια. Άρα αρκεί να υπολογίζουμε το ένα και να το κοπιάρουμε στα άλλα δύο. Έτσι προχωράμε την αναδρομή μέχρι να φτάσουμε σε μέγεθος 2χ2, και επιστρέφοντας κάθε φορά κάνουμε την αντιγραφή και 'ασπρίζουμε' το 4 τετράγωνο.

 

>
// ο πίνακας arr είναι n x n όπου n είναι δύναμη του 2
// με αρχικά όλες τις τιμές 0 (μαύρο)
void bw_fractal(int** arr, int n) {
   int i, j;
   if (n == 2)  {
       // το κάτω αριστερά pixel άσπρο (1)
       arr[1][0] = 1;
       // τίποτα άλλο εδώ αφού τα υπόλοιπα είναι ήδη 0
   }
   else  {
       // με την αναδρομή υπολογίζουμε κάθε φορά το επάνω
       // αριστερό τετράγωνο
       bw_fractal(arr, n / 2);
       // και μετά το αντιγράφουμε στα δύο δεξιά, και ασπρίζουμε
       // το κάτω αριστερό
       for (i = 0; i < n / 2; i++)
           for (j = 0; j < n / 2; j++) {
               arr[i + n / 2][j] = arr[i + n / 2][j + n / 2] = arr[i][j];
               arr[i][j + n / 2] = 1;
           }
   }
}

[npapak]

Μισο γτ νομιζω οτι δεν καταλαβεσ κατι καλα.

Οταν λεω το κατω αριστερα τετραγωνο δεν εννοω το array[N-1][0]

 

χωριζουμε το αρχικο τετραγωνο σε 4 ισα τετραγωνα και ασπριζουμε το κατω αριστερα...

οποτε το δικο σου δουλευει μονο για πινακα 2x2.

 

sorry αν δεν το εξηγησα καλα :S

[bilco]

Τα ίδια έχουμε καταλάβει

Κοίταξέ το πάλι ή καλύτερα δοκίμασε να το περάσεις σε ένα bitmap (πχ 512 Χ 512) για να δεις το αποτέλεσμα.

[npapak]

Βασικα δεν ειναι αυτο που περιμενα. Αυτο που μου εγραψες ειναι το τριγωνο του Sierpinski.

 

Εγω θελω να βγαλω κατι σαν αυτο που κανω επισυναψη.

 

Ο κωδικας που μου εδωσες αλλαζει και τα τετραγωνα που εχουν γινει ηδη ασπρα,πραγμα που εγω δεν θελω...

[Krokodilos]

Βασικα δεν ειναι αυτο που περιμενα. Αυτο που μου εγραψες ειναι το τριγωνο του Sierpinski.

Νομιζω οτι μπορω να αποδειξω οτι το τριγωνο του Sierpinski, με αυτο που ζητας επειτα απο απειρες εφαρμογες επαναληψεων ειναι ακριβως το ιδιο συνολο σημειων.

Οποτε το σχημα μετα απο πολλες επαναληψεις(βασικα οχι και τοσο πολλες, υπολογιζω γυρω στις 7-8) θα αρχισει να μοιαζει οπτικα σε εμας με το τριγωνο του Sierpinski.

[npapak]

Οριστε??

 

Δεν ειναι πιο απλο απλα να μιν πειραζουμε οτι εχουμε ηδη αλλξει??

[PCharon]

Χα, μ'αρέσουν αυτά βγάζουν ωραία σχεδιάκια.

 

Νομιζω οτι μπορω να αποδειξω οτι το τριγωνο του Sierpinski, με αυτο που ζητας επειτα απο απειρες εφαρμογες επαναληψεων ειναι ακριβως το ιδιο συνολο σημειων.

Έπεσες σχεδόν μέσα: σχηματίζεται ακριβώς το "αρνητικό" του τριγώνου του Sierpinski!

 

Επισυνάπτω υλοποιημένο το παραπάνω ως sreensaver που είχα πει, σε δύο εκδόσεις, λευκό και με τεχνητό χρωματισμό. Υπάρχει 1msec καθυστέρηση ανά τετράγωνο που χρωματίζεται για λόγους απόλαυσης.

fractal.zip

[npapak]

Δεν ειανι το αντιστροφο του τριγωνου του Sierpinski. ειναι τελειως διαφορετικο το σχημα :S

[PCharon]

Λάθος κάνεις. Τουλάχιστον η μέθοδος που έδωσες αυτό βγάζει δεν έχω κάνει λάθος (το βλέπεις κιόλας!). Έχω φτιάξει και άλλο που δημιουργεί το τρίγωνο του Sierpinski με τη γνωστή μέθοδο (σημείο - σημείο) και είναι ακριβώς το ίδιο. Δεν πιστεύω να το λες επειδή το τρίγωνο είναι ορθογώνιο αντί για το ισοσκελές που μπορεί να έχεις δει σε σχηματάκια, το ίδιο πράγμα είναι.

 

Υ.Γ. Μήπως εκτελείται πολύ γρήγορα και πρέπει να βάλω πάνω από 1msec καθυστέρηση? Επειδή το εκτελώ σε πολύ παλιό PC και προλαβαίνω να το δω να σχηματίζεται.

Υ.Γ.2 Αν έχετε βρει κι άλλες μεθόδους κατασκευής fractal, please δώσ'τε link!