1Math::PlanePath::DiagonUaslesrOcCtoannttr(i3b)uted PerlMDaotchu:m:ePnltaanteiPoanth::DiagonalsOctant(3)
2
6 Math::PlanePath::DiagonalsOctant -- points in diagonal stripes for an
7 eighth of the plane
8
10 use Math::PlanePath::DiagonalsOctant;
11 my $path = Math::PlanePath::DiagonalsOctant->new;
12 my ($x, $y) = $path->n_to_xy (123);
13
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 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 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 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 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 Direction
57 Option "direction => 'up'" reverses the order within each diagonal and
58 counts upward from the centre to the Y axis.
59 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 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 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 n_start => 0 n_start=>0
90 direction => "down" direction=>"up"
91 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
103 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
104 classes.
105 "$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 "($x,$y) = $path->n_to_xy ($n)"
112 Return the X,Y coordinates of point number $n on the path.
113 For "$n < 0.5" the return is an empty list, it being considered the
115 path begins at 1.
116 "$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 "($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
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 Nstart = d*d+1
134 where d numbers diagonal pairs, eg. d=3 for X=0,Y=5 going down. This
136 is easily reversed as
137 d = floor sqrt(N-1)
139 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 d = floor sqrt(N-0.5)
144 = int( sqrt(int(4*$n)-2)/2 )
145 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 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 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 Nrem = N - (d*(d+1)+1)
158 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 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 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 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 For "up" direction the Nrem and d are the same, but the coordinate
177 directions reverse.
178 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 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 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 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 | | /
201 | | /
202 +-------- if x1 < 0 then x1 = 0
203 x1 | / increase x1 to within octant
204 |/
205 +
206 | |/
208 | | if y1 < x1 then y1 = x1
209 | /| increase y1 to bottom-left within octant
210 |/ +----y1
211 + x1
212 And for the top right,
214 | / 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
223 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
224 this path include
225 <http://oeis.org/A055087> (etc)
227 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 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 either direction, n_start=0
243 A055086 X+Y, k repeating floor(k/2)+1 times
244 A004652 N start and end of each even-numbered diagonal
246 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 A056537 N of DiagonalsOctant at X,Y in PyramidRows order
254 inverse of A056536
255
257 Math::PlanePath, Math::PlanePath::Diagonals,
258 Math::PlanePath::DiagonalsAlternating, Math::PlanePath::PyramidRows
259
261 <http://user42.tuxfamily.org/math-planepath/index.html>
262
264 Copyright 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
265 This file is part of Math-PlanePath.
267 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 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 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/>.
280perl v5.28.1 2017-12-03Math::PlanePath::DiagonalsOctant(3)