1Math::PlanePath::KochelUCsuerrveC(o3n)tributed Perl DocuMmaetnht:a:tPiloannePath::KochelCurve(3)
2
6 Math::PlanePath::KochelCurve -- 3x3 self-similar R and F
7
9 use Math::PlanePath::KochelCurve;
10 my $path = Math::PlanePath::KochelCurve->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is an integer version of the Kochel curve by Herman Haverkort. It
15 fills the first quadrant in a 3x3 self-similar pattern made from two
16 base shapes.
17 |
19 8 80--79 72--71--70--69 60--59--58
20 | | | | |
21 7 77--78 73 66--67--68 61 56--57
22 | | | | |
23 6 76--75--74 65--64--63--62 55--54
24 |
25 5 11--12 17--18--19--20 47--48 53
26 | | | | | | |
27 4 10 13 16 25--24 21 46 49 52
28 | | | | | | | | |
29 3 9 14--15 26 23--22 45 50--51
30 | | |
31 2 8-- 7-- 6 27--28--29 44--43--42
32 | | |
33 1 1-- 2 5 32--31--30 37--38 41
34 | | | | | | |
35 Y=0-> 0 3-- 4 33--34--35--36 39--40
36 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
38 The base shapes are an "R" and an "F". The R goes along an edge, the F
40 goes diagonally across.
41 R pattern F pattern ^
43 +------+-----+-----+ +------+-----+----|+
44 |2 | |3\ |4 | |2 | |3\ |8 ||
45 | R | | F | R | | R | | F | R ||
46 | | | \ |-----| | | | \ | ||
47 +------+-----+-----+ +------+-----+-----+
48 |1 / |6 |5 / | |1 / |4 / |7 / |
49 | F | Rrev| F | | F | F | F |
50 | / |-----| / | | / | / | / |
51 +------+-----+-----+ +------+-----+-----+
52 |0| |7\ |8 | |0| |5\ ||6 |
53 | |Rrev| F | R | | |Rrev| F ||Rrev|
54 | o | \ |------> | o | \ || |
55 +------+-----+-----+ +------+-----+-----+
56 "Rrev" means the R pattern followed in reverse, which is
58 +------+-----+-----+
60 |8<----|7\ |6 | Rrev pattern
61 | R | F | Rrev|
62 | | \ |-----| turned -90 degrees
63 +------+-----+-----+ so as to start at
64 |1 / ||2 |5 / | bottom left
65 | F || R | F |
66 | / || | / |
67 +------+-----+-----+
68 |0| |3\ ||4 |
69 | |Rrev| F ||Rrev|
70 | o | \ || |
71 +------+-----+-----+
72 The F pattern is symmetric, the same forward or reverse, including its
74 sub-parts taken in reverse, so there's no separate "Frev" pattern.
75 The initial N=0 to N=8 is the Rrev turned -90, then N=9 to N=17 is the
77 F shape. The next higher level N=0,N=9,N=18 to N=72 is the Rrev too,
78 as is any N=9^k to N=8*9^k.
79 Fractal
81 The curve is conceived by Haverkort for filling a unit square by
82 descending into ever-smaller replacements, like other space-filling
83 curves. For that the top-level can be any of the patterns. To descend
84 any of the shapes can be used for the start, but for the outward
85 expanding version here the starting pattern must occur at the start of
86 its next higher level, which means Rrev is the only choice as it's the
87 only start in any of the three patterns.
88 But all the patterns can be found in the path at any desired size. For
90 example the "1" part of Rrev is an F, which means F to a desired level
91 can be found at
92 NFstart = 1 * 9^level
94 NFlast = NFstart + 9^level - 1
95 = 2 * 9^level - 1
96 XFstart = 3^level
97 YFstart = 0
98 level=3 for N=729 to N=1457 is a 27x27 which is the level-three F shown
100 in Haverkort's paper, starting at XFstart=27,YFstart=0.
101
103 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
104 classes.
105 "$path = Math::PlanePath::KochelCurve->new ()"
107 Create and return a new path object.
108 "($x,$y) = $path->n_to_xy ($n)"
110 Return the X,Y coordinates of point number $n on the path. Points
111 begin at 0 and if "$n < 0" then the return is an empty list.
112 Level Methods
114 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
115 Return "(0, 9**$level - 1)".
116
118 Math::PlanePath, Math::PlanePath::PeanoCurve,
119 Math::PlanePath::WunderlichMeander
120 Herman Haverkort, "Recursive Tilings and Space-Filling Curves with
122 Little Fragmentation", Journal of Computational Geometry, 2(1), 92-127,
123 2011.
124 <http://jocg.org/index.php/jocg/article/view/68>
126 <http://jocg.org/index.php/jocg/article/download/68/20>
127 <http://arxiv.org/abs/1002.1843>
128 <http://alexandria.tue.nl/openaccess/Metis239505.pdf> (slides)
130 <http://www.win.tue.nl/~hermanh/stack/h-rtslf-eurocg2010-talk.pdf>
131 (short form)
132
134 <http://user42.tuxfamily.org/math-planepath/index.html>
135
137 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
138 This file is part of Math-PlanePath.
140 Math-PlanePath is free software; you can redistribute it and/or modify
142 it under the terms of the GNU General Public License as published by
143 the Free Software Foundation; either version 3, or (at your option) any
144 later version.
145 Math-PlanePath is distributed in the hope that it will be useful, but
147 WITHOUT ANY WARRANTY; without even the implied warranty of
148 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
149 General Public License for more details.
150 You should have received a copy of the GNU General Public License along
152 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
153perl v5.28.1 2017-12-03 Math::PlanePath::KochelCurve(3)