Fortsätt till huvudinnehåll
Startsidan      |      Min nya blogg!      |     YouTube     |      Twitter      |      Podcasts      |      Hall of fame     |      Evolution

Harter-Heighways drakkurva

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

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(truetrue));
            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);
        }
    }
}

Kommentarer

Populära inlägg i den här bloggen

Bibelns böcker på engelska

Ibland vill man dela roliga bibelord till med sina internationella vänner, men då gäller det att kunna källförteckna så att de förstår. Därför har jag gjort en liten lista över bibelns böcker, beteckning och engelska motsvarighet. Jag har hämtat de svenska benämningarna från Bibel 2000. Gamla Testamentet: Första Moseboken el. Genesis (1 Mos): Genesis Andra Moseboken el. Exodus (2 Mos): Exodus Tredje Moseboken el. Leviticus (3 Mos): Leviticus Fjärde Moseboken el. Numeri (4 Mos): Numbers Femte Moseboken el. Deuteronomium (5 Mos): Deuteronomy Josua (Jos): Joshua Domarboken (Dom): Judges Rut (Rut): Ruth Första Samuelsboken (1 Sam): 1 Samuel Andra Samuelsboken (2 Sam): 2 Samuel Första Kungaboken (1 Kung): 1 Kings Andra Kungaboken (2 Kung): 2 Kings Första Krönikeboken (1 Krön): 1 Chronicles el. 1 Paralipomenon Andra Krönikeboken (2 Krön): 2 Chronicles el. 2 Paralipomenon Esra (Esr): Ezra el. 1 Esdras Nehemja (Neh): Nehemiah el. 2 Esdras Ester (Est): Esther el. 1-2 Maccabe

Mattias Irving bör frikännas

Häromdagen ställdes Mattias Irving inför rätta efter att ha visat ohörsamhet inför ordningsmakten. Irving är, på nästan alla tänkbara sätt, min meningsmotståndare. Jag delar definitivt inte hans åsikter om speciellt mycket. Just denna gång handlade ohörsamheten i fråga om att störa en nazistdemonstration med bl.a. psalmsång. Hur meningsmotståndare bör bemötas, är en av de frågor där vi verkligen går isär och denna gång var det nazisterna som var meningsmotståndaren. Både Irving och jag är antinazister, men jag dök inte upp för någon motaktion, det gjorde Irving. Han tog en kula för oss. Civil olydnad är en balansgång, och inte alltid är meningsmotståndaren just nazister. Vem du föraktar, beror på vem du är. Eftersom t.ex. ateister är lika föraktade som nazister i vissa läger - det finns vissa kristna sällskap som odlar myten att Hitlers ateism ledde honom till förintelsen - bör man ha ett system där spelreglerna är konsekventa. Det viktiga är inte vad man protesterar mot, utan

Har naturvetenskapen en naturalistisk bias?

Diskussionen om huruvida vetenskapen är agnostisk eller inte fortsätter. I praktiken är vetenskapen både ateistisk och gudsförnekande, bl.a. beroende på kravet att teorier måste kunna falsifieras, vilket i princip är omöjligt när man tar höjd för övernaturliga agenter. Rent tekniskt är vetenskapen agnostisk - ingen kan veta någonting om någonting - särskilt inte om verkligheten kontrolleras av gudar och demoner. Därför måste evidenslägen bedömas och därför bortser vetenskapen i praktiken från Gud. Och alla andra övernaturliga väsen. Non est ponenda pluralitas sine necessitate. Detta faller såklart inte i god jord hos den som faktiskt tror att övernaturliga väsen existerar. De vill gärna att vetenskapen ska ta särskilda hänsyn till just deras specifika föreställningar, och när så inte sker, har vi att göra med en konspiration. Här är ytterligare några invändningar som inkommit. Hittills. 1. Vetenskapen har förutfattade meningar om att gud inte finns 2. Ingen vet hur gravitation fungerar