BSc KI — Cursus Natuur & Berekening 2025-26

Opdracht 1: Sierpinski's tapijt

Inleiding

Brown Family Courtyard, U. of Puget Sound Tacoma, WA.
Fig. 1: Brown Family Courtyard, U. of Puget Sound Tacoma, WA.
Sierpinski's tapijt is een 2D fractal, voor het eerst beschreven door Wacław Sierpiński in 1916. Het is een generalisatie van Cantor's kam, en om die reden ook weer een verzameling met kansmaat nul.

Opdracht

Construeer Sierpinski's tapijt, en genereer een animatie door voortdurend in te zoomen op een hoek.

Doel

Het doel van deze opdracht is om praktische ervaring op te doen met het genereren van fractals. Een uitdaging is om de bijbehorende meetkundige vraagstukken op te lossen en te implementeren.

Er zijn tenminste twee manieren om Sierpinski's tapijt te genereren: de tegel-gebaseerde aanpak en de pixel-gebaseerde aanpak. Je mag zelf weten welke aanpak je kiest.

De tegel-gebaseerde aanpak

  1. Coördinatenstelsel.. Het is handig om de oorsprong in de linkerbenedenhoek te zetten. Zo heb je alleen te maken met niet-negatieve coördinaten. Ook zijn positieve coördinaten handig om tegels te schalen (uit te vergroten).
  2. De tegel. Het is handig eerst een vierkante tegel aan te maken in de “Turtle Shapes Editor” (TSE, onder “Tools”) met grootte 1. (In de praktijk betekent dit dat de tegel precies het hele canvas van de TSE afdekt.) Ook is het handig om meteen, nog steeds in the TSE, aan te geven dat de aangemaakte turtle shape niet mag roteren.
  3. Uitproberen. Om gevoel voor verhoudingen te krijgen kun je het volgende doen. Maak alle patches eens zichtbaar met bijvoorbeeld 
    ask patches [ set pcolor (pxcor + pycor) mod 2 ]
    Creëer vervolgens eens één tegel, en probeer die tegel bijvoorbeeld eens precies de negen patches 
    K = { patch ∈ Patches | pxcor, pycor ∈ {4, 5, 6} }
    te laten afdekken. Realiseer je daarbij ook dat patches geen roostervakken zijn, maar juist midden op roosterpunten liggen.
  4. Verkleinen en transleren. Probeer die ene tegel eens te verkleinen totdat deze alleen de patch (4, 4) afdekt. Probeer dezelfde tegel eens andere patches in K te laten afdekken. Tip: draaien en dan een stukje vooruit. (In de TSE betekent `niet roteerbaar' dat de tegelfiguur niet kan draaien, maar de onderliggende turtle kan nog steeds wel draaien.)
  5. Splitsen. Probeer nu eens, volgens de denkwijze van het Sierpinski-tapijt, de tegel te splitsen in negen kleinere tegels. (Tip: 8x hatch, om tenslotte de tegel zelf te verkleinen en te verplaatsen.)
  6. Fractal. Je kunt nu herhaaldelijk aan tegels vragen of ze willen splitsen. (Als je goed gecodeerd hebt, willen ze dat wel.)
  7. Begin van de animatie. Om de fractal vanuit de linkerhoek te animeren, kun je met één tegel beginnen. Deze moet linksonder wel op de goede plaats staan. Bepaal zelf of dat (0, 0) is, of (1/2, 1/2) of een andere coördinaat.
  8. Animatie. In de animatie worden vervolgens alle tegels herhaaldelijk geschaald vanuit de oorsprong met een vaste factor dicht boven de 1. (Tip: vergroten en verplaatsen.) Al tijdens de animaties een tegel te groot wordt, dan splitst deze. (Wat “te groot” is bepaal jij. Mischien is het handig hiervoor een slider aan te leggen.)
  9. Sliders. Het is handig sliders aan te leggen voor de vergrotingsfactor (= animatiesnelheid) en voor de grootte waarboven tegels dienen te splitsen.
  10. Vertrekkende tegels. Als de randen van je canvas op elkaar zijn aangesloten, en een tegel beweegt over bijvoorbeeld de rechterrand, dan verschijnt 'ie weer aan de linkerrand van het canvas. Als de randen van het canvas NIET op elkaar zijn aangesloten, dan zal Netlogo een foutmelding geven omdat de tegel “niet verder kan”. Zorg ervoor dat, als een tegel uit het zicht verdwijnt, deze zichzelf verwijderd. (Tip: of een tegel over de rand schuift hangt niet alleen af van z'n coördinaten, maar ook van z'n omvang.)

De pixel-gebaseerde aanpak

Deze aanpak werkt met patches in plaats van turtles.

  1. Coördinatenstelsel. In dit geval representeert het canvas het eenheidsvierkant. Kies de oorsprong linksonder, kies voor veel kleine patches, en laat elke patch z'n x en y-coördinaat t.o.v. het eenheidsvierkant onthouden. (Gebruik patches-own.)
  2. Fractal. Maak eerst een statische fractal door voor elke patch te bepalen of deze in enig middelste derde deel van het eenheidsvierkant ligt, als volgt: als van een patch het paar (x, y) in het middelste derde deel van het vierkant ligt, dan ligt die patch met zekerheid buiten het Sierpinski-tapijt. In het andere geval is er geen zekerheid, en wordt het paar (x, y) geschaald, dat wil zeggen dat x en y beiden met drie vermenigvuldigd worden waarna ze weer binnen het eenheidsvierkant worden gebracht. Als bijvoorbeeld x ≥ 2/3, dan wordt de nieuwe waarde van x gelijk aan 3x − 2. En als 1/3 < x < 2/3, dan wordt x gelijk aan 3x − 1. Hetzelfde voor y. Vervolgens wordt op het geschaalde paar (x, y) opnieuw de middel-derde check uitgevoerd. Bij succes ligt de patch met zekerheid buiten het Sierpinski-tapijt. In het andere geval is er geen zekerheid en wordt het paar (x, y) weer geschaald. Het aantal iteraties bepaalt het detail van de fractal.
  3. Animatie. Zoom in door het canvas niet het eenheidvierkant, maar een steeds kleiner vierkant te laten representeren. Dit kan makkelijk door elke patch te laten beginnen met geschaalde (x, y)-waarden. Bijvoorbeeld, met een zoom-factor gelijk aan 2 begint elke patch de middel-derde check met het paar (x/2, y/2).
  4. Hoeveel iteraties?. Tijdens een animatie hangt het aantal benodigde iteraties (per patch) af van het detailnivo (= natuurlijk getal) en de schaalfactor (= 1 / zoom). Hoe meer detail en hoe kleiner de schaal, hoe meer iteraties er nodig zijn. Als vuistregel geldt
    aantal benodigde iteraties = detailnivo − 3log schaalfactor .
  5. Sliders. Het is handig om de schaalfactor en het detailnivo in te kunnen stellen met sliders.

Tips

Extra

Met de standaard-implementatie kunnen maximaal acht punten worden gescoord. Extra punten, tot een maximum van tien punten, kunnen worden verdiend door het aanbrengen van één van de volgende features. Het ontbreken van een onderdeel uit de basis-implementatie kan niet worden gecompenseerd met een extra feature.

  1. Gelijkmatige animatie (max 2pt). Qua vorm is de tegel-gebaseerde animatie superieur, maar hij kent ook een zwak punt. Dankzij de aard van de fractal splitsen veel tegels op hetzelfde moment. Daardoor vertraagt de animatie tijdelijk. Verzin een techniek zodanig dat de animatie met een constante snelheid verloopt.
  2. Ongemerkt herschalen (max 1pt). Bij de pixel-animatie kan onbeperkt inzoomen op den duur leiden tot afwijkingen achter de komma, en dus leiden tot een verstoord beeld. Verzin iets waardoor onbeperkt inzoomen wordt vermeden maar de animatie toch vloeiend blijft verlopen.
  3. Andere verhoudingen (max 2pt). De standaard verhouding is (1/3, 1/3, 1/3). Zorg er voor dat tapijten kunnen worden gegenereerd met andere verhoudingen, bijvoorbeeld (1/4, 1/2, 1/4), of (1/2, 1/2, 1/4). Misschien zelfs (1/5, 1/5, 1/5, 1/5, 1/5).
  4. Andere opbouw (max 1pt). Met minieme wijzigingen in het algoritme ontstaan andere fractals. Een voorbeeld hiervan zie je rechts. Merk op dat in dit voorbeel de verhoudingen anders liggen en de resulterende fractal strict genomen niet meer valt onder de categorie “Sierpinski's tapijt”. Voor willekeurige wijzigingen zonder duidelijk resultaat worden geen punten toegekend☺.
  5. Oppervlakte (max 1pt). Plot na elke update de oppervlakte van de fractal.
  6. Inzoomen op een willekeurig gedeelte (max 2pt). Door anders te schalen kan worden ingezoomd op een willekeurig gedeelte. Zoom bijvoorbeld in op een rechthoek rond muiscoördinaten.
  7. Anti-aliasing (max 2pt). De pixel-animatie lijdt aan rasterisatie, wat wil zeggen dat de fractal in het diepste detail niet goed meer wordt weergegeven omdat één patch meerdere punten overdekt. Pas een primitieve vorm van anti-aliasing toe om rasterisatie-effecten gedeeltelijk op te heffen. Laat bijvoorbeeld een patch elke keer keer een ander punt binnen zijn bereik representeren. Of het (kleur-)gemiddelde van, zeg, vier punten binnen de patch.

Tenslotte

Een volledig uitgeïtereerd tapijt heeft oppervlakte nul, en is voor ons dus onzichtbaar ...

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt. 

   ------------------------------------------------------

    1. complete, nette, en intuitieve GUI
    2. kunnen genereren van een statische fractal
    3. correcte geometrie fractal
    4. kunnen genereren van een animatie
    5. correcte animatie
    6. kwaliteit code
    7. executiesnelheid
    8. documentatie (in code, in tab, *.png)

   ----- cijfer acht ------------------------------------

    9. extra feature
   10. extra feature

   ----- cijfer tien ------------------------------------

*Naast de algemene randvoorwaarden voor de programmeeropdrachten en de algemene randvoorwaarden voor de programmeeropdrachten die specifiek in Netlogo worden uitgevoerd. Zie de pagina met clausules.


Laatst gewijzigd op woensdag 13 november 2024, om 15:02 uur Auteur(s): Gerard Vreeswijk Translate to en, ru, or tr