1Math::PlanePath::DiagonUaslesr(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::Diagonals(3)
2
3
4

NAME

6       Math::PlanePath::Diagonals -- points in diagonal stripes
7

SYNOPSIS

9        use Math::PlanePath::Diagonals;
10        my $path = Math::PlanePath::Diagonals->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This path follows successive diagonals going from the Y axis down to
15       the X axis.
16
17             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
27       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
31   Direction
32       Option "direction => 'up'" reverses the order within each diagonal to
33       count upward from the X axis.
34
35           direction => "up"
36
37             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
46       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
50   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
55           n_start => 0,                    n_start=>0
56           direction=>"down"                direction=>"up"
57
58             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
66       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
69   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
73             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
84       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

FUNCTIONS

89       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
90       classes.
91
92       "$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
98               direction => "down"       the default
99               direction => "up"         number upwards from the X axis
100
101       "($x,$y) = $path->n_to_xy ($n)"
102           Return the X,Y coordinates of point number $n on the path.
103
104           For "$n < 0.5" the return is an empty list, it being considered the
105           path begins at 1.
106
107       "$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
113       "($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

FORMULAS

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
122           d=2
123               \
124           d=1  \
125               \ \
126           d=0  \ \
127               \ \ \
128
129       N is then given by
130
131           d = X+Y
132           N = d*(d+1)/2 + X + Nstart
133
134       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
138       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
142               X^2 + 3X + 2XY + Y + Y^2
143           N = ------------------------ + Nstart
144                          2
145
146               (X+Y)^2 + 3X + Y
147             = ---------------- + Nstart       (using one square)
148                       2
149
150   N to X,Y
151       The above formula N=d*(d+1)/2 can be solved for d as
152
153           d = floor( (sqrt(8*N+1) - 1)/2 )
154           # with n_start=0
155
156       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
160           X = N - d*(d+1)/2
161           Y = X - d
162
163       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
167           d = floor( (sqrt(8*N+5) - 1)/2 )
168           # N>=-0.5
169
170       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
174   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
179           |            \     \ N max
180           |       \ ----------+
181           |        |     \    |\
182           |        |\     \   |
183           |       \| \     \  |
184           |        +----------
185           |  N min  \  \     \
186           +-------------------------
187

OEIS

189       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
190       this path include
191
192           <http://oeis.org/A002262> (etc)
193
194           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
201             A127949    dY, change in Y coordinate
202
203             A000124    N on Y axis, triangular numbers + 1
204             A001844    N on X=Y diagonal
205
206             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
212           either direction=up,down
213             A097806    turn 0=straight, 1=not straight
214
215           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
220           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
231           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
236           in direction=up the X,Y coordinate forms are the same but swap X,Y
237
238           either direction=up,down
239             A038722    permutation N at transpose Y,X
240                          which is direction=down <-> direction=up
241
242           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
248           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
260             A061579    permutation N at transpose Y,X
261                          which is direction=down <-> direction=up
262

SEE ALSO

264       Math::PlanePath, Math::PlanePath::DiagonalsAlternating,
265       Math::PlanePath::DiagonalsOctant, Math::PlanePath::Corner,
266       Math::PlanePath::Rows, Math::PlanePath::Columns
267

HOME PAGE

269       <http://user42.tuxfamily.org/math-planepath/index.html>
270

LICENSE

272       Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019,
273       2020 Kevin Ryde
274
275       This file is part of Math-PlanePath.
276
277       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
282       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
287       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/>.
289
290
291
292perl v5.32.1                      2021-01-27     Math::PlanePath::Diagonals(3)
Impressum