.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::Diagonals 3pm" .TH Math::PlanePath::Diagonals 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::Diagonals \-\- points in diagonal stripes .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::Diagonals; \& my $path = Math::PlanePath::Diagonals\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path follows successive diagonals going from the Y axis down to the X axis. .PP .Vb 9 \& 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 .Ve .PP 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. .IX Xref "Triangular numbers" .SS "Direction" .IX Subsection "Direction" Option \f(CW\*(C`direction => \*(Aqup\*(Aq\*(C'\fR reverses the order within each diagonal to count upward from the X axis. .PP .Vb 1 \& 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 .Ve .PP This is merely a transpose changing X,Y to Y,X, but it's the same as in \&\f(CW\*(C`DiagonalsOctant\*(C'\fR and can be handy to control the direction when combining \&\f(CW\*(C`Diagonals\*(C'\fR with some other path or calculation. .SS "N Start" .IX Subsection "N Start" The default is to number points starting N=1 as shown above. An optional \&\f(CW\*(C`n_start\*(C'\fR can give a different start, in the same diagonals sequence. For example to start at 0, .PP .Vb 2 \& 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 .Ve .PP N=0,1,3,6,10,etc on the Y axis of \*(L"down\*(R" or the X axis of \*(L"up\*(R" is the triangular numbers Y*(Y+1)/2. .IX Xref "Triangular numbers" .SS "X,Y Start" .IX Subsection "X,Y Start" Options \f(CW\*(C`x_start => $x\*(C'\fR and \f(CW\*(C`y_start => $y\*(C'\fR give a starting position for the diagonals. For example to start at X=1,Y=1 .PP .Vb 10 \& 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 .Ve .PP 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. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::Diagonals\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::Diagonals\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::Diagonals->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::Diagonals\->new (direction => $str, n_start => $n, x_start => $x, y_start => $y)""" 4 .el .IP "\f(CW$path = Math::PlanePath::Diagonals\->new (direction => $str, n_start => $n, x_start => $x, y_start => $y)\fR" 4 .IX Item "$path = Math::PlanePath::Diagonals->new (direction => $str, n_start => $n, x_start => $x, y_start => $y)" .PD Create and return a new path object. The \f(CW\*(C`direction\*(C'\fR option (a string) can be .Sp .Vb 2 \& direction => "down" the default \& direction => "up" number upwards from the X axis .Ve .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. .Sp For \f(CW\*(C`$n < 0.5\*(C'\fR the return is an empty list, it being considered the path begins at 1. .ie n .IP """$n = $path\->xy_to_n ($x,$y)""" 4 .el .IP "\f(CW$n = $path\->xy_to_n ($x,$y)\fR" 4 .IX Item "$n = $path->xy_to_n ($x,$y)" Return the point number for coordinates \f(CW\*(C`$x,$y\*(C'\fR. \f(CW$x\fR and \f(CW$y\fR are each rounded to the nearest integer, which has the effect of treating each point \f(CW$n\fR as a square of side 1, so the quadrant x>=\-0.5, y>=\-0.5 is entirely covered. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" The returned range is exact, meaning \f(CW$n_lo\fR and \f(CW$n_hi\fR are the smallest and biggest in the rectangle. .SH "FORMULAS" .IX Header "FORMULAS" .SS "X,Y to N" .IX Subsection "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). .PP .Vb 6 \& d=2 \& \e \& d=1 \e \& \e \e \& d=0 \e \e \& \e \e \e .Ve .PP N is then given by .PP .Vb 2 \& d = X+Y \& N = d*(d+1)/2 + X + Nstart .Ve .PP 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. .PP d can be expanded out to the following quite symmetric form. This almost suggests something parabolic but is still the straight line diagonals. .PP .Vb 3 \& X^2 + 3X + 2XY + Y + Y^2 \& N = \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- + Nstart \& 2 \& \& (X+Y)^2 + 3X + Y \& = \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- + Nstart (using one square) \& 2 .Ve .SS "N to X,Y" .IX Subsection "N to X,Y" The above formula N=d*(d+1)/2 can be solved for d as .PP .Vb 2 \& d = floor( (sqrt(8*N+1) \- 1)/2 ) \& # with n_start=0 .Ve .PP 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, .PP .Vb 2 \& X = N \- d*(d+1)/2 \& Y = X \- d .Ve .PP 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. .PP .Vb 2 \& d = floor( (sqrt(8*N+5) \- 1)/2 ) \& # N>=\-0.5 .Ve .PP 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. .SS "Rectangle to N Range" .IX Subsection "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. .PP .Vb 8 \& | \e \e N max \& | \e \-\-\-\-\-\-\-\-\-\-+ \& | | \e |\e \& | |\e \e | \& | \e| \e \e | \& | +\-\-\-\-\-\-\-\-\-\- \& | N min \e \e \e \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- .Ve .SH "OEIS" .IX Header "OEIS" Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include .Sp .RS 4 (etc) .RE .PP .Vb 6 \& 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 .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::DiagonalsAlternating, Math::PlanePath::DiagonalsOctant, Math::PlanePath::Corner, Math::PlanePath::Rows, Math::PlanePath::Columns .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .PP This file is part of Math-PlanePath. .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .