1Math::PlanePath::AztecDUisaemronCdoRnitnrgisb(u3t)ed PerMlatDho:c:uPmleannteaPtaitohn::AztecDiamondRings(3)
2
6 Math::PlanePath::AztecDiamondRings -- rings around an Aztec diamond
7 shape
8
10 use Math::PlanePath::AztecDiamondRings;
11 my $path = Math::PlanePath::AztecDiamondRings->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
15 This path makes rings around an Aztec diamond shape,
16 46-45 4
18 / \
19 47 29-28 44 3
20 / / \ \
21 48 30 16-15 27 43 ... 2
22 / / / \ \ \ \
23 49 31 17 7--6 14 26 42 62 1
24 / / / / \ \ \ \ \
25 50 32 18 8 2--1 5 13 25 41 61 <- Y=0
26 | | | | | | | | | |
27 51 33 19 9 3--4 12 24 40 60 -1
28 \ \ \ \ / / / /
29 52 34 20 10-11 23 39 59 -2
30 \ \ \ / / /
31 53 35 21-22 38 58 -3
32 \ \ / /
33 54 36-37 57 -4
34 \ /
35 55-56 -5
36 ^
38 -5 -4 -3 -2 -1 X=0 1 2 3 4 5
39 This is similar to the "DiamondSpiral", but has all four corners
41 flattened to 2 vertical or horizontal, instead of just one in the
42 "DiamondSpiral". This is only a small change to the alignment of
43 numbers in the sides, but is more symmetric.
44 Y axis N=1,6,15,28,45,66,etc are the hexagonal numbers k*(2k-1). The
46 hexagonal numbers of the "second kind" 3,10,21,36,55,78, etc k*(2k+1),
47 are the vertical at X=-1 going downwards. Combining those two is the
48 triangular numbers 3,6,10,15,21,etc, k*(k+1)/2, alternately on one line
49 and the other. Those are the positions of all the horizontal steps,
50 ie. where dY=0.
51 X axis N=1,5,13,25,etc is the "centred square numbers". Those numbers
53 are made by drawing concentric squares with an extra point on each side
54 each time. The path here grows the same way, adding one extra point to
55 each of the four sides.
56 *---*---*---*
58 | |
59 | *---*---* | count total "*"s for
60 | | | | centred square numbers
61 * | *---* | *
62 | | | | | |
63 | * | * | * |
64 | | | | | |
65 | | *---* | |
66 * | | *
67 | *---*---* |
68 | |
69 *---*---*---*
70 N Start
72 The default is to number points starting N=1 as shown above. An
73 optional "n_start" can give a different start, in the same pattern.
74 For example to start at 0,
75 n_start => 0
77 45 44
79 46 28 27 43
80 47 29 15 14 26 42
81 48 30 16 6 5 13 25 41
82 49 31 17 7 1 0 4 12 24 40
83 50 32 18 8 2 3 11 23 39 59
84 51 33 19 9 10 22 38 58
85 52 34 20 21 37 57
86 53 35 36 56
87 54 55
88
90 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
91 classes.
92 "$path = Math::PlanePath::AztecDiamondRings->new ()"
94 "$path = Math::PlanePath::AztecDiamondRings->new (n_start => $n)"
95 Create and return a new Aztec diamond spiral object.
96 "($x,$y) = $path->n_to_xy ($n)"
98 Return the X,Y coordinates of point number $n on the path.
99 For "$n < 1" the return is an empty list, it being considered the
101 path starts at 1.
102 "$n = $path->xy_to_n ($x,$y)"
104 Return the point number for coordinates "$x,$y". $x and $y are
105 each rounded to the nearest integer, which has the effect of
106 treating each point in the path as a square of side 1, so the
107 entire plane is covered.
108 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
110 The returned range is exact, meaning $n_lo and $n_hi are the
111 smallest and biggest in the rectangle.
112
114 X,Y to N
115 The path makes lines in each quadrant. The quadrant is determined by
116 the signs of X and Y, then the line in that quadrant is either d=X+Y or
117 d=X-Y. A quadratic in d gives a starting N for the line and Y (or X if
118 desired) is an offset from there,
119 Y>=0 X>=0 d=X+Y N=(2d+2)*d+1 + Y
121 Y>=0 X<0 d=Y-X N=2d^2 - Y
122 Y<0 X>=0 d=X-Y N=(2d+2)*d+1 + Y
123 Y<0 X<0 d=X+Y N=(2d+4)*d+2 - Y
124 For example
126 Y=2 X=3 d=2+3=5 N=(2*5+2)*5+1 + 2 = 63
128 Y=2 X=-1 d=2-(-1)=3 N=2*3*3 - 2 = 16
129 Y=-1 X=4 d=4-(-1)=5 N=(2*5+2)*5+1 + -1 = 60
130 Y=-2 X=-3 d=-3+(-2)=-5 N=(2*-5+4)*-5+2 - (-2) = 34
131 The two X>=0 cases are the same N formula and can be combined with an
133 abs,
134 X>=0 d=X+abs(Y) N=(2d+2)*d+1 + Y
136 This works because at Y=0 the last line of one ring joins up to the
138 start of the next. For example N=11 to N=15,
139 15 2
141 \
142 14 1
143 \
144 13 <- Y=0
145 12 -1
147 /
148 11 -2
149 ^
151 X=0 1 2
152 Rectangle to N Range
154 Within each row N increases as X increases away from the Y axis, and
155 within each column similarly N increases as Y increases away from the X
156 axis. So in a rectangle the maximum N is at one of the four corners of
157 the rectangle.
158 |
160 x1,y2 M---|----M x2,y2
161 | | |
162 -------O---------
163 | | |
164 | | |
165 x1,y1 M---|----M x1,y1
166 |
167 For any two rows y1 and y2, the values in row y2 are all bigger than in
169 y1 if y2>=-y1. This is so even when y1 and y2 are on the same side of
170 the origin, ie. both positive or both negative.
171 For any two columns x1 and x2, the values in the part with Y>=0 are all
173 bigger if x2>=-x1, or in the part of the columns with Y<0 it's
174 x2>=-x1-1. So the biggest corner is at
175 max_y = (y2 >= -y1 ? y2 ? y1)
177 max_x = (x2 >= -x1 - (max_y<0) ? x2 : x1)
178 The difference in the X handling for Y positive or negative is due to
180 the quadrant ordering. When Y>=0, at X and -X the bigger N is the X
181 negative side, but when Y<0 it's the X positive side.
182 A similar approach gives the minimum N in a rectangle.
184 min_y = / y2 if y2 < 0, and set xbase=-1
186 | y1 if y1 > 0, and set xbase=0
187 \ 0 otherwise, and set xbase=0
188 min_x = / x2 if x2 < xbase
190 | x1 if x1 > xbase
191 \ xbase otherwise
192 The minimum row is Y=0, but if that's not in the rectangle then the y2
194 or y1 top or bottom edge is the minimum. Then within any row the
195 minimum N is at xbase=0 if Y<0 or xbase=-1 if Y>=0. If that xbase is
196 not in range then the x2 or x1 left or right edge is the minimum.
197
199 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
200 this path include
201 <http://oeis.org/A001844> (etc)
203 n_start=1 (the default)
205 A001844 N on X axis, the centred squares 2k(k+1)+1
206 n_start=0
208 A046092 N on X axis, 4*triangular
209 A139277 N on diagonal X=Y
210 A023532 abs(dY), being 0 if N=k*(k+3)/2
211
213 Math::PlanePath, Math::PlanePath::DiamondSpiral
214
216 <http://user42.tuxfamily.org/math-planepath/index.html>
217
219 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
220 This file is part of Math-PlanePath.
222 Math-PlanePath is free software; you can redistribute it and/or modify
224 it under the terms of the GNU General Public License as published by
225 the Free Software Foundation; either version 3, or (at your option) any
226 later version.
227 Math-PlanePath is distributed in the hope that it will be useful, but
229 WITHOUT ANY WARRANTY; without even the implied warranty of
230 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
231 General Public License for more details.
232 You should have received a copy of the GNU General Public License along
234 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
235perl v5.32.0 2020-07-M2a8th::PlanePath::AztecDiamondRings(3)