Die (raumfüllende) Hilbert-Kurve

Mistfahren mal ziemlich wissenschaftlich

Ausgerechnet die Anhänger des Sinclair ZX81 - eines der auf den ersten Blick unscheinbarsten Computer - sind heute, vierzig Jahre nach seiner Markteinführung, die aktivsten und verblüffen immer wieder mit neuen Hard- und Softwareprojekten.

So hat sich Ulrich vom ZX-Team eine vom “Zeddy“ angesteuerte kleine Maschine gebaut, die Ostereier bemalen kann, zu der Joachim die Programmierung beisteuerte. Sie stellten sie 2017 auf ihrem Team-Treffen und danach im Forum vor.

Sechs Wochen vor dem diesjährigen Osterfest stellte Joachim ein neues Muster zum Verzieren der Eier vor (siehe nebenstehenden screenshot eines YouTube-Videos) für das Wikipedia eine mehrere computerbildschirme füllende Erklärung gibt: Wikipedia Hilbert-Kurve. Es ist eine Kurve, die ein Quadrat vollständig ausfüllen kann.

Erstaunlich, was für Gedanken sich Mathematiker machen und zu welchen Resultaten sie kommen. Eine Linie bzw. Strecke hat, so lernten wir, nur eine Länge, ihre Breite ist Null. Wie zum Geier kann sie dann eine Fläche füllen? Die Antwort ist: in der Unendlichkeit, aber das können wir natürlich nicht nachprüfen. Paradox ist, dass ein endlich langes Programm genügt, das Problem anzugehen, doch ein Resultat wiederum nie wirklich geliefert werden kann.

Wie ich das meine? Das Programm enthält eine rekursive Subroutine. Rekursiv bedeutet, dass sich diese Subroutine immer wieder selbst aufruft, bis eine Abbruchbedingung erreicht ist. Diese Abbruchbedingung ist die Feinheit der Auflösung und diese Zahl bestimmt, wie oft sich die Subroutine aufruft. Hierfür benötigt das Rechenprogramm einen Stapel für die Rückkehradressen, also physisch einen Bereich des RAM-Speichers. Gehen wir nun in die Unendlichkeit, muss die Auflösung unendlich fein - der Return-Stack unendlich groß sein, der Computer also unendlich viele RAM-Bausteine allein hierfür haben. Darüber hinaus würde der Computer auch unendlich lange rechnen müssen – und so viel Zeit kann nun endgültig niemand von uns aufbringen.

Dem allen zum Trotz hat das Thema eine praktische Anwendung ...

... im Wikipedia-Artikel steht:

Mithilfe der Hilbert-Kurve endlicher Iteration kann man die Teilquadrate und mithilfe des Limes die Punkte im Quadrat in eine lineare Reihenfolge bringen, die Hilbert-Ordnung genannt wird. Mit ihr lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört binäres Suchen, binärer Suchbaum, Skip-Liste und andere.

Und das sind noch ein paar der
verständlichsten Sätze in dem langen Artikel:

Die Zuordnung hn der Hilbert-Kurve einer (endlichen) n-ten Iteration ist umkehrbar und kann zu beliebiger Feinheit gesteigert werden. Dieses und die gute Nachbarschaftserhaltung hat eine Vielfalt von Anwendungen der Hilbert-Kurve in der Informatik eröffnet, so in der Bildverarbeitung, Datendarstellung, im Hochleistungsrechnen und in anderen Gebieten.

Joachim hat jedenfalls mit der Hilbert-Kurve ein interessantes Thema aufgegriffen.

Heinz, eigentlich ein Spectrum-Mann, dachte sich, die Muster sollte man erst einmal auf dem Computermonitor begutachten und schrieb zunächst ein LOGO-Programm dafür (Läuft es auf unserer JOYCE? Freiwillige vor!) und anschließend eins für das Basic des ZX81.

