Hilbert curve

From Rosetta Code
Task
Hilbert curve
You are encouraged to solve this task according to the task description, using any language you may know.


Task

Produce a graphical or ASCII-art representation of a Hilbert curve of at least order 3.

C[edit]

Translation of: Kotlin
#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;
}
Output:
Same as Kotlin entry.

Go[edit]

Library: Go Graphics


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.

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")
}

IS-BASIC[edit]

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

Julia[edit]

Color graphics version using the Gtk package.

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)
 

Kotlin[edit]

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).

// 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()
}
}
Output:
.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
      |        |        |        |        |        |        |        |        |        |        
      |        |        |        |        |        |        |        |        |        |        
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
.  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  
|                    |              |                    |              |                    |  
|                    |              |                    |              |                    |  
.__.  .__.__.__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.__.__.  .__.  
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
.  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
.__.  .__.  .__.  .__.  .__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  .__.  .__.  .__.  .__.  
                        |                                            |                          
                        |                                            |                          
.__.  .__.  .__.  .__.  .__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  .__.  .__.  .__.  .__.  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
.  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
.__.  .__.__.__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.__.__.  .__.  
|                    |              |                    |              |                    |  
|                    |              |                    |              |                    |  
.  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
      |        |        |        |        |        |        |        |        |        |        
      |        |        |        |        |        |        |        |        |        |        
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .  
|                                                                                            |  
|                                                                                            |  
.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|        |        |        |        |        |  |        |        |        |        |        |  
|        |        |        |        |        |  |        |        |        |        |        |  
.  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
.__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  
            |                    |                          |                    |              
            |                    |                          |                    |              
.__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
.  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  
|        |        |        |        |        |  |        |        |        |        |        |  
|        |        |        |        |        |  |        |        |        |        |        |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  .__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  
|                                            |  |                                            |  
|                                            |  |                                            |  
.  .__.__.  .__.__.  .__.  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .__.  .__.__.  .__.__.  .  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
      |        |              |        |              |        |              |        |        
      |        |              |        |              |        |              |        |        
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
.  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .  
|                    |  |                    |  |                    |  |                    |  
|                    |  |                    |  |                    |  |                    |  
.__.  .__.__.__.  .__.  .__.  .__.__.__.  .__.  .__.  .__.__.__.  .__.  .__.  .__.__.__.  .__.  
   |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  |     
   |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  |     
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|        |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  
|        |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  
.  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  

Lua[edit]

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
-- 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))
 
Output:
luajit hilbert.lua 4 1M9FAF-4F2+2F-2F-2F++4F-F-4F+2F+2F+2F++3F+2F+3F--4FA10F-16F-58F-16F-
┌─────────────────────────────────────────────────────────┐
│         ┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐       ┌┐┌┐┌┐┌┐┌┐┌┐┌┐┌┐         │
│         │└┘││└┘││└┘││└┘│       │└┘││└┘││└┘││└┘│         │
│         └┐┌┘└┐┌┘└┐┌┘└┐┌┘       └┐┌┘└┐┌┘└┐┌┘└┐┌┘         │
│         ┌┘└──┘└┐┌┘└──┘└┐       ┌┘└──┘└┐┌┘└──┘└┐         │
│         │┌─┐┌─┐││┌─┐┌─┐│       │┌─┐┌─┐││┌─┐┌─┐│         │
│         └┘┌┘└┐└┘└┘┌┘└┐└┘       └┘┌┘└┐└┘└┘┌┘└┐└┘         │
│         ┌┐└┐┌┘┌┐┌┐└┐┌┘┌┐       ┌┐└┐┌┘┌┐┌┐└┐┌┘┌┐         │
│         │└─┘└─┘└┘└─┘└─┘│       │└─┘└─┘└┘└─┘└─┘│         │
│         └┐┌─┐┌─┐┌─┐┌─┐┌┘       └┐┌─┐┌─┐┌─┐┌─┐┌┘         │
│         ┌┘└┐└┘┌┘└┐└┘┌┘└┐       ┌┘└┐└┘┌┘└┐└┘┌┘└┐         │
│         │┌┐│┌┐└┐┌┘┌┐│┌┐│       │┌┐│┌┐└┐┌┘┌┐│┌┐│         │
│         └┘└┘│└─┘└─┘│└┘└┘╷ ╷┌─┐ └┘└┘│└─┘└─┘│└┘└┘         │
│         ┌┐┌┐│┌─┐┌─┐│┌┐┌┐│ ││ │ ┌┐┌┐│┌─┐┌─┐│┌┐┌┐         │
│         │└┘│└┘┌┘└┐└┘│└┘│├─┤├─┴┐│└┘│└┘┌┘└┐└┘│└┘│         │
│         └┐┌┘┌┐└┐┌┘┌┐└┐┌┘│ ││  │└┐┌┘┌┐└┐┌┘┌┐└┐┌┘         │
└──────────┘└─┘└─┘└─┘└─┘└─┘ └┴──┴─┘└─┘└─┘└─┘└─┘└──────────┘

Perl[edit]

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;

Hilbert curve (offsite image)

Perl 6[edit]

Works with: Rakudo version 2018.03
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> ],
],
);

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.

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> ],
],
);

See: Moore curve

Phix[edit]

Translation of: Go
-- 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
IupCloseOnEscape(dlg)
IupSetCallback(canvas, "ACTION", Icallback("redraw_cb"))
IupMap(dlg)
IupShowXY(dlg,IUP_CENTER,IUP_CENTER)
IupMainLoop()
IupClose()
end procedure
main()

Ring[edit]

 
# 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
 

Output image: Hilbert curve

Scala[edit]

Scala.js[edit]

@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
}
Output:
Best seen running in your browser by ScalaFiddle (ES aka JavaScript, non JVM).

Sidef[edit]

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(' ',
int(x * scale + xoff),
int(y * scale + yoff),
int(newx * scale + xoff),
int(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,
) {
 
has stack = []
has table = Hash()
 
has turtle = Turtle(
x: width,
y: height,
angle: turn,
scale: scale,
color: color,
xoff: xoff,
yoff: yoff,
)
 
method init {
 
angle.deg2rad!
turn.deg2rad!
 
table = Hash(
'+' => { turtle.turn(angle) },
'-' => { turtle.turn(-angle) },
':' => { turtle.mirror },
'[' => { stack.push(turtle.state) },
']' => { turtle.setstate(stack.pop) },
)
}
 
method execute(string, repetitions, filename, rules) {
 
repetitions.times {
string.gsub!(/(.)/, {|c| rules{c} \\ c })
}
 
string.each_char { |c|
if (table.contains(c)) {
table{c}.run
}
elsif (c.contains(/^[[:upper:]]\z/)) {
turtle.forward(len)
}
}
 
turtle.save_as(filename)
}
}
 
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)
Output:

Hilbert curve

zkl[edit]

Uses Image Magick and the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#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");
}

Image at hilbert curve