Hilbert curve

From Rosetta Code
Hilbert curve is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.


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.

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:
.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
      |        |        |        |        |        |        |        |        |        |        
      |        |        |        |        |        |        |        |        |        |        
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
.  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  
|                    |              |                    |              |                    |  
|                    |              |                    |              |                    |  
.__.  .__.__.__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.__.__.  .__.  
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
.  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
.__.  .__.  .__.  .__.  .__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  .__.  .__.  .__.  .__.  
                        |                                            |                          
                        |                                            |                          
.__.  .__.  .__.  .__.  .__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  .__.  .__.  .__.  .__.  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |     |  |     |  |     |  |     |  |     |  |     |  |  |  |  |  |  |  |  
.  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
|        |  |        |  |        |        |        |        |        |  |        |  |        |  
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
   |  |        |  |     |  |  |  |  |  |     |  |     |  |  |  |  |  |     |  |        |  |     
.__.  .__.__.__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.__.__.  .__.  
|                    |              |                    |              |                    |  
|                    |              |                    |              |                    |  
.  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .  .__.__.  .__.__.  .  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |     |  |     |  |  
.__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .__.  .__.  .__.  .__.  
      |        |        |        |        |        |        |        |        |        |        
      |        |        |        |        |        |        |        |        |        |        
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
|  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |     |  |  
.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .  
|                                                                                            |  
|                                                                                            |  
.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.__.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|        |        |        |        |        |  |        |        |        |        |        |  
|        |        |        |        |        |  |        |        |        |        |        |  
.  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
.__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  
            |                    |                          |                    |              
            |                    |                          |                    |              
.__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  .__.  .__.  .  .__.__.  .__.__.  .  .__.  .__.  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
|  |  |  |  |  |     |  |     |  |  |  |  |  |  |  |  |  |  |  |     |  |     |  |  |  |  |  |  
.  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  .  .__.  .  .__.  .__.  .__.  .__.  .  .__.  .  
|        |        |        |        |        |  |        |        |        |        |        |  
|        |        |        |        |        |  |        |        |        |        |        |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
   |  |     |  |     |  |     |  |     |  |        |  |     |  |     |  |     |  |     |  |     
.__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  .__.  .__.__.  .__.__.  .__.__.  .__.__.  .__.  
|                                            |  |                                            |  
|                                            |  |                                            |  
.  .__.__.  .__.__.  .__.  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .__.  .__.__.  .__.__.  .  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
      |        |              |        |              |        |              |        |        
      |        |              |        |              |        |              |        |        
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
|  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  |  |     |  |     |  |  
.  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .  .  .__.__.  .__.__.  .  
|                    |  |                    |  |                    |  |                    |  
|                    |  |                    |  |                    |  |                    |  
.__.  .__.__.__.  .__.  .__.  .__.__.__.  .__.  .__.  .__.__.__.  .__.  .__.  .__.__.__.  .__.  
   |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  |     
   |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  |     
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  
|        |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  
|        |  |        |  |        |  |        |  |        |  |        |  |        |  |        |  
.  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  .  .__.  .  
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  
|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  
.__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  .__.  

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 -> $v {
state ($x, $y) = @points[0,1];
state $d = -5 - 0i;
with $v {
when 'F' { @points.append: ($x += $d.re).round(.01), ($y += $d.im).round(.01) }
when /< + - >/ { $d *= "{$v}1i" }
default { }
}
}
 
say SVG.serialize(
svg => [
width => 660, height => 660, style => 'stroke:rgb(0,0,198)',
:rect[:width<100%>, :height<100%>, :fill<white>],
:polyline[ :points(@points.join: ','), :fill<white> ],
],
);

See: Hilbert curve

Ring[edit]

 
# Project : Hilbert curve
# Date  : 2018/05/01
# Author : Gal Zsolt (~ CalmoSoft ~)
# Email  : [email protected]
 
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

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)

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