Hilbert curve
Produce a graphical or ASCII-art representation of a Hilbert curve of at least order 3.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
ALGOL 68
This generates the curve following the L-System rules described in the Wikipedia article.
L-System rule | A | B | F | + | - |
Procedure | a | b | forward | right | left |
<lang algol68>BEGIN
INT level = 4; # <-- change this #
INT side = 2**level * 2 - 2; [-side:1, 0:side]STRING grid; INT x := 0, y := 0, dir := 0; INT old dir := -1; INT e=0, n=1, w=2, s=3;
FOR i FROM 1 LWB grid TO 1 UPB grid DO FOR j FROM 2 LWB grid TO 2 UPB grid DO grid[i,j] := " " OD OD;
PROC left = VOID: dir := (dir + 1) MOD 4; PROC right = VOID: dir := (dir - 1) MOD 4; PROC move = VOID: ( CASE dir + 1 IN # e: # x +:= 1, # n: # y -:= 1, # w: # x -:= 1, # s: # y +:= 1 ESAC ); PROC forward = VOID: ( # draw corner # grid[y, x] := CASE old dir + 1 IN # e # CASE dir + 1 IN "──", "─╯", " ?", "─╮" ESAC, # n # CASE dir + 1 IN " ╭", " │", "─╮", " ?" ESAC, # w # CASE dir + 1 IN " ?", " ╰", "──", " ╭" ESAC, # s # CASE dir + 1 IN " ╰", " ?", "─╯", " │" ESAC OUT " " ESAC; move; # draw segment # grid[y, x] := IF dir = n OR dir = s THEN " │" ELSE "──" FI; # advance to next corner # move; old dir := dir );
PROC a = (INT level)VOID: IF level > 0 THEN left; b(level-1); forward; right; a(level-1); forward; a(level-1); right; forward; b(level-1); left FI, b = (INT level)VOID: IF level > 0 THEN right; a(level-1); forward; left; b(level-1); forward; b(level-1); left; forward; a(level-1); right FI;
# draw # a(level);
# print # FOR row FROM 1 LWB grid TO 1 UPB grid DO print((grid[row,], new line)) OD
END </lang>
- Output:
╭───╮ ╭───╮ ╭───╮ ╭───╮ ╭───╮ ╭───╮ ╭───╮ ╭───╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───╯ │ │ ╰───╯ │ │ ╰───╯ │ │ ╰───╯ │ │ │ │ │ │ │ │ │ ╰───╮ ╭───╯ ╰───╮ ╭───╯ ╰───╮ ╭───╯ ╰───╮ ╭───╯ │ │ │ │ │ │ │ │ ╭───╯ ╰───────────╯ ╰───╮ ╭───╯ ╰───────────╯ ╰───╮ │ │ │ │ │ ╭───────╮ ╭───────╮ │ │ ╭───────╮ ╭───────╮ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───╯ ╭───╯ ╰───╮ ╰───╯ ╰───╯ ╭───╯ ╰───╮ ╰───╯ │ │ │ │ ╭───╮ ╰───╮ ╭───╯ ╭───╮ ╭───╮ ╰───╮ ╭───╯ ╭───╮ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───────╯ ╰───────╯ ╰───╯ ╰───────╯ ╰───────╯ │ │ │ ╰───╮ ╭───────╮ ╭───────╮ ╭───────╮ ╭───────╮ ╭───╯ │ │ │ │ │ │ │ │ │ │ ╭───╯ ╰───╮ ╰───╯ ╭───╯ ╰───╮ ╰───╯ ╭───╯ ╰───╮ │ │ │ │ │ │ │ ╭───╮ │ ╭───╮ ╰───╮ ╭───╯ ╭───╮ │ ╭───╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───╯ ╰───╯ │ ╰───────╯ ╰───────╯ │ ╰───╯ ╰───╯ │ │ ╭───╮ ╭───╮ │ ╭───────╮ ╭───────╮ │ ╭───╮ ╭───╮ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ ╰───╯ │ ╰───╯ ╭───╯ ╰───╮ ╰───╯ │ ╰───╯ │ │ │ │ │ │ │ ╰───╮ ╭───╯ ╭───╮ ╰───╮ ╭───╯ ╭───╮ ╰───╮ ╭───╯ │ │ │ │ │ │ │ │ │ │ ───╯ ╰───────╯ ╰───────╯ ╰───────╯ ╰───────╯ ╰──
AutoHotkey
Requires Gdip Library <lang AutoHotkey>gdip1() HilbertX := A_ScreenWidth/2 - 100, HilbertY := A_ScreenHeight/2 - 100 Hilbert(HilbertX, HilbertY, 2**5, 5, 5, Arr:=[]) xmin := xmax := ymin := ymax := 0 for i, point in Arr { xmin := A_Index = 1 ? point.x : xmin < point.x ? xmin : point.x xmax := point.x > xmax ? point.x : xmax ymin := A_Index = 1 ? point.y : ymin < point.y ? ymin : point.y ymax := point.y > ymax ? point.y : ymax } for i, point in Arr points .= point.x - xmin + HilbertX "," point.y - ymin + HilbertY "|" points := Trim(points, "|") Gdip_DrawLines(G, pPen, Points) UpdateLayeredWindow(hwnd1, hdc, 0, 0, Width, Height) return
- ---------------------------------------------------------------
Hilbert(x, y, lg, i1, i2, Arr) { if (lg = 1) { Arr[Arr.count()+1, "x"] := x Arr[Arr.count(), "y"] := y return } lg /= 2 Hilbert(x+i1*lg , y+i1*lg , lg , i1 , 1-i2 , Arr) Hilbert(x+i2*lg , y+(1-i2)*lg , lg , i1 , i2 , Arr) Hilbert(x+(1-i1)*lg , y+(1-i1)*lg , lg , i1 , i2 , Arr) Hilbert(x+(1-i2)*lg , y+i2*lg , lg , 1-i1 , i2 , Arr) }
- ---------------------------------------------------------------
gdip1(){ global If !pToken := Gdip_Startup() { MsgBox, 48, gdiplus error!, Gdiplus failed to start. Please ensure you have gdiplus on your system ExitApp } OnExit, Exit Width := A_ScreenWidth, Height := A_ScreenHeight Gui, 1: -Caption +E0x80000 +LastFound +OwnDialogs +Owner +AlwaysOnTop Gui, 1: Show, NA hwnd1 := WinExist() hbm := CreateDIBSection(Width, Height) hdc := CreateCompatibleDC() obm := SelectObject(hdc, hbm) G := Gdip_GraphicsFromHDC(hdc) Gdip_SetSmoothingMode(G, 4) pPen := Gdip_CreatePen(0xFFFF0000, 2) }
- ---------------------------------------------------------------
gdip2(){ global Gdip_DeleteBrush(pBrush) Gdip_DeletePen(pPen) SelectObject(hdc, obm) DeleteObject(hbm) DeleteDC(hdc) Gdip_DeleteGraphics(G) }
- ---------------------------------------------------------------
Exit: gdip2() Gdip_Shutdown(pToken) ExitApp Return</lang>
C
<lang c>#include <stdio.h>
- define N 32
- define K 3
- define MAX N * K
typedef struct { int x; int y; } point;
void rot(int n, point *p, int rx, int ry) {
int t; if (!ry) { if (rx == 1) { p->x = n - 1 - p->x; p->y = n - 1 - p->y; } t = p->x; p->x = p->y; p->y = t; }
}
void d2pt(int n, int d, point *p) {
int s = 1, t = d, rx, ry; p->x = 0; p->y = 0; while (s < n) { rx = 1 & (t / 2); ry = 1 & (t ^ rx); rot(s, p, rx, ry); p->x += s * rx; p->y += s * ry; t /= 4; s *= 2; }
}
int main() {
int d, x, y, cx, cy, px, py; char pts[MAX][MAX]; point curr, prev; for (x = 0; x < MAX; ++x) for (y = 0; y < MAX; ++y) pts[x][y] = ' '; prev.x = prev.y = 0; pts[0][0] = '.'; for (d = 1; d < N * N; ++d) { d2pt(N, d, &curr); cx = curr.x * K; cy = curr.y * K; px = prev.x * K; py = prev.y * K; pts[cx][cy] = '.'; if (cx == px ) { if (py < cy) for (y = py + 1; y < cy; ++y) pts[cx][y] = '|'; else for (y = cy + 1; y < py; ++y) pts[cx][y] = '|'; } else { if (px < cx) for (x = px + 1; x < cx; ++x) pts[x][cy] = '_'; else for (x = cx + 1; x < px; ++x) pts[x][cy] = '_'; } prev = curr; } for (x = 0; x < MAX; ++x) { for (y = 0; y < MAX; ++y) printf("%c", pts[y][x]); printf("\n"); } return 0;
}</lang>
- Output:
Same as Kotlin entry.
C#
<lang csharp>using System; using System.Collections.Generic; using System.Diagnostics; using System.Text;
namespace HilbertCurve {
class Program { static void Swap<T>(ref T a, ref T b) { var c = a; a = b; b = c; }
struct Point { public int x, y;
public Point(int x, int y) { this.x = x; this.y = y; }
//rotate/flip a quadrant appropriately public void Rot(int n, bool rx, bool ry) { if (!ry) { if (rx) { x = (n - 1) - x; y = (n - 1) - y; } Swap(ref x, ref y); } }
public override string ToString() { return string.Format("({0}, {1})", x, y); } }
static Point FromD(int n, int d) { var p = new Point(0, 0); int t = d;
for (int s = 1; s < n; s <<= 1) { var rx = (t & 2) != 0; var ry = ((t ^ (rx ? 1 : 0)) & 1) != 0; p.Rot(s, rx, ry); p.x += rx ? s : 0; p.y += ry ? s : 0; t >>= 2; }
return p; }
static List<Point> GetPointsForCurve(int n) { var points = new List<Point>(); int d = 0; while (d < n * n) { points.Add(FromD(n, d)); d += 1; } return points; }
static List<string> DrawCurve(List<Point> points, int n) { var canvas = new char[n, n * 3 - 2]; for (int i = 0; i < canvas.GetLength(0); i++) { for (int j = 0; j < canvas.GetLength(1); j++) { canvas[i, j] = ' '; } }
for (int i = 1; i < points.Count; i++) { var lastPoint = points[i - 1]; var curPoint = points[i]; var deltaX = curPoint.x - lastPoint.x; var deltaY = curPoint.y - lastPoint.y; if (deltaX == 0) { Debug.Assert(deltaY != 0, "Duplicate point"); //vertical line int row = Math.Max(curPoint.y, lastPoint.y); int col = curPoint.x * 3; canvas[row, col] = '|'; } else { Debug.Assert(deltaY == 0, "Duplicate point"); //horizontal line var row = curPoint.y; var col = Math.Min(curPoint.x, lastPoint.x) * 3 + 1; canvas[row, col] = '_'; canvas[row, col + 1] = '_'; } }
var lines = new List<string>(); for (int i = 0; i < canvas.GetLength(0); i++) { var sb = new StringBuilder(); for (int j = 0; j < canvas.GetLength(1); j++) { sb.Append(canvas[i, j]); } lines.Add(sb.ToString()); } return lines; }
static void Main() { for (int order = 1; order <= 5; order++) { var n = 1 << order; var points = GetPointsForCurve(n); Console.WriteLine("Hilbert curve, order={0}", order); var lines = DrawCurve(points, n); foreach (var line in lines) { Console.WriteLine(line); } Console.WriteLine(); } } }
}</lang>
- Output:
Hilbert curve, order=1 |__| Hilbert curve, order=2 __ __ __| |__ | __ | |__| |__| Hilbert curve, order=3 __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| |__ __| | |__ __ __ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__| Hilbert curve, order=4 __ __ __ __ __ __ __ __ __ __ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| Hilbert curve, order=5 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __ | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __| __| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__ | __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ | |__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__| __ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __ | |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| | |__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __| __| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__ | __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ | |__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ | |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| | |__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __| __| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__|
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <vector>
struct Point {
int x, y;
//rotate/flip a quadrant appropriately void rot(int n, bool rx, bool ry) { if (!ry) { if (rx) { x = (n - 1) - x; y = (n - 1) - y; } std::swap(x, y); } }
};
Point fromD(int n, int d) {
Point p = { 0, 0 }; bool rx, ry; int t = d; for (int s = 1; s < n; s <<= 1) { rx = ((t & 2) != 0); ry = (((t ^ (rx ? 1 : 0)) & 1) != 0); p.rot(s, rx, ry); p.x += (rx ? s : 0); p.y += (ry ? s : 0); t >>= 2; } return p;
}
std::vector<Point> getPointsForCurve(int n) {
std::vector<Point> points; for (int d = 0; d < n * n; ++d) { points.push_back(fromD(n, d)); } return points;
}
std::vector<std::string> drawCurve(const std::vector<Point> &points, int n) {
auto canvas = new char *[n]; for (size_t i = 0; i < n; i++) { canvas[i] = new char[n * 3 - 2]; std::memset(canvas[i], ' ', n * 3 - 2); }
for (int i = 1; i < points.size(); i++) { auto lastPoint = points[i - 1]; auto curPoint = points[i]; int deltaX = curPoint.x - lastPoint.x; int deltaY = curPoint.y - lastPoint.y; if (deltaX == 0) { // vertical line int row = std::max(curPoint.y, lastPoint.y); int col = curPoint.x * 3; canvas[row][col] = '|'; } else { // horizontal line int row = curPoint.y; int col = std::min(curPoint.x, lastPoint.x) * 3 + 1; canvas[row][col] = '_'; canvas[row][col + 1] = '_'; } }
std::vector<std::string> lines; for (size_t i = 0; i < n; i++) { std::string temp; temp.assign(canvas[i], n * 3 - 2); lines.push_back(temp); } return lines;
}
int main() {
for (int order = 1; order < 6; order++) { int n = 1 << order; auto points = getPointsForCurve(n); std::cout << "Hilbert curve, order=" << order << '\n'; auto lines = drawCurve(points, n); for (auto &line : lines) { std::cout << line << '\n'; } std::cout << '\n'; } return 0;
}</lang>
- Output:
Hilbert curve, order=1 |__| Hilbert curve, order=2 __ __ __| |__ | __ | |__| |__| Hilbert curve, order=3 __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| |__ __| | |__ __ __ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__| Hilbert curve, order=4 __ __ __ __ __ __ __ __ __ __ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| Hilbert curve, order=5 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __ | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __| __| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__ | __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ | |__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__| __ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __ | |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| | |__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __| __| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__ | __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ | |__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ | |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| | |__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __| __| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__|
D
<lang d>import std.stdio;
void main() {
foreach (order; 1..6) { int n = 1 << order; auto points = getPointsForCurve(n); writeln("Hilbert curve, order=", order); auto lines = drawCurve(points, n); foreach (line; lines) { writeln(line); } writeln; }
}
struct Point {
int x, y;
//rotate/flip a quadrant appropriately void rot(int n, bool rx, bool ry) { if (!ry) { if (rx) { x = (n - 1) - x; y = (n - 1) - y; }
import std.algorithm.mutation; swap(x, y); } }
int calcD(int n) { bool rx, ry; int d; for (int s = n >>> 1; s > 0; s >>>= 1) { rx = ((x & s) != 0); ry = ((y & s) != 0); d += s * s * ((rx ? 3 : 0) ^ (ry ? 1 : 0)); rot(s, rx, ry); } return d; }
void toString(scope void delegate(const(char)[]) sink) const { import std.format : formattedWrite;
sink("("); sink.formattedWrite!"%d"(x); sink(", "); sink.formattedWrite!"%d"(y); sink(")"); }
}
auto fromD(int n, int d) {
Point p; bool rx, ry; int t = d; for (int s = 1; s < n; s <<= 1) { rx = ((t & 2) != 0); ry = (((t ^ (rx ? 1 : 0)) & 1) != 0); p.rot(s, rx, ry); p.x += (rx ? s : 0); p.y += (ry ? s : 0); t >>>= 2; } return p;
}
auto getPointsForCurve(int n) {
Point[] points; for (int d; d < n * n; ++d) { points ~= fromD(n, d); } return points;
}
auto drawCurve(Point[] points, int n) {
import std.algorithm.comparison : min, max; import std.array : uninitializedArray; import std.exception : enforce;
auto canvas = uninitializedArray!(char[][])(n, n * 3 - 2); foreach (line; canvas) { line[] = ' '; }
for (int i = 1; i < points.length; ++i) { auto lastPoint = points[i - 1]; auto curPoint = points[i]; int deltaX = curPoint.x - lastPoint.x; int deltaY = curPoint.y - lastPoint.y; if (deltaX == 0) { enforce(deltaY != 0, "Duplicate point"); // vertical line int row = max(curPoint.y, lastPoint.y); int col = curPoint.x * 3; canvas[row][col] = '|'; } else { enforce(deltaY == 0, "Diagonal line"); // horizontal line int row = curPoint.y; int col = min(curPoint.x, lastPoint.x) * 3 + 1; canvas[row][col] = '_'; canvas[row][col + 1] = '_'; } }
string[] lines; foreach (row; canvas) { lines ~= row.idup; }
return lines;
}</lang>
- Output:
Hilbert curve, order=1 |__| Hilbert curve, order=2 __ __ __| |__ | __ | |__| |__| Hilbert curve, order=3 __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| |__ __| | |__ __ __ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__| Hilbert curve, order=4 __ __ __ __ __ __ __ __ __ __ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| Hilbert curve, order=5 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __ | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __| __| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__ | __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ | |__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__| __ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __ | |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| | |__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __| __| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__ | __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ | |__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ | |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| | |__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __| __| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__|
Factor
<lang factor>USING: accessors L-system ui ;
- hilbert ( L-system -- L-system )
L-parser-dialect >>commands [ 90 >>angle ] >>turtle-values "A" >>axiom { { "A" "-BF+AFA+FB-" } { "B" "+AF-BFB-FA+" } } >>rules ;
[ <L-system> hilbert "Hilbert curve" open-window ] with-ui</lang>
When using the L-system visualizer, the following controls apply:
Button | Command |
---|---|
a | zoom in |
z | zoom out |
left arrow | turn left |
right arrow | turn right |
up arrow | pitch down |
down arrow | pitch up |
q | roll left |
w | roll right |
Button | Command |
---|---|
x | iterate L-system |
Forth
<lang forth>include lib/graphics.4th
64 constant /width \ hilbert curve order^2
9 constant /length \ length of a line
variable origin \ point of origin
aka r@ lg \ get parameters from return stack aka r'@ i1 \ so define some aliases aka r"@ i2 \ to make it a bit more readable
- origin! 65536 * + origin ! ; ( n1 n2 --)
- origin@ origin @ 65536 /mod ; ( -- n1 n2)
- hilbert ( x y lg i1 i2 --)
>r >r >r lg 1 = if \ if lg equals 1 rdrop rdrop rdrop origin@ 2swap \ get point of origin /width swap - /length * >r /width swap - /length * r> 2dup origin! line \ save origin and draw line ;then
r> 2/ >r \ divide lg by 2 over over i1 lg * tuck + >r + r> lg i1 1 i2 - hilbert over over 1 i2 - lg * + swap i2 lg * + swap lg i1 i2 hilbert over over 1 i1 - lg * tuck + >r + r> lg i1 i2 hilbert i2 lg * + swap 1 i2 - lg * + swap r> 1 r> - r> hilbert
585 pic_width ! 585 pic_height ! \ set canvas size color_image 255 whiteout blue \ paint blue on white 0 dup origin! \ set point of origin 0 dup /width over dup hilbert \ hilbert curve, order=8 s" ghilbert.ppm" save_image \ save the image </lang> Output: Since Rosetta Code doesn't seem to support uploads anymore, the resulting file cannot be shown.
FreeBASIC
<lang freebasic> Dim Shared As Integer ancho = 64
Sub Hilbert(x As Integer, y As Integer, lg As Integer, i1 As Integer, i2 As Integer)
If lg = 1 Then Line - ((ancho-x) * 10, (ancho-y) * 10) Return End If lg = lg / 2 Hilbert(x+i1*lg, y+i1*lg, lg, i1, 1-i2) Hilbert(x+i2*lg, y+(1-i2)*lg, lg, i1, i2) Hilbert(x+(1-i1)*lg, y+(1-i1)*lg, lg, i1, i2) Hilbert(x+(1-i2)*lg, y+i2*lg, lg, 1-i1, i2)
End Sub
Screenres 655, 655
Hilbert(0, 0, ancho, 0, 0) End </lang>
Fōrmulæ
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
Frink
This program generates arbitrary L-systems with slight modifications (see the commmented-out list of various angles and rules.) <lang frink>// General description: // This code creates Lindenmayer rules via string manipulation // It can generate many of the examples from the Wikipedia page // discussing L-system fractals: http://en.wikipedia.org/wiki/L-system // // It does not support stochastic, context sensitive or parametric grammars // // It supports four special rules, and any number of variables in rules // f = move forward one unit // - = turn left one turn // + = turn right one turn // [ = save angle and position on a stack // ] = restore angle and position from the stack
// The turn is how far each + or - in the final rule turns to either side
turn = 90 degrees
// This is how many times the rules get applied before we draw the result
times = 5
// This is our starting string
start = "++a"
// These are the rules we apply
rules = [["f","f"],["a","-bf+afa+fb-"], ["b","+af-bfb-fa+"]]
// L-System rules pulled from Wikipedia // Dragon // 90 degrees, "fx", [["f","f"],["x","x+yf"],["y","fx-y"]]
// TerDragon // 120 degrees, "f", "f","f+f-f"
// Koch curve // 90 degrees, "f", "f","f+f-f-f+f" // use "++f" as the start to flip it over
// Sierpinski Triangle // 60 degrees, "bf", [["f","f"],["a","bf-af-b"],["b","af+bf+a"]]
// Plant // 25 degrees, "--x", [["f","ff"],["x","f-[[x]+x]+f[+fx]-x"]]
// Hilbert space filling curve // 90 degrees, "++a", [["f","f"],["a","-bf+afa+fb-"], ["b","+af-bfb-fa+"]]
// Peano-Gosper curve // 60 degrees, "x", [["f","f"],["x","x+yf++yf-fx--fxfx-yf+"], ["y","-fx+yfyf++yf+fx--fx-y"]]
// Lévy C curve // 45 degrees, "f", "f","+f--f+"
// This function will apply our rule once, using string substitutions based // on the rules we pass it // It does this in two passes to avoid problems with pairs of mutually referencing // rules such as in the Sierpinski Triangle // rules@k@1 could replace toString[k] and the entire second loop could // vanish without adversely affecting the Dragon or Koch curves.
apply_rules[rules, current] := {
n = current for k = 0 to length[rules]-1 { rep = subst[rules@k@0,toString[k],"g"] n =~ rep } for k = 0 to length[rules]-1 { rep = subst[toString[k],rules@k@1,"g"] n =~ rep } return n
}
// Here we will actually apply our rules the number of times specified current = start for i = 0 to times - 1 {
current = apply_rules[rules, current] // Uncomment this line to see the string that is being produced at each stage // println[current]
}
// Go ahead and plot the image now that we've worked it out g = new graphics g.antialiased[false] // Comment this out for non-square rules. It looks better theta = 0 degrees x = 0 y = 0 stack = new array for i = 0 to length[current]-1 {
// This produces a nice sort of rainbow effect where most colors appear // comment it out for a plain black fractal // g.color[abs[sin[i degrees]],abs[cos[i*2 degrees]],abs[sin[i*4 degrees]]]
cur = substrLen[current,i,1] if cur == "-" theta = theta - (turn) if cur == "+" theta = theta + (turn) if cur == "f" or cur == "F" { g.line[x,y,x + cos[theta],y + sin[theta]] x = x + cos[theta] y = y + sin[theta] } if cur == "[" stack.pushtheta,x,y if cur == "]" [theta,x,y] = stack.pop[]
}
g.show[] g.write["hilbert.png",512,undef] </lang>
Go
The following is based on the recursive algorithm and C code in this paper. The image produced is similar to the one linked to in the zkl example.
<lang go>package main
import "github.com/fogleman/gg"
var points []gg.Point
const width = 64
func hilbert(x, y, lg, i1, i2 int) {
if lg == 1 { px := float64(width-x) * 10 py := float64(width-y) * 10 points = append(points, gg.Point{px, py}) return } lg >>= 1 hilbert(x+i1*lg, y+i1*lg, lg, i1, 1-i2) hilbert(x+i2*lg, y+(1-i2)*lg, lg, i1, i2) hilbert(x+(1-i1)*lg, y+(1-i1)*lg, lg, i1, i2) hilbert(x+(1-i2)*lg, y+i2*lg, lg, 1-i1, i2)
}
func main() {
hilbert(0, 0, width, 0, 0) dc := gg.NewContext(650, 650) dc.SetRGB(0, 0, 0) // Black background dc.Clear() for _, p := range points { dc.LineTo(p.X, p.Y) } dc.SetHexColor("#90EE90") // Light green curve dc.SetLineWidth(1) dc.Stroke() dc.SavePNG("hilbert.png")
}</lang>
Haskell
Defines an SVG string which can be rendered in a browser. A Hilbert tree is defined in terms of a production rule, and folded to a list of points in a square of given size.
<lang haskell>import Data.Bool (bool) import Data.Tree
rule :: Char -> String rule c =
case c of 'a' -> "daab" 'b' -> "cbba" 'c' -> "bccd" 'd' -> "addc" _ -> []
vectors :: Char -> [(Int, Int)] vectors c =
case c of 'a' -> [(-1, 1), (-1, -1), (1, -1), (1, 1)] 'b' -> [(1, -1), (-1, -1), (-1, 1), (1, 1)] 'c' -> [(1, -1), (1, 1), (-1, 1), (-1, -1)] 'd' -> [(-1, 1), (1, 1), (1, -1), (-1, -1)] _ -> []
main :: IO () main = do
let w = 1024 putStrLn $ svgFromPoints w $ hilbertPoints w (hilbertTree 6)
hilbertTree :: Int -> Tree Char hilbertTree n =
let go tree = let c = rootLabel tree xs = subForest tree in Node c (bool (go <$> xs) (flip Node [] <$> rule c) (null xs)) seed = Node 'a' [] in bool seed (iterate go seed !! pred n) (0 < n)
hilbertPoints :: Int -> Tree Char -> [(Int, Int)] hilbertPoints w tree =
let go r xy tree = let d = quot r 2 f g x = g xy + (d * g x) centres = ((,) . f fst) <*> f snd <$> vectors (rootLabel tree) xs = subForest tree in bool (concat $ zipWith (go d) centres xs) centres (null xs) r = quot w 2 in go r (r, r) tree
svgFromPoints :: Int -> [(Int, Int)] -> String svgFromPoints w xys =
let sw = show w points = (unwords . fmap (((++) . show . fst) <*> ((' ' :) . show . snd))) xys in unlines [ "<svg xmlns=\"http://www.w3.org/2000/svg\"" , unwords ["width=\"512\" height=\"512\" viewBox=\"5 5", sw, sw, "\"> "] , "<path d=\"M" ++ points ++ "\" " , "stroke-width=\"2\" stroke=\"red\" fill=\"transparent\"/>" , "</svg>" ]</lang>
IS-BASIC
<lang IS-BASIC>100 PROGRAM "Hilbert.bas" 110 OPTION ANGLE DEGREES 120 GRAPHICS HIRES 2 130 LET N=5:LET P=1:LET S=11*2^(6-N) 140 PLOT 940,700,ANGLE 180; 150 CALL HILBERT(S,N,P) 160 DEF HILBERT(S,N,P) 170 IF N=0 THEN EXIT DEF 180 PLOT LEFT 90*P; 190 CALL HILBERT(S,N-1,-P) 200 PLOT FORWARD S;RIGHT 90*P; 210 CALL HILBERT(S,N-1,P) 220 PLOT FORWARD S; 230 CALL HILBERT(S,N-1,P) 240 PLOT RIGHT 90*P;FORWARD S; 250 CALL HILBERT(S,N-1,-P) 260 PLOT LEFT 90*P; 270 END DEF</lang>
J
<lang J>require'plot'
iter=: (, 1 , +@|.) @: (,~ 0j_1 ,~ 0j_1*|.) hilbert=: 3 : '0j1+(%{:) +/\0,iter ^: y
plot hilbert 5 </lang>
The idea is to represent the nth order hilbert curve as list of complex numbers that can be summed to trace the curve. The 0th order hilbert curve is an empty string. The first half of the n+1 the curve is formed by rotating the nth right by 90 degrees and reversing, appending -i and appending the nth curve. The whole n+1th curve is the first half appended to 1 appended to the conjugate of the reverse of the first half.
Java
<lang java>// Translation from https://en.wikipedia.org/wiki/Hilbert_curve
import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class HilbertCurve {
public static class Point { public int x; public int y; public Point(int x, int y) { this.x = x; this.y = y; } public String toString() { return "(" + x + ", " + y + ")"; } //rotate/flip a quadrant appropriately public void rot(int n, boolean rx, boolean ry) { if (!ry) { if (rx) { x = (n - 1) - x; y = (n - 1) - y; } //Swap x and y int t = x; x = y; y = t; } return; } public int calcD(int n) { boolean rx, ry; int d = 0; for (int s = n >>> 1; s > 0; s >>>= 1) { rx = ((x & s) != 0); ry = ((y & s) != 0); d += s * s * ((rx ? 3 : 0) ^ (ry ? 1 : 0)); rot(s, rx, ry); } return d; } }
public static Point fromD(int n, int d) { Point p = new Point(0, 0); boolean rx, ry; int t = d; for (int s = 1; s < n; s <<= 1) { rx = ((t & 2) != 0); ry = (((t ^ (rx ? 1 : 0)) & 1) != 0); p.rot(s, rx, ry); p.x += (rx ? s : 0); p.y += (ry ? s : 0); t >>>= 2; } return p; } public static List<Point> getPointsForCurve(int n) { List<Point> points = new ArrayList<Point>(); for (int d = 0; d < (n * n); d++) { Point p = fromD(n, d); points.add(p); } return points; } public static List<String> drawCurve(List<Point> points, int n) { char[][] canvas = new char[n][n * 3 - 2]; for (char[] line : canvas) { Arrays.fill(line, ' '); } for (int i = 1; i < points.size(); i++) { Point lastPoint = points.get(i - 1); Point curPoint = points.get(i); int deltaX = curPoint.x - lastPoint.x; int deltaY = curPoint.y - lastPoint.y; if (deltaX == 0) { if (deltaY == 0) { // A mistake has been made throw new IllegalStateException("Duplicate point, deltaX=" + deltaX + ", deltaY=" + deltaY); } // Vertical line int row = Math.max(curPoint.y, lastPoint.y); int col = curPoint.x * 3; canvas[row][col] = '|'; } else { if (deltaY != 0) { // A mistake has been made throw new IllegalStateException("Diagonal line, deltaX=" + deltaX + ", deltaY=" + deltaY); } // Horizontal line int row = curPoint.y; int col = Math.min(curPoint.x, lastPoint.x) * 3 + 1; canvas[row][col] = '_'; canvas[row][col + 1] = '_'; } } List<String> lines = new ArrayList<String>(); for (char[] row : canvas) { String line = new String(row); lines.add(line); } return lines; } public static void main(String... args) { for (int order = 1; order <= 5; order++) { int n = (1 << order); List<Point> points = getPointsForCurve(n); System.out.println("Hilbert curve, order=" + order); List<String> lines = drawCurve(points, n); for (String line : lines) { System.out.println(line); } System.out.println(); } return; }
}</lang>
- Output:
Hilbert curve, order=1 |__| Hilbert curve, order=2 __ __ __| |__ | __ | |__| |__| Hilbert curve, order=3 __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| |__ __| | |__ __ __ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__| Hilbert curve, order=4 __ __ __ __ __ __ __ __ __ __ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| Hilbert curve, order=5 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __ | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __| __| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__ | __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ | |__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__| __ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __ | |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| | |__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __| __| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__ | __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ | |__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ | |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| | |__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __| __| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__|
JavaScript
Imperative
An implementation of GO. Prints an SVG string that can be read in a browser. <lang javascript>const hilbert = (width, spacing, points) => (x, y, lg, i1, i2, f) => {
if (lg === 1) { const px = (width - x) * spacing; const py = (width - y) * spacing; points.push(px, py); return; } lg >>= 1; f(x + i1 * lg, y + i1 * lg, lg, i1, 1 - i2, f); f(x + i2 * lg, y + (1 - i2) * lg, lg, i1, i2, f); f(x + (1 - i1) * lg, y + (1 - i1) * lg, lg, i1, i2, f); f(x + (1 - i2) * lg, y + i2 * lg, lg, 1 - i1, i2, f); return points;
};
/**
* Draw a hilbert curve of the given order. * Outputs a svg string. Save the string as a .svg file and open in a browser. * @param {!Number} order */
const drawHilbert = order => {
if (!order || order < 1) { throw 'You need to give a valid positive integer'; } else { order = Math.floor(order); }
// Curve Constants const width = 2 ** order; const space = 10;
// SVG Setup const size = 500; const stroke = 2; const col = "red"; const fill = "transparent";
// Prep and run function const f = hilbert(width, space, []); const points = f(0, 0, width, 0, 0, f); const path = points.join(' ');
console.log( `<svg xmlns="http://www.w3.org/2000/svg" width="${size}" height="${size}" viewBox="${space / 2} ${space / 2} ${width * space} ${width * space}"> <path d="M${path}" stroke-width="${stroke}" stroke="${col}" fill="${fill}"/>
</svg>`);
};
drawHilbert(6);</lang>
Functional
A composition of pure functions which defines a Hilbert tree as the Nth application of a production rule to a seedling tree.
A list of points is derived by serialization of that tree.
Like the version above, generates an SVG string for display in a browser.
<lang JavaScript>(() => {
'use strict';
const main = () => {
// rule :: Dict Char [Char] const rule = { a: ['d', 'a', 'a', 'b'], b: ['c', 'b', 'b', 'a'], c: ['b', 'c', 'c', 'd'], d: ['a', 'd', 'd', 'c'] };
// vectors :: Dict Char [(Int, Int)] const vectors = ({ 'a': [ [-1, 1], [-1, -1], [1, -1], [1, 1] ], 'b': [ [1, -1], [-1, -1], [-1, 1], [1, 1] ], 'c': [ [1, -1], [1, 1], [-1, 1], [-1, -1] ], 'd': [ [-1, 1], [1, 1], [1, -1], [-1, -1] ] });
// hilbertCurve :: Int -> SVG string const hilbertCurve = n => { const w = 1024 return svgFromPoints(w)( hilbertPoints(w)( hilbertTree(n) ) ); }
// hilbertTree :: Int -> Tree Char const hilbertTree = n => { const go = tree => Node( tree.root, 0 < tree.nest.length ? ( map(go, tree.nest) ) : map(x => Node(x, []), rule[tree.root]) ); const seed = Node('a', []); return 0 < n ? ( take(n, iterate(go, seed)).slice(-1)[0] ) : seed; };
// hilbertPoints :: Size -> Tree Char -> [(x, y)] // hilbertPoints :: Int -> Tree Char -> [(Int, Int)] const hilbertPoints = w => tree => { const go = d => (xy, tree) => { const r = Math.floor(d / 2), centres = map( v => [ xy[0] + (r * v[0]), xy[1] + (r * v[1]) ], vectors[tree.root] ); return 0 < tree.nest.length ? concat( zipWith(go(r), centres, tree.nest) ) : centres; }; const d = Math.floor(w / 2); return go(d)([d, d], tree); };
// svgFromPoints :: Int -> [(Int, Int)] -> String const svgFromPoints = w => xys => ['<svg xmlns="http://www.w3.org/2000/svg"', `width="500" height="500" viewBox="5 5 ${w} ${w}">`, `<path d="M${concat(xys).join(' ')}" `, 'stroke-width="2" stroke="red" fill="transparent"/>', '</svg>' ].join('\n');
// TEST ------------------------------------------- console.log( hilbertCurve(6) ); };
// GENERIC FUNCTIONS ----------------------------------
// Node :: a -> [Tree a] -> Tree a const Node = (v, xs) => ({ type: 'Node', root: v, // any type of value (consistent across tree) nest: xs || [] });
// concat :: a -> [a] // concat :: [String] -> String const concat = xs => 0 < xs.length ? (() => { const unit = 'string' !== typeof xs[0] ? ( [] ) : ; return unit.concat.apply(unit, xs); })() : [];
// iterate :: (a -> a) -> a -> Gen [a] function* iterate(f, x) { let v = x; while (true) { yield(v); v = f(v); } }
// Returns Infinity over objects without finite length. // This enables zip and zipWith to choose the shorter // argument when one is non-finite, like cycle, repeat etc
// length :: [a] -> Int const length = xs => (Array.isArray(xs) || 'string' === typeof xs) ? ( xs.length ) : Infinity;
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => (Array.isArray(xs) ? ( xs ) : xs.split()).map(f);
// take :: Int -> [a] -> [a] // take :: Int -> String -> String const take = (n, xs) => 'GeneratorFunction' !== xs.constructor.constructor.name ? ( xs.slice(0, n) ) : [].concat.apply([], Array.from({ length: n }, () => { const x = xs.next(); return x.done ? [] : [x.value]; }));
// Use of `take` and `length` here allows zipping with non-finite lists // i.e. generators like cycle, repeat, iterate.
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] const zipWith = (f, xs, ys) => { const lng = Math.min(length(xs), length(ys)), as = take(lng, xs), bs = take(lng, ys); return Array.from({ length: lng }, (_, i) => f(as[i], bs[i], i)); };
// MAIN --- return main();
})();</lang>
Julia
Color graphics version using the Gtk package. <lang julia>using Gtk, Graphics, Colors
Base.isless(p1::Vec2, p2::Vec2) = (p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x)
struct Line p1::Point p2::Point end
dist(p1, p2) = sqrt((p2.y - p1.y)^2 + (p2.x - p1.x)^2) length(ln::Line) = dist(ln.p1, ln.p2) isvertical(line) = (line.p1.x == line.p2.x) ishorizontal(line) = (line.p1.y == line.p2.y)
const colorseq = [colorant"blue", colorant"red", colorant"green"] const linewidth = 1 const toporder = 3
function drawline(ctx, p1, p2, color, width)
move_to(ctx, p1.x, p1.y) set_source(ctx, color) line_to(ctx, p2.x, p2.y) set_line_width(ctx, width) stroke(ctx)
end drawline(ctx, line, color, width=linewidth) = drawline(ctx, line.p1, line.p2, color, width)
function hilbertmutateboxes(ctx, line, order, maxorder=toporder)
if line.p1 < line.p2 p1, p2 = line.p1, line.p2 else p2, p1 = line.p1, line.p2 end color = colorseq[order % 3 + 1]
d = dist(p1, p2) / 3
if ishorizontal(line) pl = Point(p1.x + d, p1.y) plu = Point(p1.x + d, p1.y - d) pld = Point(p1.x + d, p1.y + d) pr = Point(p2.x - d, p2.y) pru = Point(p2.x - d, p2.y - d) prd = Point(p2.x - d, p2.y + d) lines = [Line(plu, pl), Line(plu, pru), Line(pru, pr), Line(pr, prd), Line(pld, prd), Line(pld, pl)] else # vertical pu = Point(p1.x, p1.y + d) pul = Point(p1.x - d, p1.y + d) pur = Point(p1.x + d, p1.y + d) pd = Point(p2.x, p2.y - d) pdl = Point(p2.x - d, p2.y - d) pdr = Point(p2.x + d, p2.y - d) lines = [Line(pul, pu), Line(pul, pdl), Line(pdl, pd), Line(pu, pur), Line(pur, pdr), Line(pd, pdr)] end for li in lines drawline(ctx, li, color) end if order <= maxorder for li in lines hilbertmutateboxes(ctx, li, order + 1, maxorder) end end
end
const can = @GtkCanvas()
const win = GtkWindow(can, "Hilbert 2D", 400, 400)
@guarded draw(can) do widget
ctx = getgc(can) h = height(can) w = width(can) line = Line(Point(0, h/2), Point(w, h/2)) drawline(ctx, line, colorant"black", 2) hilbertmutateboxes(ctx, line, 0)
end
show(can)
const cond = Condition()
endit(w) = notify(cond)
signal_connect(endit, win, :destroy)
wait(cond)
</lang>
Kotlin
Terminal drawing using ASCII characters within a 96 x 96 grid - starts at top left, ends at top right.
The coordinates of the points are generated using a translation of the C code in the Wikipedia article and then scaled by a factor of 3 (n = 32). <lang scala>// Version 1.2.40
data class Point(var x: Int, var y: Int)
fun d2pt(n: Int, d: Int): Point {
var x = 0 var y = 0 var t = d var s = 1 while (s < n) { val rx = 1 and (t / 2) val ry = 1 and (t xor rx) val p = Point(x, y) rot(s, p, rx, ry) x = p.x + s * rx y = p.y + s * ry t /= 4 s *= 2 } return Point(x, y)
}
fun rot(n: Int, p: Point, rx: Int, ry: Int) {
if (ry == 0) { if (rx == 1) { p.x = n - 1 - p.x p.y = n - 1 - p.y } val t = p.x p.x = p.y p.y = t }
}
fun main(args:Array<String>) {
val n = 32 val k = 3 val pts = List(n * k) { CharArray(n * k) { ' ' } } var prev = Point(0, 0) pts[0][0] = '.' for (d in 1 until n * n) { val curr = d2pt(n, d) val cx = curr.x * k val cy = curr.y * k val px = prev.x * k val py = prev.y * k pts[cx][cy] = '.' if (cx == px ) { if (py < cy) for (y in py + 1 until cy) pts[cx][y] = '|' else for (y in cy + 1 until py) pts[cx][y] = '|' } else { if (px < cx) for (x in px + 1 until cx) pts[x][cy] = '_' else for (x in cx + 1 until px) pts[x][cy] = '_' } prev = curr } for (i in 0 until n * k) { for (j in 0 until n * k) print(pts[j][i]) println() }
}</lang>
- Output:
. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. . .__. . .__. .__. .__. .__. . .__. . .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__.__. .__.__. . .__. .__. . .__.__. .__.__. . .__. .__. . .__.__. .__.__. . | | | | | | | | | | | | .__. .__.__.__. .__. .__. .__. . .__.__. .__.__. . .__. .__. .__. .__.__.__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. . .__. . .__. .__. .__. .__. . .__. . .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__. . . .__. . .__. .__. .__. .__. .__. .__. .__. .__. . .__. . . .__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__.__. .__.__. .__.__. .__.__. .__. .__. .__. .__. .__. | | | | .__. .__. .__. .__. .__. .__.__. .__.__. .__.__. .__.__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__. . . .__. . .__. .__. .__. .__. .__. .__. .__. .__. . .__. . . .__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. . .__. . .__. .__. .__. .__. . .__. . .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__.__.__. .__. .__. .__. . .__.__. .__.__. . .__. .__. .__. .__.__.__. .__. | | | | | | | | | | | | . .__.__. .__.__. . .__. .__. . .__.__. .__.__. . .__. .__. . .__.__. .__.__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. . .__. . .__. .__. .__. .__. . .__. . .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. .__.__. . | | | | .__. .__.__. .__.__. .__.__. .__.__. .__.__.__. .__.__. .__.__. .__.__. .__.__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | . .__. . .__. .__. .__. .__. . .__. . . .__. . .__. .__. .__. .__. . .__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. . .__.__. .__.__. . .__. .__. .__. .__. . .__.__. .__.__. . .__. .__. | | | | | | | | .__. .__. . .__.__. .__.__. . .__. .__. .__. .__. . .__.__. .__.__. . .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__. . .__. .__. .__. .__. . .__. . . .__. . .__. .__. .__. .__. . .__. . | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__.__. .__.__. .__.__. .__.__. .__. .__. .__.__. .__.__. .__.__. .__.__. .__. | | | | | | | | . .__.__. .__.__. .__. .__.__. .__.__. . . .__.__. .__.__. .__. .__.__. .__.__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__.__. .__.__. . . .__.__. .__.__. . . .__.__. .__.__. . . .__.__. .__.__. . | | | | | | | | | | | | | | | | .__. .__.__.__. .__. .__. .__.__.__. .__. .__. .__.__.__. .__. .__. .__.__.__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | . .__. . . .__. . . .__. . . .__. . . .__. . . .__. . . .__. . . .__. . | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__. .__.
Lambdatalk
The output is visible in Hibert curve
<lang Scheme> 1) two twinned recursive functions
{def left {lambda {:d :n}
{if {< :n 1} then else T90 {right :d {- :n 1}} M:d T-90 {left :d {- :n 1}} M:d {left :d {- :n 1}} T-90 M:d {right :d {- :n 1}} T90}}}
{def right {lambda {:d :n}
{if {< :n 1} then else T-90 {left :d {- :n 1}} M:d T90 {right :d {- :n 1}} M:d {right :d {- :n 1}} T90 M:d {left :d {- :n 1}} T-90}}}
The word Tθ rotates the drawing direction of a pen from θ degrees and the word Md moves it on d pixels.
{def H5 {left 18 5}}
The call {def H5 {left 18 5}} produces 2387 words begining with [T90 T-90 T90 T-90 T90 M10 T-90 M10 T-90 M10 T90 M10 T90 T-90 M10 T90 M10 T90 M10 T-90 M10 T-90 M10 T90 M10 T90 M10 T-90 T90 M10 T90 M10 T-90 M10 T-90 ...]
2) the SVG context
Lambdatalk comes with a primitive, turtle, translating the previous sequence of words into a sequence of SVG points [x0 y0 x1 y2 ... xn yn] feeding the "d" attribute of a SVG path.
{def stroke
{lambda {:w :c} fill="transparent" stroke=":c" stroke-width=":w"}}
{svg
{@ width="580px" height="580px"} {path {@ d="M {turtle 10 10 0 {H5}}" {stroke 8 #000}}} {path {@ d="M {turtle 10 10 0 {H5}}" {stroke 4 #000}}} {path {@ d="M {turtle 10 10 0 {H5}}" {stroke 1 #fff}}}
} </lang>
Lua
Solved by using the Lindenmayer path, printed with Unicode, which does not show perfectly on web, but is quite nice on console. Should work with all Lua versions, used nothing special. Should work up to Hilbert(12) if your console is big enough for that.
Implemented a full line-drawing Unicode/ASCII drawing and added for the example my signature to the default axiom "A" for fun and a second Hilbert "A" at the end, because it's looking better in the display like that. The implementation of repeated commands was just an additional line of code, so why not?
Lindenmayer:
- A,B are Lindenmayer AXIOMS
Line drawing:
- +,- turn right, left
- F draw line forward
- <num> repeat the following draw command <num> times
- <any> move on canvas without drawing
<lang lua>-- any version from LuaJIT 2.0/5.1, Lua 5.2, Lua 5.3 to LuaJIT 2.1.0-beta3-readline local bit=bit32 or bit -- Lua 5.2/5.3 compatibilty -- Hilbert curve implemented by Lindenmayer system function string.hilbert(s, n) for i=1,n do s=s:gsub("[AB]",function(c) if c=="A" then c="-BF+AFA+FB-" else c="+AF-BFB-FA+" end return c end) end s=s:gsub("[AB]",""):gsub("%+%-",""):gsub("%-%+","") return s end -- Or the characters for ASCII line drawing function charor(c1, c2) local bits={ [" "]=0x0, ["╷"]=0x1, ["╶"]=0x2, ["┌"]=0x3, ["╵"]=0x4, ["│"]=0x5, ["└"]=0x6, ["├"]=0x7, ["╴"]=0x8, ["┐"]=0x9, ["─"]=0xa, ["┬"]=0xb, ["┘"]=0xc, ["┤"]=0xd, ["┴"]=0xe, ["┼"]=0xf,} local char={" ", "╷", "╶", "┌", "╵", "│", "└", "├", "╴", "┐", "─", "┬", "┘", "┤", "┴", "┼",} local b1,b2=bits[c1] or 0,bits[c2] or 0 return char[bit.bor(b1,b2)+1] end -- ASCII line drawing routine function draw(s) local char={ {"─","┘","╴","┐",}, -- r {"│","┐","╷","┌",}, -- up {"─","┌","╶","└",}, -- l {"│","└","╵","┘",}, -- down } local scr={} local move={{x=1,y=0},{x=0,y=1},{x=-1,y=0},{x=0,y=-1}} local x,y=1,1 local minx,maxx,miny,maxy=1,1,1,1 local dir,turn=0,0 s=s.."F" local rep=0 for c in s:gmatch(".") do if c=="F" then repeat if scr[y]==nil then scr[y]={} end scr[y][x]=charor(char[dir+1][turn%#char[1]+1],scr[y][x] or " ") dir = (dir+turn) % #move x, y = x+move[dir+1].x,y+move[dir+1].y maxx,maxy=math.max(maxx,x),math.max(maxy,y) minx,miny=math.min(minx,x),math.min(miny,y) turn=0 rep=rep>1 and rep-1 or 0 until rep==0 elseif c=="-" then repeat turn=turn+1 rep=rep>1 and rep-1 or 0 until rep==0 elseif c=="+" then repeat turn=turn-1 rep=rep>1 and rep-1 or 0 until rep==0 elseif c:match("%d") then -- allow repeated commands rep=rep*10+tonumber(c) else repeat x, y = x+move[dir+1].x,y+move[dir+1].y maxx,maxy=math.max(maxx,x),math.max(maxy,y) minx,miny=math.min(minx,x),math.min(miny,y) rep=rep>1 and rep-1 or 0 until rep==0 end end for i=maxy,miny,-1 do local oneline={} for x=minx,maxx do oneline[1+x-minx]=scr[i] and scr[i][x] or " " end local line=table.concat(oneline) io.write(line, "\n") end end -- MAIN -- local n=arg[1] and tonumber(arg[1]) or 3 local str=arg[2] or "A" draw(str:hilbert(n)) </lang>
- Output:
luajit hilbert.lua 4 1M9FAF-4F2+2F-2F-2F++4F-F-4F+2F+2F+2F++3F+2F+3F--4FA10F-16F-58F-16F-
┌─────────────────────────────────────────────────────────┐ │ ┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐ ┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐ │ │ │└┘││└┘││└┘││└┘│ │└┘││└┘││└┘││└┘│ │ │ └┐┌┘└┐┌┘└┐┌┘└┐┌┘ └┐┌┘└┐┌┘└┐┌┘└┐┌┘ │ │ ┌┘└──┘└┐┌┘└──┘└┐ ┌┘└──┘└┐┌┘└──┘└┐ │ │ │┌─┐┌─┐││┌─┐┌─┐│ │┌─┐┌─┐││┌─┐┌─┐│ │ │ └┘┌┘└┐└┘└┘┌┘└┐└┘ └┘┌┘└┐└┘└┘┌┘└┐└┘ │ │ ┌┐└┐┌┘┌┐┌┐└┐┌┘┌┐ ┌┐└┐┌┘┌┐┌┐└┐┌┘┌┐ │ │ │└─┘└─┘└┘└─┘└─┘│ │└─┘└─┘└┘└─┘└─┘│ │ │ └┐┌─┐┌─┐┌─┐┌─┐┌┘ └┐┌─┐┌─┐┌─┐┌─┐┌┘ │ │ ┌┘└┐└┘┌┘└┐└┘┌┘└┐ ┌┘└┐└┘┌┘└┐└┘┌┘└┐ │ │ │┌┐│┌┐└┐┌┘┌┐│┌┐│ │┌┐│┌┐└┐┌┘┌┐│┌┐│ │ │ └┘└┘│└─┘└─┘│└┘└┘╷ ╷┌─┐ └┘└┘│└─┘└─┘│└┘└┘ │ │ ┌┐┌┐│┌─┐┌─┐│┌┐┌┐│ ││ │ ┌┐┌┐│┌─┐┌─┐│┌┐┌┐ │ │ │└┘│└┘┌┘└┐└┘│└┘│├─┤├─┴┐│└┘│└┘┌┘└┐└┘│└┘│ │ │ └┐┌┘┌┐└┐┌┘┌┐└┐┌┘│ ││ │└┐┌┘┌┐└┐┌┘┌┐└┐┌┘ │ └──────────┘└─┘└─┘└─┘└─┘└─┘ └┴──┴─┘└─┘└─┘└─┘└─┘└──────────┘
Mathematica/Wolfram Language
Works with: Mathematica 11 <lang Mathematica>Graphics@HilbertCurve[4]</lang>
Nim
<lang Nim>const
Level = 4 Side = (1 shl Level) * 2 - 2
type Direction = enum E, N, W, S
const
# Strings to use according to direction. Drawings1: array[Direction, string] = ["──", " │", "──", " │"]
# Strings to use according to old and current direction. Drawings2: array[Direction, array[Direction, string]] = [["──", "─╯", " ?", "─╮"], [" ╭", " │", "─╮", " ?"], [" ?", " ╰", "──", " ╭"], [" ╰", " ?", "─╯", " │"]]
type Curve = object
grid: array[-Side..1, array[0..Side, string]] x, y: int dir, oldDir: Direction
proc newCurve(): Curve =
## Create a new curve. result.x = 0 result.y = 0 result.dir = E result.oldDir = E for row in result.grid.mitems: for item in row.mitems: item = " "
proc left(dir: var Direction) =
## Turn on the left. dir = if dir == S: E else: succ(dir)
proc right(dir: var Direction) =
## Turn on the right. dir = if dir == E: S else: pred(dir)
proc move(curve: var Curve) =
## Move to next position according to current direction. case curve.dir of E: inc curve.x of N: dec curve.y of W: dec curve.x of S: inc curve.y
proc forward(curve: var Curve) =
# Do one step: draw a corner, draw a segment and advance to next corner.
# Draw corner. curve.grid[curve.y][curve.x] = Drawings2[curve.oldDir][curve.dir] curve.move()
# Draw segment. curve.grid[curve.y][curve.x] = Drawings1[curve.dir]
# Advance to next corner. curve.move() curve.oldDir = curve.dir
- Forward reference.
proc b(curve: var Curve; level: int)
proc a(curve: var Curve; level: int) =
## "A" function. if level > 0: curve.dir.left() curve.b(level - 1) curve.forward() curve.dir.right() curve.a(level - 1) curve.forward() curve.a(level - 1) curve.dir.right() curve.forward() curve.b(level - 1) curve.dir.left()
proc b(curve: var Curve; level: int) =
## "B" function. if level > 0: curve.dir.right() curve.a(level - 1) curve.forward() curve.dir.left() curve.b(level - 1) curve.forward() curve.b(level - 1) curve.dir.left() curve.forward() curve.a(level - 1) curve.dir.right()
- Main code
var curve = newCurve()
- Draw.
curve.a(Level)
- Print.
for row in curve.grid:
for s in row: stdout.write(s) stdout.writeLine("")
</lang>
- Output:
See Algol68 version.
Perl
<lang perl>use SVG; use List::Util qw(max min);
use constant pi => 2 * atan2(1, 0);
- Compute the curve with a Lindemayer-system
%rules = (
A => '-BF+AFA+FB-', B => '+AF-BFB-FA+'
); $hilbert = 'A'; $hilbert =~ s/([AB])/$rules{$1}/eg for 1..6;
- Draw the curve in SVG
($x, $y) = (0, 0); $theta = pi/2; $r = 5;
for (split //, $hilbert) {
if (/F/) { push @X, sprintf "%.0f", $x; push @Y, sprintf "%.0f", $y; $x += $r * cos($theta); $y += $r * sin($theta); } elsif (/\+/) { $theta += pi/2; } elsif (/\-/) { $theta -= pi/2; }
}
$max = max(@X,@Y); $xt = -min(@X)+10; $yt = -min(@Y)+10; $svg = SVG->new(width=>$max+20, height=>$max+20); $points = $svg->get_path(x=>\@X, y=>\@Y, -type=>'polyline'); $svg->rect(width=>"100%", height=>"100%", style=>{'fill'=>'black'}); $svg->polyline(%$points, style=>{'stroke'=>'orange', 'stroke-width'=>1}, transform=>"translate($xt,$yt)");
open $fh, '>', 'hilbert_curve.svg'; print $fh $svg->xmlify(-namespace=>'svg'); close $fh;</lang> Hilbert curve (offsite image)
Phix
<lang Phix>-- demo\rosetta\hilbert_curve.exw include pGUI.e
Ihandle dlg, canvas cdCanvas cddbuffer, cdcanvas
constant width = 64
sequence points = {}
procedure hilbert(integer x, y, lg, i1, i2)
if lg=1 then integer px := (width-x) * 10, py := (width-y) * 10 points = append(points, {px, py}) return end if lg /= 2 hilbert(x+i1*lg, y+i1*lg, lg, i1, 1-i2) hilbert(x+i2*lg, y+(1-i2)*lg, lg, i1, i2) hilbert(x+(1-i1)*lg, y+(1-i1)*lg, lg, i1, i2) hilbert(x+(1-i2)*lg, y+i2*lg, lg, 1-i1, i2)
end procedure
function redraw_cb(Ihandle /*ih*/, integer /*posx*/, integer /*posy*/)
cdCanvasActivate(cddbuffer) cdCanvasBegin(cddbuffer, CD_OPEN_LINES) for i=1 to length(points) do integer {x,y} = points[i] cdCanvasVertex(cddbuffer, x, y) end for cdCanvasEnd(cddbuffer) cdCanvasFlush(cddbuffer) return IUP_DEFAULT
end function
function map_cb(Ihandle ih)
cdcanvas = cdCreateCanvas(CD_IUP, ih) cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas) cdCanvasSetBackground(cddbuffer, CD_WHITE) cdCanvasSetForeground(cddbuffer, CD_MAGENTA) return IUP_DEFAULT
end function
procedure main()
hilbert(0, 0, width, 0, 0) IupOpen() canvas = IupCanvas(NULL) IupSetAttribute(canvas, "RASTERSIZE", "655x655") IupSetCallback(canvas, "MAP_CB", Icallback("map_cb")) dlg = IupDialog(canvas) IupSetAttribute(dlg, "TITLE", "Hilbert Curve") IupSetAttribute(dlg, "DIALOGFRAME", "YES") -- no resize here IupSetCallback(canvas, "ACTION", Icallback("redraw_cb")) IupMap(dlg) IupShowXY(dlg,IUP_CENTER,IUP_CENTER) IupMainLoop() IupClose()
end procedure main()</lang>
Processing
<lang java>int iterations = 7; float strokeLen = 600; int angleDeg = 90; String axiom = "L"; StringDict rules = new StringDict(); String sentence = axiom; int xo, yo;
void setup() {
size(700, 700); xo= 50; yo = height - 50; strokeWeight(1); noFill(); rules.set("L", "+RF-LFL-FR+"); rules.set("R", "-LF+RFR+FL-"); generate(iterations);
}
void draw() {
background(0); translate(xo, yo); plot(radians(angleDeg));
}
void generate(int n) {
for (int i=0; i < n; i++) { strokeLen *= 0.5; String nextSentence = ""; for (int j=0; j < sentence.length(); j++) { char c = sentence.charAt(j); String ruleResult = rules.get(str(c), str(c)); nextSentence += ruleResult; } sentence = nextSentence; }
}
void plot(float angle) {
for (int i=0; i < sentence.length(); i++) { char c = sentence.charAt(i); if (c == 'F') { stroke(255); line(0, 0, 0, -strokeLen); translate(0, -strokeLen); } else if (c == '+') { rotate(angle); } else if (c == '-') { rotate(-angle); } }
}
void keyPressed() {
if (key == '-') { angleDeg -= 1; println("Angle: " + angleDeg); } if (key == '=' || key == '+') { angleDeg += 1; println("Angle: " + angleDeg); } if (key == 'a') { strokeLen *= 2; } if (key == 'z') { strokeLen /= 2; } if (keyCode == LEFT) { xo -= 25; } if (keyCode == RIGHT) { xo += 25; } if (keyCode == UP) { yo -= 25; } if (keyCode == DOWN) { yo += 25; }
}</lang>
Processing Python mode
<lang python>iterations = 7 stroke_len = 600 angle_deg = 90 axiom = 'L' sentence = axiom rules = {
'L': '+RF-LFL-FR+', 'R': '-LF+RFR+FL-',
}
def setup():
size(700, 700) global xo, yo xo, yo = 50, height - 50 strokeWeight(1) noFill() generate(iterations)
def draw():
background(0) translate(xo, yo) plot(radians(angle_deg))
def generate(n):
global stroke_len, sentence for _ in range(n): stroke_len *= 0.5 next_sentence = for c in sentence: next_sentence += rules.get(c, c) sentence = next_sentence
def plot(angle):
for c in sentence: if c == 'F': stroke(255) line(0, 0, 0, -stroke_len) translate(0, -stroke_len) elif c == '+': rotate(angle) elif c == '-': rotate(-angle)
def keyPressed():
global angle_deg, xo, yo, stroke_len if key == '-': angle_deg -= 5 print(angle_deg) if str(key) in "=+": angle_deg += 5 print(angle_deg) if key == 'a': stroke_len *= 2 if key == 'z': stroke_len /= 2 if keyCode == LEFT: xo -= 50 if keyCode == RIGHT: xo += 50 if keyCode == UP: yo -= 50 if keyCode == DOWN: yo += 50</lang>
Python
Functional
Composition of pure functions, with type comments for the reader rather than the compiler.
An SVG path is serialised from the Nth application of re-write rules to a Hilbert tree structure.
(To view the Hilbert curve, save the output SVG text in a file with an appropriate extension (e.g. .svg), and open it with a browser).
<lang Python>Hilbert curve
from itertools import (chain, islice)
- hilbertCurve :: Int -> SVG String
def hilbertCurve(n):
An SVG string representing a Hilbert curve of degree n. w = 1024 return svgFromPoints(w)( hilbertPoints(w)( hilbertTree(n) ) )
- hilbertTree :: Int -> Tree Char
def hilbertTree(n):
Nth application of a rule to a seedling tree.
# rule :: Dict Char [Char] rule = { 'a': ['d', 'a', 'a', 'b'], 'b': ['c', 'b', 'b', 'a'], 'c': ['b', 'c', 'c', 'd'], 'd': ['a', 'd', 'd', 'c'] }
# go :: Tree Char -> Tree Char def go(tree): c = tree['root'] xs = tree['nest'] return Node(c)( map(go, xs) if xs else map( flip(Node)([]), rule[c] ) ) seed = Node('a')([]) return list(islice( iterate(go)(seed), n ))[-1] if 0 < n else seed
- hilbertPoints :: Int -> Tree Char -> [(Int, Int)]
def hilbertPoints(w):
Serialization of a tree to a list of points bounded by a square of side w.
# vectors :: Dict Char [(Int, Int)] vectors = { 'a': [(-1, 1), (-1, -1), (1, -1), (1, 1)], 'b': [(1, -1), (-1, -1), (-1, 1), (1, 1)], 'c': [(1, -1), (1, 1), (-1, 1), (-1, -1)], 'd': [(-1, 1), (1, 1), (1, -1), (-1, -1)] }
# points :: Int -> ((Int, Int), Tree Char) -> [(Int, Int)] def points(d): Size -> Centre of a Hilbert subtree -> All subtree points def go(xy, tree): r = d // 2
def deltas(v): return ( xy[0] + (r * v[0]), xy[1] + (r * v[1]) ) centres = map(deltas, vectors[tree['root']]) return chain.from_iterable( map(points(r), centres, tree['nest']) ) if tree['nest'] else centres return go
d = w // 2 return lambda tree: list(points(d)((d, d), tree))
- svgFromPoints :: Int -> [(Int, Int)] -> SVG String
def svgFromPoints(w):
Width of square canvas -> Point list -> SVG string
def go(xys): def points(xy): return str(xy[0]) + ' ' + str(xy[1]) xs = ' '.join(map(points, xys)) return '\n'.join( ['<svg xmlns="http://www.w3.org/2000/svg"', f'width="512" height="512" viewBox="5 5 {w} {w}">', f'<path d="M{xs}" ', 'stroke-width="2" stroke="red" fill="transparent"/>', '</svg>' ] ) return go
- ------------------------- TEST --------------------------
def main():
Testing generation of the SVG for a Hilbert curve print( hilbertCurve(6) )
- ------------------- GENERIC FUNCTIONS -------------------
- Node :: a -> [Tree a] -> Tree a
def Node(v):
Contructor for a Tree node which connects a value of some kind to a list of zero or more child trees. return lambda xs: {'type': 'Node', 'root': v, 'nest': xs}
- flip :: (a -> b -> c) -> b -> a -> c
def flip(f):
The (curried or uncurried) function f with its arguments reversed. return lambda a: lambda b: f(b)(a)
- iterate :: (a -> a) -> a -> Gen [a]
def iterate(f):
An infinite list of repeated applications of f to x. def go(x): v = x while True: yield v v = f(v) return go
- TEST ---------------------------------------------------
if __name__ == '__main__':
main()</lang>
Recursive
<lang Python> import matplotlib.pyplot as plt import numpy as np import turtle as tt
- dictionary containing the first order hilbert curves
base_shape = {'u': [np.array([0, 1]), np.array([1, 0]), np.array([0, -1])],
'd': [np.array([0, -1]), np.array([-1, 0]), np.array([0, 1])], 'r': [np.array([1, 0]), np.array([0, 1]), np.array([-1, 0])], 'l': [np.array([-1, 0]), np.array([0, -1]), np.array([1, 0])]}
def hilbert_curve(order, orientation):
""" Recursively creates the structure for a hilbert curve of given order """ if order > 1: if orientation == 'u': return hilbert_curve(order - 1, 'r') + [np.array([0, 1])] + \ hilbert_curve(order - 1, 'u') + [np.array([1, 0])] + \ hilbert_curve(order - 1, 'u') + [np.array([0, -1])] + \ hilbert_curve(order - 1, 'l') elif orientation == 'd': return hilbert_curve(order - 1, 'l') + [np.array([0, -1])] + \ hilbert_curve(order - 1, 'd') + [np.array([-1, 0])] + \ hilbert_curve(order - 1, 'd') + [np.array([0, 1])] + \ hilbert_curve(order - 1, 'r') elif orientation == 'r': return hilbert_curve(order - 1, 'u') + [np.array([1, 0])] + \ hilbert_curve(order - 1, 'r') + [np.array([0, 1])] + \ hilbert_curve(order - 1, 'r') + [np.array([-1, 0])] + \ hilbert_curve(order - 1, 'd') else: return hilbert_curve(order - 1, 'd') + [np.array([-1, 0])] + \ hilbert_curve(order - 1, 'l') + [np.array([0, -1])] + \ hilbert_curve(order - 1, 'l') + [np.array([1, 0])] + \ hilbert_curve(order - 1, 'u') else: return base_shape[orientation]
- test the functions
if __name__ == '__main__':
order = 8 curve = hilbert_curve(order, 'u') curve = np.array(curve) * 4 cumulative_curve = np.array([np.sum(curve[:i], 0) for i in range(len(curve)+1)]) # plot curve using plt plt.plot(cumulative_curve[:, 0], cumulative_curve[:, 1]) # draw curve using turtle graphics tt.setup(1920, 1000) tt.pu() tt.goto(-950, -490) tt.pd() tt.speed(0) for item in curve: tt.goto(tt.pos()[0] + item[0], tt.pos()[1] + item[1]) tt.done()
</lang>
QB64
<lang qb64>_Title "Hilbert Curve" Dim Shared As Integer sw, sh, wide, cell
wide = 128: cell = 4 sw = wide * cell + cell sh = sw
Screen _NewImage(sw, sh, 8) Cls , 15: Color 0 PSet (wide * cell, wide * cell)
Call Hilbert(0, 0, wide, 0, 0)
Sleep System
Sub Hilbert (x As Integer, y As Integer, lg As Integer, p As Integer, q As Integer)
Dim As Integer iL, iX, iY iL = lg: iX = x: iY = y If iL = 1 Then Line -((wide - iX) * cell, (wide - iY) * cell) Exit Sub End If iL = iL \ 2 Call Hilbert(iX + p * iL, iY + p * iL, iL, p, 1 - q) Call Hilbert(iX + q * iL, iY + (1 - q) * iL, iL, p, q) Call Hilbert(iX + (1 - p) * iL, iY + (1 - p) * iL, iL, p, q) Call Hilbert(iX + (1 - q) * iL, iY + q * iL, iL, 1 - p, q)
End Sub</lang>
Racket
<lang racket>#lang racket
(require racket/draw)
(define rules '([A . (- B F + A F A + F B -)]
[B . (+ A F - B F B - F A +)]))
(define (get-cmds n cmd)
(cond [(= 0 n) (list cmd)] [else (append-map (curry get-cmds (sub1 n)) (dict-ref rules cmd (list cmd)))]))
(define (make-curve DIM N R OFFSET COLOR BACKGROUND-COLOR)
(define target (make-bitmap DIM DIM)) (define dc (new bitmap-dc% [bitmap target])) (send dc set-background BACKGROUND-COLOR) (send dc set-pen COLOR 1 'solid) (send dc clear) (for/fold ([x 0] [y 0] [θ (/ pi 2)]) ([cmd (in-list (get-cmds N 'A))]) (define (draw/values x* y* θ*) (send/apply dc draw-line (map (curry + OFFSET) (list x y x* y*))) (values x* y* θ*)) (match cmd ['F (draw/values (+ x (* R (cos θ))) (+ y (* R (sin θ))) θ)] ['+ (values x y (+ θ (/ pi 2)))] ['- (values x y (- θ (/ pi 2)))] [_ (values x y θ)])) target)
(make-curve 500 6 7 30 (make-color 255 255 0) (make-color 0 0 0))</lang>
Raku
(formerly Perl 6)
<lang perl6>use SVG;
role Lindenmayer {
has %.rules; method succ { self.comb.map( { %!rules{$^c} // $c } ).join but Lindenmayer(%!rules) }
}
my $hilbert = 'A' but Lindenmayer( { A => '-BF+AFA+FB-', B => '+AF-BFB-FA+' } );
$hilbert++ xx 7; my @points = (647, 13);
for $hilbert.comb {
state ($x, $y) = @points[0,1]; state $d = -5 - 0i; when 'F' { @points.append: ($x += $d.re).round(1), ($y += $d.im).round(1) } when /< + - >/ { $d *= "{$_}1i" } default { }
}
say SVG.serialize(
svg => [ :660width, :660height, :style<stroke:blue>, :rect[:width<100%>, :height<100%>, :fill<white>], :polyline[ :points(@points.join: ','), :fill<white> ], ],
);</lang> See: Hilbert curve
There is a variation of a Hilbert curve known as a Moore curve which is essentially 4 Hilbert curves joined together in a loop. <lang perl6>use SVG;
role Lindenmayer {
has %.rules; method succ { self.comb.map( { %!rules{$^c} // $c } ).join but Lindenmayer(%!rules) }
}
my $moore = 'AFA+F+AFA' but Lindenmayer( { A => '-BF+AFA+FB-', B => '+AF-BFB-FA+' } );
$moore++ xx 6; my @points = (327, 647);
for $moore.comb {
state ($x, $y) = @points[0,1]; state $d = 0 - 5i; when 'F' { @points.append: ($x += $d.re).round(1), ($y += $d.im).round(1) } when /< + - >/ { $d *= "{$_}1i" } default { }
}
say SVG.serialize(
svg => [ :660width, :660height, :style<stroke:darkviolet>, :rect[:width<100%>, :height<100%>, :fill<white>], :polyline[ :points(@points.join: ','), :fill<white> ], ],
);</lang> See: Moore curve
Ring
<lang ring>
- Project : Hilbert curve
load "guilib.ring"
paint = null x1 = 0 y1 = 0
new qapp
{ win1 = new qwidget() { setwindowtitle("Hilbert curve") setgeometry(100,100,400,500) label1 = new qlabel(win1) { setgeometry(10,10,400,400) settext("") } new qpushbutton(win1) { setgeometry(150,400,100,30) settext("draw") setclickevent("draw()") } show() } exec() }
func draw
p1 = new qpicture() color = new qcolor() { setrgb(0,0,255,255) } pen = new qpen() { setcolor(color) setwidth(1) } paint = new qpainter() { begin(p1) setpen(pen)
x1 = 0.5 y1 = 0.5 hilbert(0, 0, 200, 0, 0, 200, 4)
endpaint() } label1 { setpicture(p1) show() }
func hilbert (x, y, xi, xj, yi, yj, n)
cur = new QCursor() { setpos(100, 100) }
if (n <= 0) drawtoline(x + (xi + yi)/2, y + (xj + yj)/2) else hilbert(x, y, yi/2, yj/2, xi/2, xj/2, n-1) hilbert(x+xi/2, y+xj/2 , xi/2, xj/2, yi/2, yj/2, n-1) hilbert(x+xi/2+yi/2, y+xj/2+yj/2, xi/2, xj/2, yi/2, yj/2, n-1); hilbert(x+xi/2+yi, y+xj/2+yj, -yi/2,-yj/2, -xi/2, -xj/2, n-1) ok
func drawtoline x2, y2
paint.drawline(x1, y1, x2, y2) x1 = x2 y1 = y2
</lang> Output image: Hilbert curve
Ruby
Implemented as a Lindenmayer System, depends on JRuby or JRubyComplete
<lang Ruby>
- frozen_string_literal: true
load_library :grammar attr_reader :hilbert def settings
size 600, 600
end
def setup
sketch_title '2D Hilbert' @hilbert = Hilbert.new hilbert.create_grammar 5 no_loop
end
def draw
background 0 hilbert.render
end
Turtle = Struct.new(:x, :y, :theta)
- Hilbert Class has access to Sketch methods eg :line, :width, :height
class Hilbert
include Processing::Proxy
attr_reader :grammar, :axiom, :draw_length, :production, :turtle DELTA = 90.radians def initialize @axiom = 'FL' @grammar = Grammar.new( axiom, 'L' => '+RF-LFL-FR+', 'R' => '-LF+RFR+FL-' ) @draw_length = 200 stroke 0, 255, 0 stroke_weight 2 @turtle = Turtle.new(width / 9, height / 9, 0) end
def render production.scan(/./) do |element| case element when 'F' # NB NOT using affine transforms draw_line(turtle) when '+' turtle.theta += DELTA when '-' turtle.theta -= DELTA when 'L' when 'R' else puts 'Grammar not recognized' end end end
def draw_line(turtle) x_temp = turtle.x y_temp = turtle.y turtle.x += draw_length * Math.cos(turtle.theta) turtle.y += draw_length * Math.sin(turtle.theta) line(x_temp, y_temp, turtle.x, turtle.y) end
############################## # create grammar from axiom and # rules (adjust scale) ##############################
def create_grammar(gen) @draw_length *= 0.6**gen @production = @grammar.generate gen end
end </lang>
The grammar library:-
<lang ruby>
- common library class for lsystems in JRubyArt
class Grammar
attr_reader :axiom, :rules def initialize(axiom, rules) @axiom = axiom @rules = rules end
def apply_rules(prod) prod.gsub(/./) { |token| rules.fetch(token, token) } end
def generate(gen) return axiom if gen.zero?
prod = axiom gen.times do prod = apply_rules(prod) end prod end
end </lang>
Rust
Output is a file in SVG format. Implemented using a Lindenmayer system as per the Wikipedia page. <lang rust>// [dependencies] // svg = "0.8.0"
use svg::node::element::path::Data; use svg::node::element::Path;
struct HilbertCurve {
current_x: f64, current_y: f64, current_angle: i32, line_length: f64,
}
impl HilbertCurve {
fn new(x: f64, y: f64, length: f64, angle: i32) -> HilbertCurve { HilbertCurve { current_x: x, current_y: y, current_angle: angle, line_length: length, } } fn rewrite(order: usize) -> String { let mut str = String::from("A"); for _ in 0..order { let mut tmp = String::new(); for ch in str.chars() { match ch { 'A' => tmp.push_str("-BF+AFA+FB-"), 'B' => tmp.push_str("+AF-BFB-FA+"), _ => tmp.push(ch), } } str = tmp; } str } fn execute(&mut self, order: usize) -> Path { let mut data = Data::new().move_to((self.current_x, self.current_y)); for ch in HilbertCurve::rewrite(order).chars() { match ch { 'F' => data = self.draw_line(data), '+' => self.turn(90), '-' => self.turn(-90), _ => {} } } Path::new() .set("fill", "none") .set("stroke", "black") .set("stroke-width", "1") .set("d", data) } fn draw_line(&mut self, data: Data) -> Data { let theta = (self.current_angle as f64).to_radians(); self.current_x += self.line_length * theta.cos(); self.current_y -= self.line_length * theta.sin(); data.line_to((self.current_x, self.current_y)) } fn turn(&mut self, angle: i32) { self.current_angle = (self.current_angle + angle) % 360; } fn save(file: &str, size: usize, order: usize) -> std::io::Result<()> { use svg::node::element::Rectangle; let x = 10.0; let y = 10.0; let rect = Rectangle::new() .set("width", "100%") .set("height", "100%") .set("fill", "white"); let mut hilbert = HilbertCurve::new(x, y, 10.0, 0); let document = svg::Document::new() .set("width", size) .set("height", size) .add(rect) .add(hilbert.execute(order)); svg::save(file, &document) }
}
fn main() {
HilbertCurve::save("hilbert_curve.svg", 650, 6).unwrap();
}</lang>
- Output:
See: hilbert_curve.svg (offsite SVG image)
Scala
Scala.js
<lang Scala>@js.annotation.JSExportTopLevel("ScalaFiddle") object ScalaFiddle {
// $FiddleStart import scala.util.Random
case class Point(x: Int, y: Int)
def xy2d(order: Int, d: Int): Point = { def rot(order: Int, p: Point, rx: Int, ry: Int): Point = { val np = if (rx == 1) Point(order - 1 - p.x, order - 1 - p.y) else p if (ry == 0) Point(np.y, np.x) else p }
@scala.annotation.tailrec def iter(rx: Int, ry: Int, s: Int, t: Int, p: Point): Point = { if (s < order) { val _rx = 1 & (t / 2) val _ry = 1 & (t ^ _rx) val temp = rot(s, p, _rx, _ry) iter(_rx, _ry, s * 2, t / 4, Point(temp.x + s * _rx, temp.y + s * _ry)) } else p }
iter(0, 0, 1, d, Point(0, 0)) }
def randomColor = s"rgb(${Random.nextInt(240)}, ${Random.nextInt(240)}, ${Random.nextInt(240)})"
val order = 64 val factor = math.min(Fiddle.canvas.height, Fiddle.canvas.width) / order.toDouble val maxD = order * order var d = 0 Fiddle.draw.strokeStyle = randomColor Fiddle.draw.lineWidth = 2 Fiddle.draw.lineCap = "square"
Fiddle.schedule(10) { val h = xy2d(order, d) Fiddle.draw.lineTo(h.x * factor, h.y * factor) Fiddle.draw.stroke if ({d += 1; d >= maxD}) {d = 1; Fiddle.draw.strokeStyle = randomColor} Fiddle.draw.beginPath Fiddle.draw.moveTo(h.x * factor, h.y * factor) } // $FiddleEnd
}</lang>
- Output:
Best seen running in your browser by ScalaFiddle (ES aka JavaScript, non JVM).
Seed7
<lang seed7>$ include "seed7_05.s7i";
include "draw.s7i"; include "keybd.s7i";
const integer: delta is 8;
const proc: drawDown (inout integer: x, inout integer: y, in integer: n) is forward; const proc: drawUp (inout integer: x, inout integer: y, in integer: n) is forward;
const proc: drawRight (inout integer: x, inout integer: y, in integer: n) is func
begin if n > 0 then drawDown(x, y, pred(n)); line(x, y, 0, delta, white); y +:= delta; drawRight(x, y, pred(n)); line(x, y, delta, 0, white); x +:= delta; drawRight(x, y, pred(n)); line(x, y, 0, -delta, white); y -:= delta; drawUp(x, y, pred(n)); end if; end func;
const proc: drawLeft (inout integer: x, inout integer: y, in integer: n) is func
begin if n > 0 then drawUp(x, y, pred(n)); line(x, y, 0, -delta, white); y -:= delta; drawLeft(x, y, pred(n)); line(x, y, -delta, 0, white); x -:= delta; drawLeft(x, y, pred(n)); line(x, y, 0, delta, white); y +:= delta; drawDown(x, y, pred(n)); end if; end func;
const proc: drawDown (inout integer: x, inout integer: y, in integer: n) is func
begin if n > 0 then drawRight(x, y, pred(n)); line(x, y, delta, 0, white); x +:= delta; drawDown(x, y, pred(n)); line(x, y, 0, delta, white); y +:= delta; drawDown(x, y, pred(n)); line(x, y, -delta, 0, white); x -:= delta; drawLeft(x, y, pred(n)); end if; end func;
const proc: drawUp (inout integer: x, inout integer: y, in integer: n) is func
begin if n > 0 then drawLeft(x, y, pred(n)); line(x, y, -delta, 0, white); x -:= delta; drawUp(x, y, pred(n)); line(x, y, 0, -delta, white); y -:= delta; drawUp(x, y, pred(n)); line(x, y, delta, 0, white); x +:= delta; drawRight(x, y, pred(n)); end if; end func;
const proc: main is func
local var integer: x is 11; var integer: y is 11; begin screen(526, 526); KEYBOARD := GRAPH_KEYBOARD; drawRight(x, y, 6); readln(KEYBOARD); end func;</lang>
Sidef
Generic implementation of the Lindenmayer system: <lang ruby>require('Image::Magick')
class Turtle(
x = 500, y = 500, angle = 0, scale = 1, mirror = 1, xoff = 0, yoff = 0, color = 'black',
) {
has im = %O<Image::Magick>.new(size => "#{x}x#{y}")
method init { angle.deg2rad! im.ReadImage('canvas:white') }
method forward(r) { var (newx, newy) = (x + r*sin(angle), y + r*-cos(angle))
im.Draw( primitive => 'line', points => join(' ', round(x * scale + xoff), round(y * scale + yoff), round(newx * scale + xoff), round(newy * scale + yoff), ), stroke => color, strokewidth => 1, )
(x, y) = (newx, newy) }
method save_as(filename) { im.Write(filename) }
method turn(theta) { angle += theta*mirror }
method state { [x, y, angle, mirror] }
method setstate(state) { (x, y, angle, mirror) = state... }
method mirror { mirror.neg! }
}
class LSystem(
angle = 90, scale = 1, xoff = 0, yoff = 0, len = 5, color = 'black', width = 500, height = 500, turn = 0,
) {
method execute(string, repetitions, filename, rules) {
var theta = angle.deg2rad var turtle = Turtle( x: width, y: height, angle: turn, scale: scale, color: color, xoff: xoff, yoff: yoff, )
var stack = [] var table = Hash( '+' => { turtle.turn(theta) }, '-' => { turtle.turn(-theta) }, ':' => { turtle.mirror }, '[' => { stack.push(turtle.state) }, ']' => { turtle.setstate(stack.pop) }, )
repetitions.times { string.gsub!(/(.)/, {|c| rules{c} \\ c }) }
string.each_char { |c| if (table.contains(c)) { table{c}.run } elsif (c.is_uppercase) { turtle.forward(len) } }
turtle.save_as(filename) }
}</lang>
Generating the Hilbert curve: <lang ruby>var rules = Hash(
a => '-bF+aFa+Fb-', b => '+aF-bFb-Fa+',
)
var lsys = LSystem(
width: 600, height: 600,
xoff: -50, yoff: -50,
len: 8, angle: 90, color: 'dark green',
)
lsys.execute('a', 6, "hilbert_curve.png", rules)</lang> Output image: Hilbert curve
Vala
<lang vala>struct Point{
int x; int y; Point(int px,int py){ x=px; y=py; }
}
public class Hilbert : Gtk.DrawingArea {
private int it = 1; private Point[] points; private const int WINSIZE = 300;
public Hilbert() { set_size_request(WINSIZE, WINSIZE); }
public void button_toggled_cb(Gtk.ToggleButton button){ if(button.get_active()){ it = int.parse(button.get_label()); redraw_canvas(); } }
public override bool draw(Cairo.Context cr){ int border_size = 20; int unit = (WINSIZE - 2 * border_size)/((1<<it)-1);
//adjust border_size to center the drawing border_size = border_size + (WINSIZE - 2 * border_size - unit * ((1<<it)-1)) / 2;
//white background cr.rectangle(0, 0, WINSIZE, WINSIZE); cr.set_source_rgb(1, 1, 1); cr.fill_preserve(); cr.stroke();
points = {}; hilbert(0, 0, 1<<it, 0, 0);
//magenta lines cr.set_source_rgb(1, 0, 1);
// move to first point Point point = translate(border_size, WINSIZE, unit*points[0].x, unit*points[0].y); cr.move_to(point.x, point.y);
foreach(Point i in points[1:points.length]){ point = translate(border_size, WINSIZE, unit*i.x, unit*i.y); cr.line_to(point.x, point.y); } cr.stroke(); return false; }
private Point translate(int border_size, int size, int x, int y){ return Point(border_size + x,size - border_size - y); }
private void hilbert(int x, int y, int lg, int i1, int i2) { if (lg == 1) { points += Point(x,y); return; } lg >>= 1; hilbert(x+i1*lg, y+i1*lg, lg, i1, 1-i2); hilbert(x+i2*lg, y+(1-i2)*lg, lg, i1, i2); hilbert(x+(1-i1)*lg, y+(1-i1)*lg, lg, i1, i2); hilbert(x+(1-i2)*lg, y+i2*lg, lg, 1-i1, i2); }
private void redraw_canvas(){ var window = get_window(); if (window == null)return; window.invalidate_region(window.get_clip_region(), true); }
}
int main(string[] args){
Gtk.init (ref args);
var window = new Gtk.Window(); window.title = "Rosetta Code / Hilbert"; window.window_position = Gtk.WindowPosition.CENTER; window.destroy.connect(Gtk.main_quit); window.set_resizable(false);
var label = new Gtk.Label("Iterations:");
// create radio buttons to select the number of iterations var rb1 = new Gtk.RadioButton(null); rb1.set_label("1"); var rb2 = new Gtk.RadioButton.with_label_from_widget(rb1, "2"); var rb3 = new Gtk.RadioButton.with_label_from_widget(rb1, "3"); var rb4 = new Gtk.RadioButton.with_label_from_widget(rb1, "4"); var rb5 = new Gtk.RadioButton.with_label_from_widget(rb1, "5");
var hilbert = new Hilbert();
rb1.toggled.connect(hilbert.button_toggled_cb); rb2.toggled.connect(hilbert.button_toggled_cb); rb3.toggled.connect(hilbert.button_toggled_cb); rb4.toggled.connect(hilbert.button_toggled_cb); rb5.toggled.connect(hilbert.button_toggled_cb);
var box = new Gtk.Box(Gtk.Orientation.HORIZONTAL, 0); box.pack_start(label, false, false, 5); box.pack_start(rb1, false, false, 0); box.pack_start(rb2, false, false, 0); box.pack_start(rb3, false, false, 0); box.pack_start(rb4, false, false, 0); box.pack_start(rb5, false, false, 0);
var grid = new Gtk.Grid(); grid.attach(box, 0, 0, 1, 1); grid.attach(hilbert, 0, 1, 1, 1); grid.set_border_width(5); grid.set_row_spacing(5);
window.add(grid); window.show_all();
//initialise the drawing with iteration = 4 rb4.set_active(true);
Gtk.main(); return 0;
}</lang>
Visual Basic .NET
<lang vbnet>Imports System.Text
Module Module1
Sub Swap(Of T)(ByRef a As T, ByRef b As T) Dim c = a a = b b = c End Sub
Structure Point Dim x As Integer Dim y As Integer
'rotate/flip a quadrant appropriately Sub Rot(n As Integer, rx As Boolean, ry As Boolean) If Not ry Then If rx Then x = (n - 1) - x y = (n - 1) - y End If Swap(x, y) End If End Sub
Public Overrides Function ToString() As String Return String.Format("({0}, {1})", x, y) End Function End Structure
Function FromD(n As Integer, d As Integer) As Point Dim p As Point Dim rx As Boolean Dim ry As Boolean Dim t = d Dim s = 1 While s < n rx = ((t And 2) <> 0) ry = (((t Xor If(rx, 1, 0)) And 1) <> 0) p.Rot(s, rx, ry) p.x += If(rx, s, 0) p.y += If(ry, s, 0) t >>= 2
s <<= 1 End While Return p End Function
Function GetPointsForCurve(n As Integer) As List(Of Point) Dim points As New List(Of Point) Dim d = 0 While d < n * n points.Add(FromD(n, d)) d += 1 End While Return points End Function
Function DrawCurve(points As List(Of Point), n As Integer) As List(Of String) Dim canvas(n, n * 3 - 2) As Char For i = 1 To canvas.GetLength(0) For j = 1 To canvas.GetLength(1) canvas(i - 1, j - 1) = " " Next Next
For i = 1 To points.Count - 1 Dim lastPoint = points(i - 1) Dim curPoint = points(i) Dim deltaX = curPoint.x - lastPoint.x Dim deltaY = curPoint.y - lastPoint.y If deltaX = 0 Then 'vertical line Dim row = Math.Max(curPoint.y, lastPoint.y) Dim col = curPoint.x * 3 canvas(row, col) = "|" Else 'horizontal line Dim row = curPoint.y Dim col = Math.Min(curPoint.x, lastPoint.x) * 3 + 1 canvas(row, col) = "_" canvas(row, col + 1) = "_" End If Next
Dim lines As New List(Of String) For i = 1 To canvas.GetLength(0) Dim sb As New StringBuilder For j = 1 To canvas.GetLength(1) sb.Append(canvas(i - 1, j - 1)) Next lines.Add(sb.ToString()) Next Return lines End Function
Sub Main() For order = 1 To 5 Dim n = 1 << order Dim points = GetPointsForCurve(n) Console.WriteLine("Hilbert curve, order={0}", order) Dim lines = DrawCurve(points, n) For Each line In lines Console.WriteLine(line) Next Console.WriteLine() Next End Sub
End Module</lang>
- Output:
Hilbert curve, order=1 |__| Hilbert curve, order=2 __ __ __| |__ | __ | |__| |__| Hilbert curve, order=3 __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| |__ __| | |__ __ __ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__| Hilbert curve, order=4 __ __ __ __ __ __ __ __ __ __ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| Hilbert curve, order=5 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __| |__ |__| __ |__ __| __ | __ | __ |__ __| __ | __ | __ |__ __| __ | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__| |__| | |__ __| |__ __| | |__ __ __ __ __| __ __ | __ __ __ __ | __ __ |__ __ __ __ __| __| |__ __| |__ | |__| | |__| __| |__ |__| | |__| | __| |__ __| |__ | __ | | __ | |__ __| __ |__ __| __ |__ __| | __ | | __ | |__| |__| |__| |__| __| |__ __| |__ __| |__ __| |__ __| |__ |__| |__| |__| |__| __ __ __ __ |__ __ __ __ __ __ __ __ __ __| __ __ __ __ | |__| | | |__| | __| |__ |__| __| |__ |__| __| |__ | |__| | | |__| | |__ __| |__ __| | __ | __ |__ __| __ | __ | |__ __| |__ __| __| |__ __ __| |__ |__| |__| | |__ __| |__ __| | |__| |__| __| |__ __ __| |__ | __ __ __ __ | __ __ | __ __ __ __ | __ __ | __ __ __ __ | |__| __| |__ |__| | |__| | |__| __| |__ |__| | |__| | |__| __| |__ |__| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ |__ __| __ | |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| | |__ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __| __| |__ |__| __| |__ |__| __| |__ __| |__ |__| __| |__ |__| __| |__ | __ | __ |__ __| __ | __ | | __ | __ |__ __| __ | __ | |__| |__| | |__ __| |__ __| | |__| |__| |__| |__| | |__ __| |__ __| | |__| |__| __ __ | __ __ __ __ | __ __ __ __ | __ __ __ __ | __ __ | |__| | |__| __| |__ |__| | |__| | | |__| | |__| __| |__ |__| | |__| | |__ __| __ |__ __| __ |__ __| |__ __| __ |__ __| __ |__ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ __ __ __ __ __ __ __ __ | | __ __ __ __ __ __ __ __ __ | |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| |__| __| |__ |__| __ |__ __| __ __ |__ __| __ __ |__ __| __ __ |__ __| __ | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | | |__ __| |__ __| | |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| |__ __ __ __ __| __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ __| |__ | __ | | __ | | __ | | __ | | __ | | __ | | __ | | __ | |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__| |__|
Wren
<lang ecmascript>import "graphics" for Canvas, Color, Point import "dome" for Window
class Game {
static init() { Window.title = "Hilbert curve" Canvas.resize(650, 650) Window.resize(650, 650) __points = [] __width = 64 hilbert(0, 0, __width, 0, 0) var col = Color.hex("#90EE90") // light green var prev = __points[0] for (p in __points.skip(1)) { var curr = p Canvas.line(prev.x, prev.y, curr.x, curr.y, col) prev = curr } }
static hilbert(x, y, lg, i1, i2) { if (lg == 1) { var px = (__width - x) * 10 var py = (__width - y) * 10 __points.add(Point.new(px, py)) return } lg = lg >> 1 hilbert(x+i1*lg, y+i1*lg, lg, i1, 1-i2) hilbert(x+i2*lg, y+(1-i2)*lg, lg, i1, i2) hilbert(x+(1-i1)*lg, y+(1-i1)*lg, lg, i1, i2) hilbert(x+(1-i2)*lg, y+i2*lg, lg, 1-i1, i2) }
static update() {}
static draw(dt) {}
}</lang>
XPL0
Hilbert curve from turtle graphic program on Wikipedia. <lang XPL0>def Order=5, Size=15; \length of line segment int Dir, X, Y;
proc GoFwd; [case Dir&3 of
0: X:= X+Size; 1: Y:= Y+Size; 2: X:= X-Size; 3: Y:= Y-Size
other []; Line(X, Y, \white\7); ];
proc Hilbert(Lev, Ang); int Lev, Ang; [if Lev then
[Dir:= Dir+Ang; Hilbert(Lev-1, -Ang); GoFwd; Dir:= Dir-Ang; Hilbert(Lev-1, Ang); GoFwd; Hilbert(Lev-1, Ang); Dir:= Dir-Ang; GoFwd; Hilbert(Lev-1, -Ang); Dir:= Dir+Ang; ];
];
[SetVid($12); \640x480 graphics Dir:= 0; X:= 0; Y:= 0; Move(X, Y); Hilbert(Order, 1); ]</lang>
Yabasic
<lang Yabasic>width = 64
sub hilbert(x, y, lg, i1, i2)
if lg = 1 then line to (width-x) * 10, (width-y) * 10 return end if lg = lg / 2 hilbert(x+i1*lg, y+i1*lg, lg, i1, 1-i2) hilbert(x+i2*lg, y+(1-i2)*lg, lg, i1, i2) hilbert(x+(1-i1)*lg, y+(1-i1)*lg, lg, i1, i2) hilbert(x+(1-i2)*lg, y+i2*lg, lg, 1-i1, i2)
end sub
open window 655, 655
hilbert(0, 0, width, 0, 0)</lang>
zkl
Uses Image Magick and the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl <lang zkl>hilbert(6) : turtle(_);
fcn hilbert(n){ // Lindenmayer system --> Data of As & Bs
var [const] A="-BF+AFA+FB-", B="+AF-BFB-FA+"; buf1,buf2 := Data(Void,"A").howza(3), Data().howza(3); // characters do(n){ buf1.pump(buf2.clear(),fcn(c){ if(c=="A") A else if(c=="B") B else c }); t:=buf1; buf1=buf2; buf2=t; // swap buffers } buf1 // n=6 --> 13,651 letters
}
fcn turtle(hilbert){
const D=10; ds,dir := T( T(D,0), T(0,-D), T(-D,0), T(0,D) ), 0; // turtle offsets dx,dy := ds[dir]; img:=PPM(650,650); x,y:=10,10; color:=0x00ff00; hilbert.replace("A","").replace("B",""); // A & B are no-op during drawing foreach c in (hilbert){ switch(c){
case("F"){ img.line(x,y, (x+=dx),(y+=dy), color) } // draw forward case("+"){ dir=(dir+1)%4; dx,dy = ds[dir] } // turn right 90* case("-"){ dir=(dir-1)%4; dx,dy = ds[dir] } // turn left 90*
} } img.writeJPGFile("hilbert.zkl.jpg");
}</lang> Image at hilbert curve