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
15 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 <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 <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 It fills the first quadrant in a 3x3 self-similar pattern made from two
29 base shapes.
30 |
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 X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
51 The base shapes are an "R" and an "F". The R goes along an edge, the F
53 goes diagonally across.
54 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 "Rrev" means the R pattern followed in reverse, which is
71 +------+-----+-----+
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 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 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 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 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 NFstart = 1 * 9^level
106 NFlast = NFstart + 9^level - 1
107 = 2 * 9^level - 1
108 XFstart = 3^level
109 YFstart = 0
110 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
115 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
116 classes.
117 "$path = Math::PlanePath::KochelCurve->new ()"
119 Create and return a new path object.
120 "($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 Level Methods
126 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
127 Return "(0, 9**$level - 1)".
128
130 Math::PlanePath, Math::PlanePath::PeanoCurve,
131 Math::PlanePath::WunderlichMeander
132
134 <http://user42.tuxfamily.org/math-planepath/index.html>
135
137 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
138 Kevin Ryde
139 This file is part of Math-PlanePath.
141 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 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 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/>.
154perl v5.32.1 2021-01-27 Math::PlanePath::KochelCurve(3)