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 nonnegatives 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*(d1)/2 is the X position,
X = N  d*(d1)/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*(d1)/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 YX 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=Y1 A100182 total N in column to Y=X diagonal A101165 total N in column to Y=X1 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(XY) 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 bitand Y A003986 X bitor Y A003987 X bitxor 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 MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.