1Math::PlanePath::KochelUCsuerrveC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::KochelCurve(3)
2
3
4

NAME

6       Math::PlanePath::KochelCurve -- 3x3 self-similar R and F
7

SYNOPSIS

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

DESCRIPTION

14       This is an integer version of the Kochel curve by
15
16           Herman Haverkort, "Recursive Tilings and Space-Filling Curves with
17           Little Fragmentation", Journal of Computational Geometry, volume 2,
18           number 1, 2011, pages 92-127.
19
20           <http://jocg.org/index.php/jocg/article/view/68>,
21           <http://jocg.org/index.php/jocg/article/download/68/20>,
22           <http://arxiv.org/abs/1002.1843>
23
24           <http://alexandria.tue.nl/openaccess/Metis239505.pdf> (slides),
25           <http://www.win.tue.nl/~hermanh/stack/h-rtslf-eurocg2010-talk.pdf>
26           (short form)
27
28       It fills the first quadrant in a 3x3 self-similar pattern made from two
29       base shapes.
30
31                   |
32             8    80--79  72--71--70--69  60--59--58
33                       |   |           |   |       |
34             7    77--78  73  66--67--68  61  56--57
35                   |       |   |           |   |
36             6    76--75--74  65--64--63--62  55--54
37                                                   |
38             5    11--12  17--18--19--20  47--48  53
39                   |   |   |           |   |   |   |
40             4    10  13  16  25--24  21  46  49  52
41                   |   |   |   |   |   |   |   |   |
42             3     9  14--15  26  23--22  45  50--51
43                   |           |           |
44             2     8-- 7-- 6  27--28--29  44--43--42
45                           |           |           |
46             1     1-- 2   5  32--31--30  37--38  41
47                   |   |   |   |           |   |   |
48           Y=0->   0   3-- 4  33--34--35--36  39--40
49
50                   X=0  1   2   3   4   5   6   7   8   9  10  11  12  13  14
51
52       The base shapes are an "R" and an "F".  The R goes along an edge, the F
53       goes diagonally across.
54
55                 R pattern                      F pattern   ^
56           +------+-----+-----+           +------+-----+----|+
57           |2   | |3\   |4    |           |2   | |3\   |8   ||
58           |  R | |  F  |   R |           |  R | |  F  |  R ||
59           |    | |   \ |-----|           |    | |   \ |    ||
60           +------+-----+-----+           +------+-----+-----+
61           |1  /  |6    |5  / |           |1  /  |4  / |7  / |
62           |  F   | Rrev|  F  |           |  F   |  F  |  F  |
63           | /    |-----| /   |           | /    | /   | /   |
64           +------+-----+-----+           +------+-----+-----+
65           |0|    |7\   |8    |           |0|    |5\   ||6   |
66           | |Rrev|  F  |  R  |           | |Rrev|  F  ||Rrev|
67           | o    |   \ |------>          | o    |   \ ||    |
68           +------+-----+-----+           +------+-----+-----+
69
70       "Rrev" means the R pattern followed in reverse, which is
71
72           +------+-----+-----+
73           |8<----|7\   |6    |    Rrev pattern
74           |   R  |  F  | Rrev|
75           |      |   \ |-----|    turned -90 degrees
76           +------+-----+-----+    so as to start at
77           |1  /  ||2   |5  / |    bottom left
78           |  F   || R  |  F  |
79           | /    ||    | /   |
80           +------+-----+-----+
81           |0|    |3\   ||4   |
82           | |Rrev|  F  ||Rrev|
83           | o    |   \ ||    |
84           +------+-----+-----+
85
86       The F pattern is symmetric, the same forward or reverse, including its
87       sub-parts taken in reverse, so there's no separate "Frev" pattern.
88
89       The initial N=0 to N=8 is the Rrev turned -90, then N=9 to N=17 is the
90       F shape.  The next higher level N=0,N=9,N=18 to N=72 is the Rrev too,
91       as is any N=9^k to N=8*9^k.
92
93   Fractal
94       The curve is conceived by Haverkort for filling a unit square by
95       descending into ever-smaller replacements, similar to other space-
96       filling curves.  For that, the top-level can be any of the patterns.
97       But for the outward expanding version here, the starting pattern must
98       occur at the start of its next higher level, which means Rrev is the
99       only choice as it's the only start in any of the three patterns.
100
101       All the patterns can be found in the path at any desired size.  For
102       example the "1" part of Rrev is an F, which means F to a desired level
103       can be found at
104
105           NFstart = 1 * 9^level
106           NFlast = NFstart + 9^level - 1
107                  = 2 * 9^level - 1
108           XFstart = 3^level
109           YFstart = 0
110
111       level=3 for N=729 to N=1457 is a 27x27 which is the level-three F shown
112       in Haverkort's paper, starting at XFstart=27,YFstart=0.
113

FUNCTIONS

115       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
116       classes.
117
118       "$path = Math::PlanePath::KochelCurve->new ()"
119           Create and return a new path object.
120
121       "($x,$y) = $path->n_to_xy ($n)"
122           Return the X,Y coordinates of point number $n on the path.  Points
123           begin at 0 and if "$n < 0" then the return is an empty list.
124
125   Level Methods
126       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
127           Return "(0, 9**$level - 1)".
128

SEE ALSO

130       Math::PlanePath, Math::PlanePath::PeanoCurve,
131       Math::PlanePath::WunderlichMeander
132

HOME PAGE

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

LICENSE

137       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
138       Kevin Ryde
139
140       This file is part of Math-PlanePath.
141
142       Math-PlanePath is free software; you can redistribute it and/or modify
143       it under the terms of the GNU General Public License as published by
144       the Free Software Foundation; either version 3, or (at your option) any
145       later version.
146
147       Math-PlanePath is distributed in the hope that it will be useful, but
148       WITHOUT ANY WARRANTY; without even the implied warranty of
149       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
150       General Public License for more details.
151
152       You should have received a copy of the GNU General Public License along
153       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
154
155
156
157perl v5.32.1                      2021-01-27   Math::PlanePath::KochelCurve(3)
Impressum