I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Sierpinski square curve

From Rosetta Code
Sierpinski square 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 Sierpinski square curve of at least order 3.

C++[edit]

Output is a file in SVG format.

// See https://en.wikipedia.org/wiki/Sierpi%C5%84ski_curve#Representation_as_Lindenmayer_system
#include <cmath>
#include <fstream>
#include <iostream>
#include <string>
 
std::string rewrite(const std::string& s) {
std::string t;
for (char c : s) {
if (c == 'X')
t += "XF-F+F-XF+F+XF-F+F-X";
else
t += c;
}
return t;
}
 
void line(std::ostream& out, double& x, double& y, double length, int angle) {
constexpr double pi = 3.14159265359;
double theta = (pi * angle)/180.0;
x += length * std::cos(theta);
y += length * std::sin(theta);
out << 'L' << x << ',' << y << '\n';
}
 
void execute(std::ostream& out, const std::string& s, double x, double y,
double length, int angle) {
out << 'M' << x << ',' << y << '\n';
for (char c : s) {
if (c == 'F')
line(out, x, y, length, angle);
else if (c == '+')
angle = (angle + 90) % 360;
else if (c == '-')
angle = (angle - 90) % 360;
}
}
 
int main() {
const int size = 635, length = 5;
const int order = 5;
std::ofstream out("sierpinski_square.svg");
if (!out) {
std::cerr << "Cannot open output file\n";
return 1;
}
out << "<svg xmlns='http://www.w3.org/2000/svg' width='"
<< size << "' height='" << size << "'>\n";
out << "<rect width='100%' height='100%' fill='white'/>\n";
out << "<path stroke-width='1' stroke='black' fill='none' d='";
std::string s = "F+XF+F+XF";
for (int i = 0; i < order; ++i)
s = rewrite(s);
execute(out, s, (size - length)/2, length, length, 0);
out << "'/>\n</svg>\n";
return 0;
}

Go[edit]

Library: Go Graphics

The following uses the Lindenmayer system with the appropriate parameters from the Wikipedia article and produces a similar image (apart from the colors, yellow on blue) to the Sidef and zkl entries.

package main
 
import (
"github.com/fogleman/gg"
"github.com/trubitsyn/go-lindenmayer"
"log"
"math"
)
 
const twoPi = 2 * math.Pi
 
var (
width = 770.0
height = 770.0
dc = gg.NewContext(int(width), int(height))
)
 
var cx, cy, h, theta float64
 
func main() {
dc.SetRGB(0, 0, 1) // blue background
dc.Clear()
cx, cy = 10, height/2+5
h = 6
sys := lindenmayer.Lsystem{
Variables: []rune{'X'},
Constants: []rune{'F', '+', '-'},
Axiom: "F+XF+F+XF",
Rules: []lindenmayer.Rule{
{"X", "XF-F+F-XF+F+XF-F+F-X"},
},
Angle: math.Pi / 2, // 90 degrees in radians
}
result := lindenmayer.Iterate(&sys, 5)
operations := map[rune]func(){
'F': func() {
newX, newY := cx+h*math.Sin(theta), cy-h*math.Cos(theta)
dc.LineTo(newX, newY)
cx, cy = newX, newY
},
'+': func() {
theta = math.Mod(theta+sys.Angle, twoPi)
},
'-': func() {
theta = math.Mod(theta-sys.Angle, twoPi)
},
}
if err := lindenmayer.Process(result, operations); err != nil {
log.Fatal(err)
}
// needed to close the square at the extreme left
operations['+']()
operations['F']()
 
// create the image and save it
dc.SetRGB255(255, 255, 0) // yellow curve
dc.SetLineWidth(2)
dc.Stroke()
dc.SavePNG("sierpinski_square_curve.png")
}

Java[edit]

Translation of: C++
import java.io.*;
 
