algorytm.org

L-systemy



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

L-systemy
Ocena użytkowników:***** / 21
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 27 lipca 2005 18:17

L-systemy (systemy Lindemayera), znajdują zastosowanie w grafice komputerowej, szczególnie w generowaniu fraktali i modelowaniu roślin.
L-systemy wykorzystują tzw. produkcje. Działają one w następujący sposób: dany mamy symbol początkowy zwany aksjomatem - niech będzie to np. ac. Dane są również reguły np: a:b oraz b:ba - co w uproszczeniu możemy czytać następująco: jeżeli mamy a to zastępujemy je symbolem b, jeżeli mamy b to zastępujemy go symbolami ba. Czyli dla naszego aksjomatu i powyższych reguł otrzymamy:
1 iteracja) ac pod wpływem a:b przechodzi w bc a następnie pod wpływem b:ba w bac
2 iteracja) bac przechodzi w bbc a następnie w babac
3 iteracja) babac w bbbbc i dalej do babababac
...
Powstały w ten sposób ciąg symboli jest już po kilku iteracjach dosyć dobrym przybliżeniem fraktala, do którego dąży w granicy. Następnie otrzymany w ten sposób ciąg symboli interpretujemy zgodnie z zasadami "grafiki żółwia" i otrzymujemy gotowy obraz. Żółw rozumie następujące symbole:
  • F idź do przodu ustaloną odległość rysując linię,
  • f idź do przudu ustaloną odległość nie rysując linii,
  • + skręć o ustalony kąt w prawo,
  • - skręć o ustalony kąt w lewo,
  • [ wrzuć bieżący stan na stos - zapamiętaj pozycję żółwia oraz bieżący kąt
  • ] bieżącym stanem staje się stan pobrany ze szczytu stosu, żółw nie rysuje przy tym żadnych linii, choć jego pozycja może zmienić się,

Następujący system generuje tzw. Kwadratową wyspę Koch’a.
aksjomat: F+F+F+F
reguła: F: F+F-F-FF+F+F-F
Teraz należy zastosować regułę do aksjomatu, następnie otrzymany ciąg należy znów "potraktować" regułą, i tak kilka razy. Następnie należy otrzymany ciąg narysować według wyżej przedstawionych reguł "grafiki żółwia", dla kąta równego 90 stopni.
W Delhpi oraz Builderze można to zrobić stosując fukcję MoveTo dla f, oraz fukcję LineTo dla F. Przesuwać należy o dx oraz dy które są równe: dx=odleglosc*cos(kierunek), dy=odleglosc*sin(kierunek), kierunek na początku równy jest np 0 stopni, a dla symboli + oraz - zmieniamy go o określony kąt (zmienna odleglosc służy wyłącznie do skalowania obrazu).
Przy użyciu symboli operowania na stosie: [ oraz ] możemy konstryować struktury podobne do rzeczywistych roślin. Poszczególne produkcje takich L-systemów mają za zadanie tworzyć korzeń, gałęzie i liście.

Oto kilka przykładów reguł i ich wyników:

  • trójkąt Sierpińskiego
    aksjomat: F+F+F
    reguła: F: F+F-F-F+F
    kąt: 120 stopni

    L-Systemy - trójkąt Sierpinskiego

  • płatek śniegu Koch'a
    aksjomat: F++F++F
    reguła: F: F-F++F-F
    kąt: 60 stopni

    L-Systemy - płatek śniegu Koch'a

  • krzywa Hilberta
    aksjomat: X
    reguły: X: -YF+XFX+FY-
          Y: +XF-YFY-FX+
    kąt: 90 stopni

    L-Systemy - krzywa Hilberta

  • krzywa Moor'a
    aksjomat: XFX+F+XFX
    reguły: X: -YF+XFX+FY-
          Y: +XF-YFY-FX+
    kąt: 90 stopni

    L-Systemy - krzywa Moor'a

  • krzywa Peano
    aksjomat: X
    reguły: X: XFYFX+F+YFXFY-F-XFYFX
          Y: YFXFY-F-XFYFX+F+YFXFY
    kąt: 90 stopni

    L-Systemy - krzywa Peano

  • smok Heighway'a
    aksjomat: FX
    reguły: X: X+YF+
          Y: -FX-Y
    kąt: 90 stopni

    L-Systemy - smok Heighway'a

  • smok Levy'ego
    aksjomat: F
    reguła: F: +F--F+
    kąt: 45 stopni

    L-Systemy - smok Levy'ego

  • spirala
    aksjomat: AAAA
    reguły: A: X+X+X+X+X+X+
          X: [F+F+F+F[---X-Y]+++++F++++++++F-F-F-F]
          Y: [F+F+F+F[---Y]+++++F++++++++F-F-F-F]
    kąt: 15 stopni

    L-Systemy - spirala

  • pentadendryt
    aksjomat: F
    reguła: F: F+F-F--F+F+F
    kąt: 72 stopni

    L-Systemy - pentadendryt

  • struktura drzewiasta
    aksjomat: F
    reguła: F: F[+F]F[-F]F
    kąt: 25.7 stopni

    L-Systemy - drzewko

  • struktura drzewiasta
    aksjomat: ----F
    reguła: F: FF+[+F-F-F]-[-F+F+F]
    kąt: 22.5 stopni

    L-Systemy - drzewko


Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 3
Andrzej PartykaJava
.java
.java
***** / 0
Krzysztof BruszewskiScilab
.sci
.sci
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 sierpnia 2012 18:57
Dodaj komentarz