Math::PlanePath::KochelCurve(3pm)

Usage

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

Overview

This is an integer version of the Kochel curve by

Herman Haverkort, "Recursive Tilings and Space-Filling Curves with Little Fragmentation", Journal of Computational Geometry, volume 2, number 1, 2011, pages 92-127.

<http://jocg.org/index.php/jocg/article/view/68>, <http://jocg.org/index.php/jocg/article/download/68/20>, <http://arxiv.org/abs/1002.1843>

<http://alexandria.tue.nl/openaccess/Metis239505.pdf> (slides), <http://www.win.tue.nl/~hermanh/stack/h-rtslf-eurocg2010-talk.pdf> (short form)

It fills the first quadrant in a 3x3 self-similar pattern made from two base shapes.

            |
      8    80--79  72--71--70--69  60--59--58
                |   |           |   |       |
      7    77--78  73  66--67--68  61  56--57
            |       |   |           |   |
      6    76--75--74  65--64--63--62  55--54
                                            |
      5    11--12  17--18--19--20  47--48  53
            |   |   |           |   |   |   |
      4    10  13  16  25--24  21  46  49  52
            |   |   |   |   |   |   |   |   |
      3     9  14--15  26  23--22  45  50--51
            |           |           |
      2     8-- 7-- 6  27--28--29  44--43--42
                    |           |           |
      1     1-- 2   5  32--31--30  37--38  41
            |   |   |   |           |   |   |
    Y=0->   0   3-- 4  33--34--35--36  39--40
            X=0  1   2   3   4   5   6   7   8   9  10  11  12  13  14

The base shapes are an "R" and an "F". The R goes along an edge, the F goes diagonally across.

          R pattern                      F pattern   ^
    +------+-----+-----+           +------+-----+----|+
    |2   | |3\   |4    |           |2   | |3\   |8   ||
    |  R | |  F  |   R |           |  R | |  F  |  R ||
    |    | |   \ |-----|           |    | |   \ |    ||
    +------+-----+-----+           +------+-----+-----+
    |1  /  |6    |5  / |           |1  /  |4  / |7  / |
    |  F   | Rrev|  F  |           |  F   |  F  |  F  |
    | /    |-----| /   |           | /    | /   | /   |
    +------+-----+-----+           +------+-----+-----+
    |0|    |7\   |8    |           |0|    |5\   ||6   |
    | |Rrev|  F  |  R  |           | |Rrev|  F  ||Rrev|
    | o    |   \ |------>          | o    |   \ ||    |
    +------+-----+-----+           +------+-----+-----+

"Rrev" means the R pattern followed in reverse, which is

    +------+-----+-----+
    |8<----|7\   |6    |    Rrev pattern
    |   R  |  F  | Rrev|
    |      |   \ |-----|    turned -90 degrees
    +------+-----+-----+    so as to start at
    |1  /  ||2   |5  / |    bottom left
    |  F   || R  |  F  |
    | /    ||    | /   |
    +------+-----+-----+
    |0|    |3\   ||4   |
    | |Rrev|  F  ||Rrev|
    | o    |   \ ||    |
    +------+-----+-----+

The F pattern is symmetric, the same forward or reverse, including its sub-parts taken in reverse, so there's no separate "Frev" pattern.

The initial N=0 to N=8 is the Rrev turned -90, then N=9 to N=17 is the F shape. The next higher level N=0,N=9,N=18 to N=72 is the Rrev too, as is any N=9^k to N=8*9^k.

Fractal

The curve is conceived by Haverkort for filling a unit square by descending into ever-smaller replacements, similar to other space-filling curves. For that, the top-level can be any of the patterns. But for the outward expanding version here, the starting pattern must occur at the start of its next higher level, which means Rrev is the only choice as it's the only start in any of the three patterns.

All the patterns can be found in the path at any desired size. For example the "1" part of Rrev is an F, which means F to a desired level can be found at

    NFstart = 1 * 9^level
    NFlast = NFstart + 9^level - 1
           = 2 * 9^level - 1
    XFstart = 3^level
    YFstart = 0

level=3 for N=729 to N=1457 is a 27x27 which is the level-three F shown in Haverkort's paper, starting at XFstart=27,YFstart=0.

Functions

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

"$path = Math::PlanePath::KochelCurve->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.

Level Methods

"($n_lo, $n_hi) = $path->level_to_n_range($level)": Return "(0, 9**$level - 1)".

Home page

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

Releases

6 releases since Debian 8 (Jessie); the text changed 3 times.