public class SierpinskiSquareCurve {
public static void main(final String[] args) {
try (Writer writer = new BufferedWriter(new FileWriter("sierpinski_square.svg"))) {
SierpinskiSquareCurve s = new SierpinskiSquareCurve(writer);
int size = 635, length = 5;
s.currentAngle = 0;
s.currentX = (size - length)/2;
s.currentY = length;
s.lineLength = length;
s.begin(size);
s.execute(rewrite(5));
s.end();
} catch (final Exception ex) {
ex.printStackTrace();
}
}
 
private SierpinskiSquareCurve(final Writer writer) {
this.writer = writer;
}
 
private void begin(final int size) throws IOException {
write("<svg xmlns='http://www.w3.org/2000/svg' width='%d' height='%d'>\n", size, size);
write("<rect width='100%%' height='100%%' fill='white'/>\n");
write("<path stroke-width='1' stroke='black' fill='none' d='");
}
 
private void end() throws IOException {
write("'/>\n</svg>\n");
}
 
private void execute(final String s) throws IOException {
write("M%g,%g\n", currentX, currentY);
for (int i = 0, n = s.length(); i < n; ++i) {
switch (s.charAt(i)) {
case 'F':
line(lineLength);
break;
case '+':
turn(ANGLE);
break;
case '-':
turn(-ANGLE);
break;
}
}
}
 
private void line(final double length) throws IOException {
final double theta = (Math.PI * currentAngle) / 180.0;
currentX += length * Math.cos(theta);
currentY += length * Math.sin(theta);
write("L%g,%g\n", currentX, currentY);
}
 
private void turn(final int angle) {
currentAngle = (currentAngle + angle) % 360;
}
 
private void write(final String format, final Object... args) throws IOException {
writer.write(String.format(format, args));
}
 
private static String rewrite(final int order) {
String s = AXIOM;
for (int i = 0; i < order; ++i) {
final StringBuilder sb = new StringBuilder();
for (int j = 0, n = s.length(); j < n; ++j) {
final char ch = s.charAt(j);
if (ch == 'X')
sb.append(PRODUCTION);
else
sb.append(ch);
}
s = sb.toString();
}
return s;
}
 
private final Writer writer;
private double lineLength;
private double currentX;
private double currentY;
private int currentAngle;
 
private static final String AXIOM = "F+XF+F+XF";
private static final String PRODUCTION = "XF-F+F-XF+F+XF-F+F-X";
private static final int ANGLE = 90;
}

Julia[edit]

using Lindenmayer # https://github.com/cormullion/Lindenmayer.jl
 
scurve = LSystem(Dict("X" => "XF-F+F-XF+F+XF-F+F-X"), "F+XF+F+XF")
 
drawLSystem(scurve,
forward = 3,
turn = 90,
startingy = -400,
iterations = 6,
filename = "sierpinski_square_curve.png",
showpreview = true
)
 

Perl[edit]

use strict;
use warnings;
use SVG;
use List::Util qw(max min);
use constant pi => 2 * atan2(1, 0);
 
my $rule = 'XF-F+F-XF+F+XF-F+F-X';
my $S = 'F+F+XF+F+XF';
$S =~ s/X/$rule/g for 1..5;
 
my (@X, @Y);
my ($x, $y) = (0, 0);
my $theta = pi/4;
my $r = 6;
 
for (split //, $S) {
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; }
}
 
my ($xrng, $yrng) = ( max(@X) - min(@X), max(@Y) - min(@Y));
my ($xt, $yt) = (-min(@X) + 10, -min(@Y) + 10);
 
my $svg = SVG->new(width=>$xrng+20, height=>$yrng+20);
my $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 my $fh, '>', 'sierpinski-square-curve.svg';
print $fh $svg->xmlify(-namespace=>'svg');
close $fh;

See: sierpinski-square-curve.svg (offsite SVG image)

Phix[edit]

constant rule = "XF-F+F-XF+F+XF-F+F-X"
string s = "F+F+XF+F+XF"
for n=1 to 4 do
string next = ""
for i=1 to length(s) do
integer ch = s[i]
next &= iff(ch='X'?rule:ch)
end for
s = next
end for
 
sequence X = {}, Y= {}
atom x=0, y=0, theta=PI/4, r = 6
string svg = ""
for i=1 to length(s) do
integer ch = s[i]
switch ch do
case 'F': X &= x; x += r*cos(theta)
Y &= y; y += r*sin(theta)
case '+': theta += PI/2
case '-': theta -= PI/2
end switch
end for
constant svgfmt = """
<svg xmlns="http://www.w3.org/2000/svg" height="%d" width="%d">
<rect height="100%%" width="100%%" style="fill:black" />
<polyline points="%s" style="stroke: orange; stroke-width: 1" transform="translate(%d,%d)" />
</svg>"""
string points = ""
for i=1 to length(X) do
points &= sprintf("%.2f,%.2f ",{X[i],Y[i]})
end for
integer fn = open("sierpinski_square_curve.svg","w")
atom xt = -min(X)+10,
yt = -min(Y)+10
printf(fn,svgfmt,{max(X)+xt+10,max(Y)+yt+10,points,xt,yt})
close(fn)

Raku[edit]

(formerly Perl 6)

Works with: Rakudo version 2020.02
use SVG;
 
