--- name: "Math::PlanePath::Diagonals" section: "3pm" platform: "linux" package: "libmath-planepath-perl" version: "129-1" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::PlanePath::Diagonals" --- # Math::PlanePath::Diagonals(3pm) ## 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 \ (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 \ ## 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 \.