Anders Hesselboms teknikblogg

Harter-Heighways drakkurva

2018-01-28

Harter-Heighways drakkurva är en enkel och vacker linjär fraktal med många intressanta attribut. Dels är dess kontur självrepetitiv och kan pusslas ihop med lika dana konturer på många olika sätt, och linjen som kurvan består av korsar aldrig sig själv, oavsett hur lång drakkurva man väljer att rita. En drakkurva kan beskrivas som en serie av höger- och vänstersvängar. Första iterationen består av en sväng, normalt höger. Alla iterationer efter den första innehåller lika många instruktioner som den föregående, multiplicerat med två och plus 1. Alltså 1, 3, 7, 15, 31, och så vidare. Den första generationen består alltså av en högersväng (H):

För att skapa nästa iteration utgår man från den föregående och lägger till svängarna från den, baklänges, samtidigt som man byter ut högersvängar till vänstersvängar (V). Man avgränsar föregående iteration från den nya iterationen med en högersväng, alltså:

HHV

Tecken 1 (H) är första iterationen, nästa tecken 2 (H) är avgränsaren mellan den gamla och nya generationen, och den sista vänstersvängen (V) är vårt H från första iterationen, ersatt med ett V. Vidare, HHV baklänges blir VHH och byter man ut alla H mot V och alla V mot H så får man HVV. Då är generation tre alltså HHV, H som avgränsare och sist HVV.

HHVHHVV

Och så vidare! Nästa generation kompletteras med föregående generation baklänges, med höger ändrat till vänster och vänster ändrat till höger. Och ett H i mitten:

HHVHHVVHHHVVHVV

Ett papper kan vikas som en drakkurva, men inte i särskilt många generationer. I C# skulle man kunna använda en sådan här struktur för att beskriva ett enda steg i drakkurvan.

public struct DragonStep
{
    public DragonStep(bool isRightTurn)
            : this(isRightTurn, false) { }
    public DragonStep(bool isRightTurn,
        bool isIterationSeparator)
    {
        IsRightTurn = isRightTurn;
        IsIterationSeparator = isIterationSeparator;
    }
    public bool IsRightTurn { get; set; }
    public bool IsIterationSeparator { get; set; }
}

Egentligen behövs bara en boolesk egenskap för att hålla reda på om steget representerar en höger- eller vänstersväng, men jag vill hålla reda på var en generation börjar och slutar för att kunna rendera den med olika färger.

Här är listklassen som anropas för att bygga kurvan. Funktionen GetDragonSequence skapar en sekvens av höger och vänster-svängar i form av en lista av strukturen vi nyss såg. När man fått listan, handlar det bara om att välja en startposition och en startriktning, och sedan svänga åt höger eller vänster enligt vad som står i listan.

public class DragonCurveGenerator
{
    public static List<DragonStep> GetDragonSequence(int generations)
    {
        var ret = new List<DragonStep>();
        if (generations <= 0)
            return ret;
        if (generations > 0)
            ret.Add(new DragonStep(true));
        if (generations <= 1)
            return ret;
        for (var i = 1; i < generations; i++)
        {
            var lastGenerationFinalIndex = ret.Count - 1;
            ret.Add(new DragonStep(true, true));
            for (var x = lastGenerationFinalIndex; x >= 0 ; x--)
                ret.Add(new DragonStep(!ret[x].IsRightTurn));
        }
        return ret;
    }
}

Jag definierar upp de möjliga riktningarna med en enumeration, för enkelhetens skull:

public enum Direction { Up, Right, Down, Left }

Sen är det bara en fråga om att rita kurvan, alltså följa sekvensen av svängar. Här får varje sväng representeras av en pixel. Notera att jag utnyttjar avgränsaren mellan iterationer för färgsättning.

public class DragonCurveRenderer
{
    public static void Draw(List<DragonStep> steps,
        Graphics g, Point startPosition, Direction startDirection,
        Brush color1, Brush color2, int first)
    {
        if (steps == null || steps.Count <= 0)
            return;
        var direction = startDirection;
        var x = startPosition.X;
        var y = startPosition.Y;
        var color = color1;
        var index = 0;
        foreach (var step in steps)
        {
            if (step.IsIterationSeparator)
            {
                color = color == color1 ? color2 : color1;
                index++;
            }
            if (index >= first)
                g.FillRectangle(color, x, y, 1, 1);
            ApplyDirection(direction, ref x, ref y);
            if (step.IsRightTurn)
            {
                if ((int) direction < 3)
                    direction++;
                else
                    direction = Direction.Up;
            }
            else
            {
                if (direction > 0)
                    direction--;
                else
                    direction = Direction.Left;
            }
        }
    }
    private static void ApplyDirection(Direction direction,
        ref int x, ref int y)
    {
        switch (direction)
        {
            case Direction.Up:
                y--;
                break;
            case Direction.Right:
                x++;
                break;
            case Direction.Down:
                y++;
                break;
            case Direction.Left:
                x--;
                break;
            default:
                throw new ArgumentOutOfRangeException();
        }
    }
}

Bilden föreställer en drakkurva på 18 generationer där generation 6 (med index 5) är den förste som ritas ut. Alltså totalt 13 fält, varannan är vit, varannan är svart. Så här kan användningen se ut (Windows Forms):

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace DragonCurve
{
    public partial class Form1 : Form
    {
        private List<DragonStep> DragonSteps { get; set; }
        public Form1()
        {
            InitializeComponent();
        }
        private void Form1_Load(object sender, EventArgs e)
        {
            DragonSteps = DragonCurveGenerator.GetDragonSequence(18);
        }
        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            var startPoint = new Point(550, 450);
            DragonCurveRenderer.Draw(DragonSteps, e.Graphics,
                startPoint, Direction.Up, Brushes.White, Brushes.Black, 5);
        }
    }
}