Mir kam (wen wundert es?) der Gedanke, Heinz' Programm in das BasiCode-System zu übertragen. Auf den ersten Blick klingt es umständlich, das Drumherum "aufzublasen". Doch es bringt den Vorteil, dass die übertragbare Hälfte des BasiCode-Programms dann auch sofort auf allen Computern genutzt werden kann, für die es BasiCode-3 gibt. Die Grafik-Befehle müssen nicht abgeändert werden, denn sie sind in der nicht-übertragbaren Hälfte verankert - der LINETO-Befehl wird einheitlich mit GOSUB 630 aufgerufen.

Unter BasiCode-Anwendern sind Programme mit selbstähnlichen Strukturen schon bekannt, zum Beispiel SCHNEEFL.ASC und SIERPINS.ASC, die unter dem Reiter "Programs" des online-Bascoders zu finden sind, wo sie auch gleich ausprobiert werden können. Um das Hilbert-Programm zu testen genügt es, es unter dem Reiter "Listing" hineinzukopieren, zum Starten einfach in das große linke Fenster klicken.

1000 LET A=200
 1003 GOTO 20
 1006 REM   HILBERT-KURVE
 1010 GOSUB 8010
 1020 GOSUB 9010
 1030 IF G<>0 THEN GOTO 1050
 1040 GOTO 950
 1050 GOSUB 600
 1060 LET HO=.18
 1070 LET VE=.82
 1080 LET CN=1
 1090 GOSUB 620
 1100 LET X=0
 1110 LET Y=0
 1120 LET CN=0
 1130 GOSUB 630
 1140 LET S=128/2^G
 1150 LET RI=0
 1160 LET W=90
 1170 LET N=G
 1180 GOSUB 3010
 1190 GOSUB 210
 1200 GOSUB 100
 1210 GOTO 1020
 3000 REM *** REKU *** IN DER NÄCHSTEN ZEILE STARTET
 3001 REM DAS REKURSIONS-UNTERPROGRAMM
 3010 IF N=0 THEN GOTO 3990
 3011 REM EIN GUTER INTERPRETER BEMÄNGELT, WENN RETURN
 3012 REM IN EINER GOSUB-ROUTINE MEHRMALS AUFTAUCHT,
 3013 REM DESWEGEN STEHT HIER EIN  SPRUNG ZUR ZEILE,
 3014 REM DIE DEN (NUN EINZIGEN)RETURN-BEFEHL ENTHÄLT.
 3015 REM DER SPRUNG ERFOLGT, WENN N GLEICH NULL
 3016 REM ERREICHT WIRD (ABBRUCHBEDINGUNG, OHNE SIE
 3017 REM WÜRDE DER RETURN-STACK RASCH ÜBERLAUFEN)
 3020 LET RI=RI+W
 3030 LET N=N-1
 3040 LET W=-W
 3050 GOSUB 3010:REM HIER RUFT SICH DIE GOSUB-ROUTINE SELBST WIEDER AUF
 3060 LET W=-W
 3070 GOSUB 4010
 3080 LET RI=RI-W
 3090 GOSUB 3010:REM HIER RUFT SICH DIE GOSUB-ROUTINE SELBST WIEDER AUF
 3100 GOSUB 4010
 3110 GOSUB 3010:REM HIER RUFT SICH DIE GOSUB-ROUTINE SELBST WIEDER AUF
 3120 LET RI=RI-W
 3130 GOSUB 4010
 3140 LET W=-W
 3150 GOSUB 3010:REM HIER RUFT SICH DIE GOSUB-ROUTINE SELBST WIEDER AUF
 3160 LET W=-W
 3170 LET RI=RI+W
 3180 LET N=N+1
 3990 RETURN
 4000 REM *** DRAW ***
 4010 RI=(RI+1080) MOD 360
 4020 REM IF RI<360 THEN GOTO 4050
 4030 REM LET RI=RI-360
 4040 REM GOTO 4020
 4050 REM IF RI>-90 THEN GOTO 4080
 4060 REM LET RI=RI+360
 4070 REM GOTO 4050
 4080 LET A=S*V(1+RI/90)
 4090 LET B=S*H(1+RI/90)
 4100 LET X=X+B
 4110 LET Y=Y+A
 4120 LET HO=.18+X/HG
 4130 LET VE=.82-Y/VG
 4140 GOSUB 630
 4990 RETURN
 8000 REM *** INIT ***
 8010 RESTORE
 8020 DIM V(5)
 8030 DIM H(5)
 8040 FOR N=1 TO 4
 8050 READ M
 8060 V(N)=M
 8070 NEXT N
 8080 FOR N=1 TO 4
 8090 READ M
 8100 LET H(N)=M
 8110 NEXT N
 8120 LET CC(1)=0
 8130 LET CC(0)=7
 8140 RETURN
 9000 REM *** ERKLAERUNG ***
 9010 GOSUB 100
 9020 LET HO=7
 9030 LET VE=2
 9040 GOSUB 110
 9050 LET SR$="HILBERT-KURVE"
 9060 GOSUB 150
 9070 LET HO=0
 9080 LET VE=5
 9090 GOSUB 110
 9100 PRINT "DIE HILBERTKURVE IST EINE LINIE,"
 9110 PRINT
 9120 PRINT "DIE SELBSTAEHNLICH IN IMMER FEI-"
 9130 PRINT
 9140 PRINT "NERER VERAESTELUNG  SCHLIESSLICH"
 9150 PRINT
 9160 PRINT "EINE  FLAECHE  VOLLSTAENDIG AUS-"
 9170 PRINT
 9180 PRINT "FUELLT."
 9190 PRINT
 9200 PRINT
 9210 PRINT "       VERSCHACHTELUNGS-"
 9220 PRINT
 9230 PRINT "       TIEFE: (0 = ENDE) ";
 9240 INPUT G
 9250 LET G=ABS(INT(G))
 9260 RETURN
