1Math::PlanePath::KochPeUaskesr(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::KochPeaks(3)
2
6 Math::PlanePath::KochPeaks -- Koch curve peaks
7
9 use Math::PlanePath::KochPeaks;
10 my $path = Math::PlanePath::KochPeaks->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path traces out concentric peaks made from integer versions of the
15 self-similar "KochCurve" at successively greater replication levels.
16 29 9
18 / \
19 27----28 30----31 8
20 \ /
21 23 26 32 35 7
22 / \ / \ / \
23 21----22 24----25 33----34 36----37 6
24 \ /
25 20 38 5
26 / \
27 19----18 40----39 4
28 \ /
29 17 8 41 3
30 / / \ \
31 15----16 6---- 7 9----10 42----43 2
32 \ \ / /
33 14 5 2 11 44 1
34 / / / \ \ \
35 13 4 1 3 12 45 <- Y=0
36 ^
38 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9 ...
39 The initial figure is the peak N=1,2,3 then for the next level each
41 straight side expands to 3x longer with a notch in the middle like N=4
42 through N=8,
43 *
45 / \
46 *---* becomes *---* *---*
47 The angle is maintained in each replacement so
49 *
51 /
52 *---*
53 \
54 * *
55 / becomes /
56 * *
57 For example the segment N=1 to N=2 becomes N=4 to N=8, or in the next
59 level N=5 to N=6 becomes N=17 to N=21.
60 The X,Y coordinates are arranged as integers on a square grid. The
62 result is flattened triangular segments with diagonals at a 45 degree
63 angle.
64 Unlike other triangular grid paths "KochPeaks" uses the "odd" squares,
66 with one of X,Y odd and the other even. This means the rotation
67 formulas etc described in "Triangular Lattice" in Math::PlanePath don't
68 apply directly.
69 Level Ranges
71 Counting the innermost N=1 to N=3 peak as level 0, each peak is
72 Nstart = level + (2*4^level + 1)/3
74 Nend = level + (8*4^level + 1)/3
75 points = Nend-Nstart+1 = 2*4^level + 1
76 For example the outer peak shown above is level 2 starting at
78 Nstart=2+(2*4^2+1)/3=13 through to Nend=2+(8*4^2+1)/3=45 with
79 points=2*4^2+1=33 inclusive (45-13+1=33). The X width at a given level
80 is the endpoints at
81 Xlo = -(3^level)
83 Xhi = +(3^level)
84 For example the level 2 above runs from Xlo=-9 to Xhi=+9. The highest
86 Y is the centre peak half-way through the level at
87 Ypeak = 3^level
89 Npeak = level + (5*4^level + 1)/3
90 For example the level 2 outer peak above is Ypeak=3^2=9 at
92 N=2+(5*4^2+1)/3=29. For each level the Xlo,Xhi and Ypeak extents grow
93 by a factor of 3.
94 The triangular notches in each segment are not big enough to go past
96 the Xlo and Xhi end points. The new triangular part can equal the
97 ends, such as N=6 or N=19, but not go beyond.
98 In general a segment like N=5 to N=6 which is at the Xlo end will
100 expand to give two such segments and two points at the limit in the
101 next level, as for example N=5 to N=6 expands to N=19,20 and N=20,21.
102 So the count of points at Xlo doubles each time,
103 CountLo = 2^level
105 CountHi = 2^level same at Xhi
106
108 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
109 classes.
110 "$path = Math::PlanePath::KochPeaks->new ()"
112 Create and return a new path object.
113 "($x,$y) = $path->n_to_xy ($n)"
115 Return the X,Y coordinates of point number $n on the path. Points
116 begin at 0 and if "$n < 0" then the return is an empty list.
117 Fractional $n gives an X,Y position along a straight line between
119 the integer positions.
120 Level Methods
122 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
123 Return per "Level Ranges" above,
124 ((2 * 4**$level + 1)/3 + $level,
126 (8 * 4**$level + 1)/3 + $level)
127
129 Rectangle to N Range
130 The baseline for a given level is along a diagonal X+Y=3^level or
131 -X+Y=3^level. The containing level can thus be found as
132 level = floor(log3( Xmax + Ymax ))
134 with Xmax as maximum absolute value, max(abs(X))
135 The endpoint in a level is simply 1 before the start of the next, so
137 Nlast = Nstart(level+1) - 1
139 = (level+1) + (2*4^(level+1) + 1)/3 - 1
140 = level + (8*4^level + 1)/3
141 Using this Nlast is an over-estimate of the N range needed, but an easy
143 calculation.
144 It's not too difficult to work down for an exact range, by considering
146 which parts of the curve might intersect a rectangle. But some
147 backtracking and level descending is necessary because a rectangle
148 might extend into the empty part of a notch and so be past its baseline
149 but not intersect any. There's plenty of room for a rectangle to
150 intersect nothing at all too.
151
153 Math::PlanePath, Math::PlanePath::KochCurve,
154 Math::PlanePath::KochSnowflakes, Math::PlanePath::PeanoCurve,
155 Math::PlanePath::HilbertCurve
156
158 <http://user42.tuxfamily.org/math-planepath/index.html>
159
161 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
162 Math-PlanePath is free software; you can redistribute it and/or modify
164 it under the terms of the GNU General Public License as published by
165 the Free Software Foundation; either version 3, or (at your option) any
166 later version.
167 Math-PlanePath is distributed in the hope that it will be useful, but
169 WITHOUT ANY WARRANTY; without even the implied warranty of
170 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
171 General Public License for more details.
172 You should have received a copy of the GNU General Public License along
174 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
175perl v5.32.0 2020-07-28 Math::PlanePath::KochPeaks(3)