role Lindenmayer {
has %.rules;
method succ {
self.comb.map( { %!rules{$^c} // $c } ).join but Lindenmayer(%!rules)
}
}
 
my $sierpinski = 'X' but Lindenmayer( { X => 'XF-F+F-XF+F+XF-F+F-X' } );
 
$sierpinski++ xx 5;
 
my $dim = 600;
my $scale = 6;
 
my @points = (-80, 298);
 
for $sierpinski.comb {
state ($x, $y) = @points[0,1];
state $d = $scale + 0i;
when 'F' { @points.append: ($x += $d.re).round(1), ($y += $d.im).round(1) }
when /< + - >/ { $d *= "{$_}1i" }
default { }
}
 
my @t = @points.tail(2).clone;
 
my $out = './sierpinski-square-curve-perl6.svg'.IO;
 
$out.spurt: SVG.serialize(
svg => [
:width($dim), :height($dim),
:rect[:width<100%>, :height<100%>, :fill<black>],
:polyline[
:points((@points, map {(@t »+=» $_).clone}, ($scale,0), (0,$scale), (-$scale,0)).join: ','),
:fill<black>, :transform("rotate(45, 300, 300)"), :style<stroke:#61D4FF>,
],
:polyline[
:points(@points.map( -> $x,$y { $x, $dim - $y + 1 }).join: ','),
:fill<black>, :transform("rotate(45, 300, 300)"), :style<stroke:#61D4FF>,
],
],
);

See: Sierpinski-square-curve-perl6.svg (offsite SVG image)

Rust[edit]

Program output is a file in SVG format.

// [dependencies]
// svg = "0.8.0"
 
use svg::node::element::path::Data;
use svg::node::element::Path;
 
struct SierpinskiSquareCurve {
current_x: f64,
current_y: f64,
current_angle: i32,
line_length: f64,
}
 
impl SierpinskiSquareCurve {
fn new(x: f64, y: f64, length: f64, angle: i32) -> SierpinskiSquareCurve {
SierpinskiSquareCurve {
current_x: x,
current_y: y,
current_angle: angle,
line_length: length,
}
}
fn rewrite(order: usize) -> String {
let mut str = String::from("F+XF+F+XF");
for _ in 0..order {
let mut tmp = String::new();
for ch in str.chars() {
match ch {
'X' => tmp.push_str("XF-F+F-XF+F+XF-F+F-X"),
_ => 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 SierpinskiSquareCurve::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, length: f64, order: usize) -> std::io::Result<()> {
use svg::node::element::Rectangle;
let x = (size as f64 - length) / 2.0;
let y = length;
let rect = Rectangle::new()
.set("width", "100%")
.set("height", "100%")
.set("fill", "white");
let mut s = SierpinskiSquareCurve::new(x, y, length, 0);
let document = svg::Document::new()
.set("width", size)
.set("height", size)
.add(rect)
.add(s.execute(order));
svg::save(file, &document)
}
}
 
fn main() {
SierpinskiSquareCurve::save("sierpinski_square_curve.svg", 635, 5.0, 5).unwrap();
}

Sidef[edit]

Uses the LSystem() class from Hilbert curve.

var rules = Hash(
x => 'xF-F+F-xF+F+xF-F+F-x',
)
 
var lsys = LSystem(
width: 510,
height: 510,
 
xoff: -505,
yoff: -254,
 
len: 4,
angle: 90,
color: 'dark green',
)
 
lsys.execute('F+xF+F+xF', 5, "sierpiński_square_curve.png", rules)

Output image: Sierpiński square curve

zkl[edit]

Uses Image Magick and the PPM class from http://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#zkl

sierpinskiSquareCurve(4) : turtle(_);
 
fcn sierpinskiSquareCurve(n){ // Lindenmayer system --> Data of As
var [const] A="AF-F+F-AF+F+AF-F+F-A", B=""; // Production rules
var [const] Axiom="F+AF+F+AF";
buf1,buf2 := Data(Void,Axiom).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=4 --> 3,239 characters
}
 
fcn turtle(curve){ // a "square" turtle, directions are +-90*
const D=10;
ds,dir := T( T(D,0), T(0,-D), T(-D,0), T(0,D) ), 2; // turtle offsets
dx,dy := ds[dir];
img,color := PPM(650,650), 0x00ff00; // green on black
x,y := img.w/2, 10;
curve.replace("A","").replace("B",""); // A & B are no-op during drawing
foreach c in (curve){
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("sierpinskiSquareCurve.zkl.jpg");
}
Output:

Offsite image at Sierpinski square curve of order 4