1Math::PlanePath::DiagonUaslesr(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::Diagonals(3)
2
6 Math::PlanePath::Diagonals -- points in diagonal stripes
7
9 use Math::PlanePath::Diagonals;
10 my $path = Math::PlanePath::Diagonals->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path follows successive diagonals going from the Y axis down to
15 the X axis.
16 6 | 22
18 5 | 16 23
19 4 | 11 17 24
20 3 | 7 12 18 ...
21 2 | 4 8 13 19
22 1 | 2 5 9 14 20
23 Y=0 | 1 3 6 10 15 21
24 +-------------------------
25 X=0 1 2 3 4 5
26 N=1,3,6,10,etc on the X axis is the triangular numbers.
28 N=1,2,4,7,11,etc on the Y axis is the triangular plus 1, the next point
29 visited after the X axis.
30 Direction
32 Option "direction => 'up'" reverses the order within each diagonal to
33 count upward from the X axis.
34 direction => "up"
36 5 | 21
38 4 | 15 20
39 3 | 10 14 19 ...
40 2 | 6 9 13 18 24
41 1 | 3 5 8 12 17 23
42 Y=0 | 1 2 4 7 11 16 22
43 +-----------------------------
44 X=0 1 2 3 4 5 6
45 This is merely a transpose changing X,Y to Y,X, but it's the same as in
47 "DiagonalsOctant" and can be handy to control the direction when
48 combining "Diagonals" with some other path or calculation.
49 N Start
51 The default is to number points starting N=1 as shown above. An
52 optional "n_start" can give a different start, in the same diagonals
53 sequence. For example to start at 0,
54 n_start => 0, n_start=>0
56 direction=>"down" direction=>"up"
57 4 | 10 | 14
59 3 | 6 11 | 9 13
60 2 | 3 7 12 | 5 8 12
61 1 | 1 4 8 13 | 2 4 7 11
62 Y=0 | 0 2 5 9 14 | 0 1 3 6 10
63 +----------------- +-----------------
64 X=0 1 2 3 4 X=0 1 2 3 4
65 N=0,1,3,6,10,etc on the Y axis of "down" or the X axis of "up" is the
67 triangular numbers Y*(Y+1)/2.
68 X,Y Start
70 Options "x_start => $x" and "y_start => $y" give a starting position
71 for the diagonals. For example to start at X=1,Y=1
72 7 | 22 x_start => 1,
74 6 | 16 23 y_start => 1
75 5 | 11 17 24
76 4 | 7 12 18 ...
77 3 | 4 8 13 19
78 2 | 2 5 9 14 20
79 1 | 1 3 6 10 15 21
80 Y=0 |
81 +------------------
82 X=0 1 2 3 4 5
83 The effect is merely to add a fixed offset to all X,Y values taken and
85 returned, but it can be handy to have the path do that to step through
86 non-negatives or similar.
87
89 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
90 classes.
91 "$path = Math::PlanePath::Diagonals->new ()"
93 "$path = Math::PlanePath::Diagonals->new (direction => $str, n_start =>
94 $n, x_start => $x, y_start => $y)"
95 Create and return a new path object. The "direction" option (a
96 string) can be
97 direction => "down" the default
99 direction => "up" number upwards from the X axis
100 "($x,$y) = $path->n_to_xy ($n)"
102 Return the X,Y coordinates of point number $n on the path.
103 For "$n < 0.5" the return is an empty list, it being considered the
105 path begins at 1.
106 "$n = $path->xy_to_n ($x,$y)"
108 Return the point number for coordinates "$x,$y". $x and $y are
109 each rounded to the nearest integer, which has the effect of
110 treating each point $n as a square of side 1, so the quadrant
111 x>=-0.5, y>=-0.5 is entirely covered.
112 "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
114 The returned range is exact, meaning $n_lo and $n_hi are the
115 smallest and biggest in the rectangle.
116
118 X,Y to N
119 The sum d=X+Y numbers each diagonal from d=0 upwards, corresponding to
120 the Y coordinate where the diagonal starts (or X if direction=up).
121 d=2
123 \
124 d=1 \
125 \ \
126 d=0 \ \
127 \ \ \
128 N is then given by
130 d = X+Y
132 N = d*(d+1)/2 + X + Nstart
133 The d*(d+1)/2 shows how the triangular numbers fall on the Y axis when
135 X=0 and Nstart=0. For the default Nstart=1 it's 1 more than the
136 triangulars, as noted above.
137 d can be expanded out to the following quite symmetric form. This
139 almost suggests something parabolic but is still the straight line
140 diagonals.
141 X^2 + 3X + 2XY + Y + Y^2
143 N = ------------------------ + Nstart
144 2
145 (X+Y)^2 + 3X + Y
147 = ---------------- + Nstart (using one square)
148 2
149 N to X,Y
151 The above formula N=d*(d+1)/2 can be solved for d as
152 d = floor( (sqrt(8*N+1) - 1)/2 )
154 # with n_start=0
155 For example N=12 is d=floor((sqrt(8*12+1)-1)/2)=4 as that N falls in
157 the fifth diagonal. Then the offset from the Y axis NY=d*(d-1)/2 is
158 the X position,
159 X = N - d*(d+1)/2
161 Y = X - d
162 In the code, fractional N is handled by imagining each diagonal
164 beginning 0.5 back from the Y axis. That's handled by adding 0.5 into
165 the sqrt, which is +4 onto the 8*N.
166 d = floor( (sqrt(8*N+5) - 1)/2 )
168 # N>=-0.5
169 The X and Y formulas are unchanged, since N=d*(d-1)/2 is still the Y
171 axis. But each diagonal d begins up to 0.5 before that and therefore X
172 extends back to -0.5.
173 Rectangle to N Range
175 Within each row increasing X is increasing N, and in each column
176 increasing Y is increasing N. So in a rectangle the lower left corner
177 is minimum N and the upper right is maximum N.
178 | \ \ N max
180 | \ ----------+
181 | | \ |\
182 | |\ \ |
183 | \| \ \ |
184 | +----------
185 | N min \ \ \
186 +-------------------------
187
189 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
190 this path include
191 <http://oeis.org/A002262> (etc)
193 direction=down (the default)
195 A002262 X coordinate, runs 0 to k
196 A025581 Y coordinate, runs k to 0
197 A003056 X+Y coordinate sum, k repeated k+1 times
198 A114327 Y-X coordinate diff
199 A101080 HammingDist(X,Y)
200 A127949 dY, change in Y coordinate
202 A000124 N on Y axis, triangular numbers + 1
204 A001844 N on X=Y diagonal
205 A185787 total N in row to X=Y diagonal
207 A185788 total N in row to X=Y-1
208 A100182 total N in column to Y=X diagonal
209 A101165 total N in column to Y=X-1
210 A185506 total N in rectangle 0,0 to X,Y
211 either direction=up,down
213 A097806 turn 0=straight, 1=not straight
214 direction=down, x_start=1, y_start=1
216 A057555 X,Y pairs
217 A057046 X at N=2^k
218 A057047 Y at N=2^k
219 direction=down, n_start=0
221 A057554 X,Y pairs
222 A023531 dSum = dX+dY, being 1 at N=triangular+1 (and 0)
223 A000096 N on X axis, X*(X+3)/2
224 A000217 N on Y axis, the triangular numbers
225 A129184 turn 1=left,0=right
226 A103451 turn 1=left or right,0=straight, but extra initial 1
227 A103452 turn 1=left,0=straight,-1=right, but extra initial 1
228 direction=up, n_start=0
229 A129184 turn 0=left,1=right
230 direction=up, n_start=-1
232 A023531 turn 1=left,0=right
233 direction=down, n_start=-1
234 A023531 turn 0=left,1=right
235 in direction=up the X,Y coordinate forms are the same but swap X,Y
237 either direction=up,down
239 A038722 permutation N at transpose Y,X
240 which is direction=down <-> direction=up
241 either direction, x_start=1, y_start=1
243 A003991 X*Y coordinate product
244 A003989 GCD(X,Y) greatest common divisor starting (1,1)
245 A003983 min(X,Y)
246 A051125 max(X,Y)
247 either direction, n_start=0
249 A049581 abs(X-Y) coordinate diff
250 A004197 min(X,Y)
251 A003984 max(X,Y)
252 A004247 X*Y coordinate product
253 A048147 X^2+Y^2
254 A109004 GCD(X,Y) greatest common divisor starting (0,0)
255 A004198 X bit-and Y
256 A003986 X bit-or Y
257 A003987 X bit-xor Y
258 A156319 turn 0=straight,1=left,2=right
259 A061579 permutation N at transpose Y,X
261 which is direction=down <-> direction=up
262
264 Math::PlanePath, Math::PlanePath::DiagonalsAlternating,
265 Math::PlanePath::DiagonalsOctant, Math::PlanePath::Corner,
266 Math::PlanePath::Rows, Math::PlanePath::Columns
267
269 <http://user42.tuxfamily.org/math-planepath/index.html>
270
272 Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019,
273 2020 Kevin Ryde
274 This file is part of Math-PlanePath.
276 Math-PlanePath is free software; you can redistribute it and/or modify
278 it under the terms of the GNU General Public License as published by
279 the Free Software Foundation; either version 3, or (at your option) any
280 later version.
281 Math-PlanePath is distributed in the hope that it will be useful, but
283 WITHOUT ANY WARRANTY; without even the implied warranty of
284 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
285 General Public License for more details.
286 You should have received a copy of the GNU General Public License along
288 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
289perl v5.34.0 2022-01-21 Math::PlanePath::Diagonals(3)