1Math::PlanePath::DiagonUaslesrOcCtoannttr(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::DiagonalsOctant(3)
2
3
4

NAME

6       Math::PlanePath::DiagonalsOctant -- points in diagonal stripes for an
7       eighth of the plane
8

SYNOPSIS

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

DESCRIPTION

15       This path follows successive diagonals downwards from the Y axis down
16       to the X=Y centre line, traversing the eighth of the plane on and above
17       X=Y.
18
19           8 |  21 27 33 40 47 55 63 72 81
20             |    \  \  \  \  \  \  \
21           7 |  17 22 28 34 41 48 56 64
22             |    \  \  \  \  \  \
23           6 |  13 18 23 29 35 42 49
24             |    \  \  \  \  \
25           5 |  10 14 19 24 30 36
26             |    \  \  \  \
27           4 |   7 11 15 20 25
28             |    \  \  \
29           3 |   5  8 12 16
30             |    \  \
31           2 |   3  6  9
32             |    \
33           1 |   2  4
34             |
35         Y=0 |   1
36             + ----------------------------
37               X=0  1  2  3  4  5  6  7  8
38
39       N=1,4,9,16,etc on the X=Y leading diagonal are the perfect squares.
40       N=2,6,12,20,etc at the ends of the other diagonals are the pronic
41       numbers k*(k+1).
42
43       Incidentally "octant" usually refers to an eighth of a 3-dimensional
44       coordinate space.  Since "PlanePath" is only 2 dimensions there's no
45       confusion and at the risk of abusing nomenclature half a quadrant is
46       reckoned as an "octant".
47
48   Pyramid Rows
49       Taking two diagonals running from k^2+1 to (k+1)^2 is the same as a row
50       of the step=2 "PyramidRows" (see Math::PlanePath::PyramidRows).  Each
51       endpoint is the same, but here it's two diagonals instead of one row.
52       For example in the "PyramidRows" the Y=3 row runs from N=10 to N=16
53       ending at X=3,Y=3.  Here that's in two diagonals N=10 to N=12 and then
54       N=13 to N=16, and that N=16 endpoint is the same X=3,Y=3.
55
56   Direction
57       Option "direction => 'up'" reverses the order within each diagonal and
58       counts upward from the centre to the Y axis.
59
60           8 |  25 29 34 39 45 51 58 65 73
61             |    \  \  \  \  \  \  \
62           7 |  20 24 28 33 38 44 50 57
63             |    \  \  \  \  \  \
64           6 |  16 19 23 27 32 37 43
65             |    \  \  \  \  \
66           5 |  12 15 18 22 26 31
67             |    \  \  \  \
68           4 |   9 11 14 17 21             direction => "up"
69             |    \  \  \
70           3 |   6  8 10 13
71             |    \  \
72           2 |   4  5  7
73             |    \
74           1 |   2  3
75             |
76         Y=0 |   1
77             +---------------------------
78               X=0  1  2  3  4  5  6  7  8
79
80       In this arrangement N=1,2,4,6,9,etc on the Y axis are alternately the
81       squares and the pronic numbers.  The squares are on even Y and pronic
82       on odd Y.
83
84   N Start
85       The default is to number points starting N=1 as shown above.  An
86       optional "n_start" can give a different start, in the same diagonals
87       sequence.  For example to start at 0,
88
89           n_start => 0                    n_start=>0
90           direction => "down"             direction=>"up"
91
92             6  | 12                        | 15
93             5  |  9 13                     | 11 14
94             4  |  6 10 14                  |  8 10 13
95             3  |  4  7 11 15               |  5  7  9 12
96             2  |  2  5  8                  |  3  4  6
97             1  |  1  3                     |  1  2
98           Y=0  |  0                        |  0
99                +--------------             +--------------
100                 X=0  1  2  3                X=0  1  2  3
101

FUNCTIONS

103       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
104       classes.
105
106       "$path = Math::PlanePath::DiagonalsOctant->new ()"
107       "$path = Math::PlanePath::DiagonalsOctant->new (direction => $str,
108       n_start => $n)"
109           Create and return a new path object.
110
111       "($x,$y) = $path->n_to_xy ($n)"
112           Return the X,Y coordinates of point number $n on the path.
113
114           For "$n < 0.5" the return is an empty list, it being considered the
115           path begins at 1.
116
117       "$n = $path->xy_to_n ($x,$y)"
118           Return the point number for coordinates "$x,$y".  $x and $y are
119           each rounded to the nearest integer, which has the effect of
120           treating each point $n as a square of side 1.
121
122       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
123           The returned range is exact, meaning $n_lo and $n_hi are the
124           smallest and biggest in the rectangle.
125

FORMULAS

