SYNOPSIS
use Math::PlanePath::Diagonals;
my $path = Math::PlanePath::Diagonals->new;
my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION
This path follows successive diagonals going from the Y axis down to the X axis.
6 | 22
5 | 16 23
4 | 11 17 24
3 | 7 12 18 ...
2 | 4 8 13 19
1 | 2 5 9 14 20
Y=0 | 1 3 6 10 15 21
+-------------------------
X=0 1 2 3 4 5
N=1,3,6,10,etc on the X axis is the triangular numbers. N=1,2,4,7,11,etc on the Y axis is the triangular plus 1, the next point visited after the X axis.
Direction
Option "direction => 'up'" reverses the order within each diagonal to count upward from the X axis.
direction => "up"
5 | 21
4 | 15 20
3 | 10 14 19 ...
2 | 6 9 13 18 24
1 | 3 5 8 12 17 23
Y=0 | 1 2 4 7 11 16 22
+-----------------------------
X=0 1 2 3 4 5 6
This is merely a transpose changing X,Y to Y,X, but it's the same as in "DiagonalsOctant" and can be handy to control the direction when combining "Diagonals" with some other path or calculation.
N Start
The default is to number points starting N=1 as shown above. An optional "n_start" can give a different start, in the same diagonals sequence. For example to start at 0,
n_start => 0, n_start=>0
direction=>"down" direction=>"up"
4 | 10 | 14
3 | 6 11 | 9 13
2 | 3 7 12 | 5 8 12
1 | 1 4 8 13 | 2 4 7 11
Y=0 | 0 2 5 9 14 | 0 1 3 6 10
+----------------- +-----------------
X=0 1 2 3 4 X=0 1 2 3 4
N=0,1,3,6,10,etc on the Y axis of ``down'' or the X axis of ``up'' is the triangular numbers Y*(Y+1)/2.
X,Y Start
Options "x_start => $x" and "y_start => $y" give a starting position for the diagonals. For example to start at X=1,Y=1
7 | 22 x_start => 1,
6 | 16 23 y_start => 1
5 | 11 17 24
4 | 7 12 18 ...
3 | 4 8 13 19
2 | 2 5 9 14 20
1 | 1 3 6 10 15 21
Y=0 |
+------------------
X=0 1 2 3 4 5
The effect is merely to add a fixed offset to all X,Y values taken and returned, but it can be handy to have the path do that to step through non-negatives or similar.
FUNCTIONS
See ``FUNCTIONS'' in Math::PlanePath for behaviour common to all path classes.- "$path = Math::PlanePath::Diagonals->new ()"
- "$path = Math::PlanePath::Diagonals->new (direction => $str, n_start => $n, x_start => $x, y_start => $y)"
-
Create and return a new path object. The "direction" option (a string) can
be
direction => "down" the default direction => "up" number upwards from the X axis - "($x,$y) = $path->n_to_xy ($n)"
-
Return the X,Y coordinates of point number $n on the path.
For "$n < 0.5" the return is an empty list, it being considered the path begins at 1.
- "$n = $path->xy_to_n ($x,$y)"
- Return the point number for coordinates "$x,$y". $x and $y are each rounded to the nearest integer, which has the effect of treating each point $n as a square of side 1, so the quadrant x>=-0.5, y>=-0.5 is entirely covered.
- "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
- The returned range is exact, meaning $n_lo and $n_hi are the smallest and biggest in the rectangle.
FORMULAS
X,Y to N
The sum d=X+Y numbers each diagonal from d=0 upwards, corresponding to the Y coordinate where the diagonal starts (or X if direction=up).
d=2
\
d=1 \
\ \
d=0 \ \
\ \ \
N is then given by
d = X+Y
N = d*(d+1)/2 + X + Nstart
The d*(d+1)/2 shows how the triangular numbers fall on the Y axis when X=0 and Nstart=0. For the default Nstart=1 it's 1 more than the triangulars, as noted above.
d can be expanded out to the following quite symmetric form. This almost suggests something parabolic but is still the straight line diagonals.
X^2 + 3X + 2XY + Y + Y^2
N = ------------------------ + Nstart
2
N to X,Y
The above formula N=d*(d+1)/2 can be solved for d as
d = floor( (sqrt(8*N+1) - 1)/2 )
# with n_start=0
For example N=12 is d=floor((sqrt(8*12+1)-1)/2)=4 as that N falls in the fifth diagonal. Then the offset from the Y axis NY=d*(d-1)/2 is the X position,
X = N - d*(d-1)/2
Y = d - X
In the code fractional N is handled by imagining each diagonal beginning 0.5 back from the Y axis. That's handled by adding 0.5 into the sqrt, which is +4 onto the 8*N.
d = floor( (sqrt(8*N+5) - 1)/2 )
# N>=-0.5
The X and Y formulas are unchanged, since N=d*(d-1)/2 is still the Y axis. But each diagonal d begins up to 0.5 before that and therefor X extends back to -0.5.
Rectangle to N Range
Within each row increasing X is increasing N, and in each column increasing Y is increasing N. So in a rectangle the lower left corner is the minimum N and the upper right is the maximum N.
| \ \ N max
| \ ----------+
| | \ |\
| |\ \ |
| \| \ \ |
| +----------
| N min \ \ \
+-------------------------
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
- <http://oeis.org/A002262> (etc)
direction=down (the default)
A002262 X coordinate, runs 0 to k
A025581 Y coordinate, runs k to 0
A003056 X+Y coordinate sum, k repeated k+1 times
A114327 Y-X coordinate diff
A101080 HammingDist(X,Y)
A127949 dY, change in Y coordinate
A000124 N on Y axis, triangular numbers + 1
A001844 N on X=Y diagonal
A185787 total N in row to X=Y diagonal
A185788 total N in row to X=Y-1
A100182 total N in column to Y=X diagonal
A101165 total N in column to Y=X-1
A185506 total N in rectangle 0,0 to X,Y
direction=down, n_start=0
A023531 dSum = dX+dY, being 1 at N=triangular+1 (and 0)
A000096 N on X axis, X*(X+3)/2
A000217 N on Y axis, the triangular numbers
A129184 turn 1=left,0=right
A103451 turn 1=left or right,0=straight, but extra initial 1
A103452 turn 1=left,0=straight,-1=right, but extra initial 1
direction=up, n_start=0
A129184 turn 0=left,1=right
direction=up, n_start=-1
A023531 turn 1=left,0=right
direction=down, n_start=-1
A023531 turn 0=left,1=right
in direction=up the X,Y coordinate forms are the same but swap X,Y
either direction, n_start=1
A038722 permutation N at transpose Y,X
which is direction=down <-> direction=up
n_start=1, x_start=1, y_start=1, either direction
A003991 X*Y coordinate product
A003989 GCD(X,Y) greatest common divisor starting (1,1)
A003983 min(X,Y)
A051125 max(X,Y)
n_start=1, x_start=1, y_start=1, direction=down
A057046 X for N=2^k
A057047 Y for N=2^k
n_start=0 (either direction)
A049581 abs(X-Y) coordinate diff
A004197 min(X,Y)
A003984 max(X,Y)
A004247 X*Y coordinate product
A048147 X^2+Y^2
A109004 GCD(X,Y) greatest common divisor starting (0,0)
A004198 X bit-and Y
A003986 X bit-or Y
A003987 X bit-xor Y
A156319 turn 0=straight,1=left,2=right
A061579 permutation N at transpose Y,X
which is direction=down <-> direction=up
LICENSE
Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016 Kevin RydeThis file is part of Math-PlanePath.
Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.