Provided by: libmath-planepath-perl_129-1_all bug

NAME

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

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

               (X+Y)^2 + 3X + Y
             = ---------------- + Nstart       (using one square)
                       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 = X - d

       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 therefore 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 minimum N and the upper right is
       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

           either direction=up,down
             A097806    turn 0=straight, 1=not straight

           direction=down, x_start=1, y_start=1
             A057555    X,Y pairs
             A057046    X at N=2^k
             A057047    Y at N=2^k

           direction=down, n_start=0
             A057554    X,Y pairs
             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=up,down
             A038722    permutation N at transpose Y,X
                          which is direction=down <-> direction=up

           either direction, x_start=1, y_start=1
             A003991    X*Y coordinate product
             A003989    GCD(X,Y) greatest common divisor starting (1,1)
             A003983    min(X,Y)
             A051125    max(X,Y)

           either direction, n_start=0
             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

SEE ALSO

       Math::PlanePath, Math::PlanePath::DiagonalsAlternating, Math::PlanePath::DiagonalsOctant,
       Math::PlanePath::Corner, Math::PlanePath::Rows, Math::PlanePath::Columns

HOME PAGE

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

LICENSE

       Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde

       This 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/>.