127   N to X,Y
128       To break N into X,Y it's convenient to take two diagonals at a time,
129       since the length then changes by 1 each pair making a quadratic.
130       Starting at each X=0,Y=odd just after perfect square N allows just a
131       sqrt.
132
133           Nstart = d*d+1
134
135       where d numbers diagonal pairs, eg. d=3 for X=0,Y=5 going down.  This
136       is easily reversed as
137
138           d = floor sqrt(N-1)
139
140       The code reckons the start of the diagonal as 0.5 further back, so that
141       N=9.5 is at X=-.5,Y=5.5.  To do that d is formed as
142
143           d = floor sqrt(N-0.5)
144             = int( sqrt(int(4*$n)-2)/2 )
145
146       Taking /2 out of the sqrt helps with "Math::BigInt" which circa Perl
147       5.14 doesn't inter-operate with flonums very well.
148
149       In any case N-Nstart is an offset into two diagonals, the first of
150       length d many points and the second d+1.  For example d=3 starting Y=5
151       for points N=10,11,12 followed by Y=6 N=13,14,15,16.
152
153       The formulas are simplified by calculating a remainder relative to the
154       second diagonal, so it's negative for the first and positive for the
155       second,
156
157           Nrem = N - (d*(d+1)+1)
158
159       d*(d+1)+1 is 1 past the pronic numbers when end each first diagonal, as
160       described above.  In any case for example d=3 is relative to N=13
161       making Nrem=-3,-2,-1 or Nrem=0,1,2,3.
162
163       To include the preceding 0.5 in the second diagonal simply means
164       reckoning Nrem>=-0.5 as belonging to the second.  In that base
165
166           if Nrem >= -0.5
167             X = Nrem            # direction="down"
168             Y = 2*d - Nrem
169           else
170             X = Nrem + d
171             Y = d - Nrem - 1
172
173       For example N=15 Nrem=1 is the first case, X=1, Y=2*3-1=5.  Or N=11
174       Nrem=-2 the second X=-2+3=1, Y=3-(-2)-1=4.
175
176       For "up" direction the Nrem and d are the same, but the coordinate
177       directions reverse.
178
179           if Nrem >= -0.5
180             X = d - Nrem        # direction="up"
181             Y = d + Nrem
182           else
183             X = -Nrem - 1
184             Y = 2d + Nrem
185
186       Another way is to reckon Nstart from the X=0,Y=even diagonals, which is
187       then two diagonals of the same length and d formed by a sqrt inverting
188       a pronic Nstart=d*(d+1).
189
190   Rectangle to N Range
191       Within each row increasing X is increasing N, and in each column
192       increasing Y is increasing N.  This is so in both "down" and "up"
193       arrangements.  On that basis in a rectangle the lower left corner is
194       the minimum N and the upper right is the maximum N.
195
196       If the rectangle is partly outside the covered octant then the corners
197       must be shifted to put them in range, ie. trim off any rows or columns
198       entirely outside the rectangle.  For the lower left this means,
199
200             |  |    /
201             |  |   /
202             +--------          if x1 < 0 then x1 = 0
203           x1   | /             increase x1 to within octant
204                |/
205                +
206
207                |  |/
208                |  |            if y1 < x1 then y1 = x1
209                | /|            increase y1 to bottom-left within octant
210                |/ +----y1
211                +  x1
212
213       And for the top right,
214
215                |    /  x2
216                | ------+ y2    if x2 > y2 then x2 = y2
217                |  /    |       decrease x2 so top-right within octant
218                | /     |         (the end of the y2 row)
219                |/
220                +
221

OEIS

223       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
224       this path include
225
226           <http://oeis.org/A055087> (etc)
227
228           direction=down
229             A002620    N at end each run X=k,Y=k and X=k,Y=k+1
230           direction=down, n_start=0
231             A055087    X coord, runs 0 to k twice
232             A082375    Y-X, runs k to 0 or 1 stepping by 2
233             A005563    N on X=Y diagonal, X*(X+2)
234
235           direction=up
236             A002620    N on Y axis, end of each run, quarter squares
237           direction=up, n_start=0
238             A024206    N on Y axis (starting from n=1 is Y=0, so Y=n-1)
239             A014616    N in column X=1 (is Y axis N-1, from N=3)
240             A002378    N on X=Y diagonal, pronic X*(X+1)
241
242           either direction, n_start=0
243             A055086    X+Y, k repeating floor(k/2)+1 times
244
245           A004652      N start and end of each even-numbered diagonal
246
247           permutations
248             A056536     N of PyramidRows in DiagonalsOctant order
249             A091995      with DiagonalsOctant direction=up
250             A091018      N-1, ie. starting from 0
251             A090894      N-1 and DiagonalsOctant direction=up
252
253             A056537     N of DiagonalsOctant at X,Y in PyramidRows order
254                          inverse of A056536
255

SEE ALSO

257       Math::PlanePath, Math::PlanePath::Diagonals,
258       Math::PlanePath::DiagonalsAlternating, Math::PlanePath::PyramidRows
259

HOME PAGE

261       <http://user42.tuxfamily.org/math-planepath/index.html>
262

LICENSE

264       Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
265
266       This file is part of Math-PlanePath.
267
268       Math-PlanePath is free software; you can redistribute it and/or modify
269       it under the terms of the GNU General Public License as published by
270       the Free Software Foundation; either version 3, or (at your option) any
271       later version.
272
273       Math-PlanePath is distributed in the hope that it will be useful, but
274       WITHOUT ANY WARRANTY; without even the implied warranty of
275       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
276       General Public License for more details.
277
278       You should have received a copy of the GNU General Public License along
279       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
280
281
282
283perl v5.32.0                      2020-07-28Math::PlanePath::DiagonalsOctant(3)
Impressum