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

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]

This example does not show the output mentioned in the task description on this page (or a page linked to from here). Please ensure that it meets all task requirements and remove this message.
Note that phrases in task descriptions such as "print and display" and "print and show" for example, indicate that (reasonable length) output be a part of a language's solution.


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