1Math::PlanePath::KochSnUoswefrlaCkoenst(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::KochSnowflakes(3)
2
6 Math::PlanePath::KochSnowflakes -- Koch snowflakes as concentric rings
7
9 use Math::PlanePath::KochSnowflakes;
10 my $path = Math::PlanePath::KochSnowflakes->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path traces out concentric integer versions of the Koch snowflake
15 at successively greater iteration levels.
16 48 6
18 / \
19 50----49 47----46 5
20 \ /
21 54 51 45 42 4
22 / \ / \ / \
23 56----55 53----52 44----43 41----40 3
24 \ /
25 57 12 39 2
26 / / \ \
27 58----59 14----13 11----10 37----38 1
28 \ \ 3 / /
29 60 15 1----2 9 36 <- Y=0
30 / \ \
31 62----61 4---- 5 7---- 8 35----34 -1
32 \ \ / /
33 63 6 33 -2
34 \
35 16----17 19----20 28----29 31----32 -3
36 \ / \ / \ /
37 18 21 27 30 -4
38 / \
39 22----23 25----26 -5
40 \ /
41 24 -6
42 ^
44 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5 6 7 8 9
45 The initial figure is the triangle N=1,2,3 then for the next level each
47 straight side expands to 3x longer and a notch like N=4 through N=8,
48 *---* becomes *---* *---*
50 \ /
51 *
52 The angle is maintained in each replacement, for example the segment
54 N=5 to N=6 becomes N=20 to N=24 at the next level.
55 Triangular Coordinates
57 The X,Y coordinates are arranged as integers on a square grid per
58 "Triangular Lattice" in Math::PlanePath, except the Y coordinates of
59 the innermost triangle which is
60 N=3 X=0, Y=+2/3
62 *
63 / \
64 / \
65 / \
66 / o \
67 / \
68 N=1 *-----------* N=2
69 X=-1, Y=-1/3 X=1, Y=-1/3
70 These values are not integers, but they're consistent with the centring
72 and scaling of the higher levels. If all-integer is desired then
73 rounding gives Y=0 or Y=1 and doesn't overlap the subsequent points.
74 Level Ranges
76 Counting the innermost triangle as level 0, each ring is
77 Nstart = 4^level
79 length = 3*4^level many points
80 For example the outer ring shown above is level 2 starting N=4^2=16 and
82 having length=3*4^2=48 points (through to N=63 inclusive).
83 The X range at a given level is the initial triangle baseline iterated
85 out. Each level expands the sides by a factor of 3 so
86 Xlo = -(3^level)
88 Xhi = +(3^level)
89 For example level 2 above runs from X=-9 to X=+9. The Y range is the
91 points N=6 and N=12 iterated out. Ylo in level 0 since there's no
92 downward notch on that innermost triangle.
93 Ylo = / -(2/3)*3^level if level >= 1
95 \ -1/3 if level == 0
96 Yhi = +(2/3)*3^level
97 Notice that for each level the extents grow by a factor of 3 but the
99 notch introduced in each segment is not big enough to go past the
100 corner positions. They can equal the extents horizontally, for example
101 in level 1 N=14 is at X=-3 the same as the corner N=4, and on the right
102 N=10 at X=+3 the same as N=8, but they don't go past.
103 The snowflake is an example of a fractal curve with ever finer
105 structure. The code here can be used for that by going from N=Nstart
106 to N=Nstart+length-1 and scaling X/3^level Y/3^level to give a 2-wide
107 1-high figure of desired fineness. See examples/koch-svg.pl for a
108 complete program doing that as an SVG image file.
109 Area
111 The area of the snowflake at a given level can be calculated from the
112 area under the Koch curve per "Area" in Math::PlanePath::KochCurve
113 which is the 3 sides, and the central triangle
114 * ^ Yhi
116 / \ | height = 3^level
117 / \ |
118 / \ |
119 *-------* v
120 <-------> width = 3^level - (- 3^level) = 2*3^level
122 Xlo Xhi
123 triangle_area = width*height/2 = 9^level
125 snowflake_area[level] = triangle_area[level] + 3*curve_area[level]
127 = 9^level + 3*(9^level - 4^level)/5
128 = (8*9^level - 3*4^level) / 5
129 If the snowflake is conceived as a fractal of fixed initial triangle
131 size and ever-smaller notches then the area is divided by that central
132 triangle area 9^level,
133 unit_snowflake[level] = snowflake_area[level] / 9^level
135 = (8 - 3*(4/9)^level) / 5
136 -> 8/5 as level -> infinity
137 Which is the well-known 8/5 * initial triangle area for the fractal
139 snowflake.
140
142 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
143 classes.
144 "$path = Math::PlanePath::KochSnowflakes->new ()"
146 Create and return a new path object.
147 Level Methods
149 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
150 Return per "Level Ranges" above,
151 (4**$level,
153 4**($level+1) - 1)
154
156 Rectangle to N Range
157 As noted in "Level Ranges" above, for a given level
158 -(3^level) <= X <= 3^level
160 -(2/3)*(3^level) <= Y <= (2/3)*(3^level)
161 So the maximum X,Y in a rectangle gives
163 level = ceil(log3(max(abs(x1), abs(x2), abs(y1)*3/2, abs(y2)*3/2)))
165 and the last point in that level is
167 Nlevel = 4^(level+1) - 1
169 Using this as an N range is an over-estimate, but an easy calculation.
171 It's not too difficult to trace down for an exact range
172
174 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
175 the Koch snowflake include the following. See "OEIS" in
176 Math::PlanePath::KochCurve for entries related to a single Koch side.
177 <http://oeis.org/A164346> (etc)
179 A164346 number of points in ring n, being 3*4^n
181 A178789 number of acute angles in ring n, 4^n + 2
182 A002446 number of obtuse angles in ring n, 2*4^n - 2
183 The acute angles are those of +/-120 degrees and the obtuse ones +/-240
185 degrees. Eg. in the outer ring=2 shown above the acute angles are at
186 N=18, 22, 24, 26, etc. The angles are all either acute or obtuse, so
187 A178789 + A002446 = A164346.
188
190 Math::PlanePath, Math::PlanePath::KochCurve, Math::PlanePath::KochPeaks
191 Math::PlanePath::QuadricIslands
193
195 <http://user42.tuxfamily.org/math-planepath/index.html>
196
198 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
199 Math-PlanePath is free software; you can redistribute it and/or modify
201 it under the terms of the GNU General Public License as published by
202 the Free Software Foundation; either version 3, or (at your option) any
203 later version.
204 Math-PlanePath is distributed in the hope that it will be useful, but
206 WITHOUT ANY WARRANTY; without even the implied warranty of
207 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
208 General Public License for more details.
209 You should have received a copy of the GNU General Public License along
211 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
212perl v5.28.0 2017-12-03Math::PlanePath::KochSnowflakes(3)