The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-PlanePath-61
River stage one • 3 direct dependents • 4 total dependents
2 ++
/ Math::PlanePath::KochCurve

NAME

Math::PlanePath::KochCurve -- horizontal Koch curve

SYNOPSIS

 use Math::PlanePath::KochCurve;
 my $path = Math::PlanePath::KochCurve->new;
 my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

This is an integer version of the self-similar curve by Helge von Koch going along the X axis and making triangular excursions upwards.

                               8                                   3
                             /  \
                      6---- 7     9----10                19-...    2
                       \              /                    \
             2           5          11          14          18     1
           /  \        /              \        /  \        /
     0----1     3---- 4                12----13    15----16    <- Y=0
     ^
    X=0   2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19

The replicating shape is the initial N=0 to N=4,

            *
           / \
      *---*   *---*

which is rotated and repeated 3 times in the same pattern to give sections N=4 to N=8, N=8 to N=12, and N=12 to N=16. Then that N=0 to N=16 is itself replicated three times at the angles of the base pattern, and so on infinitely.

The X,Y coordinates are arranged on a square grid using every second point, per "Triangular Lattice" in Math::PlanePath. The result is flattened triangular segments with diagonals at a 45 degree angle.

Level Ranges

Each replication adds 3 copies of the existing points and is thus 4 times bigger, so if N=0 to N=4 is reckoned as level 1 then a given replication level goes from

    Nstart = 0
    Nlevel = 4^level   (inclusive)

Each replication is 3 times the width. The initial N=0 to N=4 figure is 6 wide and in general a level runs from

    Xstart = 0
    Xlevel = 2*3^level   (at N=Nlevel)

The highest Y is 3 times greater at each level similarly. The peak is at the midpoint of each level,

    Npeak = (4^level)/2
    Ypeak = 3^level
    Xpeak = 3^level

It can be seen that the N=6 point backtracks horizontally to the same X as the start of its section N=4 to N=8. This happens in the further replications too and is the maximum extent of the backtracking.

The Nlevel is multiplied by 4 to get the end of the next higher level. The same 4*N can be applied to all points N=0 to N=Nlevel to get the same shape but a factor of 3 bigger X,Y coordinates. The in-between points 4*N+1, 4*N+2 and 4*N+3 are then new finer structure in the higher level.

Fractal

Koch conceived the curve as having a fixed length and infinitely fine structure, making it continuous everywhere but differentiable nowhere. The code here can be pressed into use for that sort of construction for a given level of granularity by scaling

    X/3^level
    Y/3^level

which makes it a fixed 2 wide by 1 high. Or for unit-side equilateral triangles then apply further factors 1/2 and sqrt(3)/2, as noted in "Triangular Lattice" in Math::PlanePath.

    (X/2) / 3^level
    (Y*sqrt(3)/2) / 3^level

Turn Sequence

The sequence of turns made by the curve is straightforward. In the base 4 representation of N, the lowest non-zero digit gives the turn

   low digit       turn
   ---------   ------------
      1         +60 degrees
      2        -120 degrees
      3         +60 degrees

For example N=8 is 20 base 4, so turn -120 degrees for the next segment, ie. for N=8 to N=9.

When the least significant digit is non-zero it determines the turn, making the base N=0 to N=4 shape. When the low digit is zero it's instead the next level up which is in control, eg. N=0,4,8,12,16, making a turn where the base shape repeats.

Net Direction

The cumulative turn at a given N can be found by counting digits 1 and 2 in base 4.

    direction = 60 * ((count of digit 1s in base 4)
                      - (count of digit 2s in base 4))  degrees

For example N=11 is 23 in base 4, so 60*(0-1) = -60 degrees.

In this formula the count of 1s and 2s can go past 360 degrees, representing a spiralling around which occurs at progressively higher replication levels. The direction can be taken mod 360 degrees, or the count mod 6, for a direction 0 to 5 or as desired.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

$path = Math::PlanePath::KochCurve->new ()

Create and return a new path object.

($x,$y) = $path->n_to_xy ($n)

Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.

Fractional positions give an X,Y position along a straight line between the integer positions.

$n = $path->n_start()

Return 0, the first N in the path.

SEE ALSO

Math::PlanePath, Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::KochPeaks, Math::PlanePath::KochSnowflakes

Math::Fractal::Curve

HOME PAGE

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 2011 Kevin Ryde

Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.