25000 DATA 1,0,-1,0,0,1,0,-1,0,-1
30000 REM MODULO-FUNKTION IN AELTEREN BASICS
30010 REM NICHT VORHANDEN - DANN ZEILE 4010
30020 REM MIT REM UNWIRKSAM MACHEN UND ZEILEN
30030 REM 4020 BIS 4070 AKTIVIEREN
32000 REM  *** HILBERT-KURVE ***
32010 REM CODE: JOACHIM       ZX-
32020 REM       ZX-HEINZ     TEAM
32030 REM BASICODE-FASSUNG  MAERZ
32040 REM   TH. RADEMACHER   2021

Es hat eine gewisse Faszination zuzuschauen, wie der Computer die Verästelungen zeichnet, ohne sich zu verhaspeln. Ich fühlte mich an ein Spiel aus der Grundschulzeit erinnert:

Im Schulhort spielten wir außer "Name, Stadt, Land" (in den alten Bundesländern bekannt als "Stadt, Land, Fluss") auch sehr gern "Mistfahren": Auf einem Blatt Papier werden kreuz und quer Zahlen z.B. von 1 bis 30 aufgeschrieben. Der erste Spieler kreist nun die 1 ein und zeichnet einen Weg zur nächsten Nummer (der 2) und kreist sie ein. Der zweite Spieler zeichnet von dort mit einer anderen Farbe einen Weg zur nächsten Nummer und kreist sie ein. Nun ist der erste Spieler wieder an der Reihe. Die anderen Nummern und immer mehr werdenden Linien dürfen weder berührt noch gekreuzt werden, sonst ist das Spiel für den ungeschickten Zeichner verloren.

Ob es die Kurzen heute noch spielen? Vermutlich nur, wenn es das auch als App für das Tablet gibt !?!

Ich habe mich so weit es ging an Joachims und Heinz' Vorlage gehalten und nur dort eingegriffen, wo ZX81 und die restliche Computerwelt nicht kompatibel sind. Zum Beispiel bemängeln manche BASICs, wenn es für eine GOSUB-Anweisung zwei RETURN-Anweisungen gibt, z.B. im THEN- und ELSE-Zweig einer IF-Anweisung. Die Verwendung von SIN und COS habe ich zwecks Zeitersparnis durch eine Variante der MOD-Funktion ersetzt.

Es gibt übrigens weitere solcher raumfüllenden Kurven, zum Beispiel hat Bernd ein Turbo-Pascal-Programm für Peano-Kurven geschrieben ... einfach 'mal einen Abstecher ins joyceforum.de wagen !

Thomas Rademacher // April 2021