.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" 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 turned on, 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 .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::DiagonalsOctant 3pm" .TH Math::PlanePath::DiagonalsOctant 3pm "2014-08-30" "perl v5.20.1" "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::DiagonalsOctant \-\- points in diagonal stripes for an eighth of the plane .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::DiagonalsOctant; \& my $path = Math::PlanePath::DiagonalsOctant\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This path follows successive diagonals downwards from the Y axis down to the X=Y centre line, traversing the eighth of the plane on and above X=Y. .PP .Vb 10 \& 8 | 21 27 33 40 47 55 63 72 81 \& | \e \e \e \e \e \e \e \& 7 | 17 22 28 34 41 48 56 64 \& | \e \e \e \e \e \e \& 6 | 13 18 23 29 35 42 49 \& | \e \e \e \e \e \& 5 | 10 14 19 24 30 36 \& | \e \e \e \e \& 4 | 7 11 15 20 25 \& | \e \e \e \& 3 | 5 8 12 16 \& | \e \e \& 2 | 3 6 9 \& | \e \& 1 | 2 4 \& | \& Y=0 | 1 \& + \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 .Ve .PP N=1,4,9,16,etc on the X=Y leading diagonal are the perfect squares. N=2,6,12,20,etc at the ends of the other diagonals are the pronic numbers k*(k+1). .IX Xref "Square numbers Pronic numbers" .PP Incidentally \*(L"octant\*(R" usually refers to an eighth of a 3\-dimensional coordinate space. Since \f(CW\*(C`PlanePath\*(C'\fR is only 2 dimensions there's no confusion and at the risk of abusing nomenclature half a quadrant is reckoned as an \*(L"octant\*(R". .SS "Pyramid Rows" .IX Subsection "Pyramid Rows" Taking two diagonals running from k^2+1 to (k+1)^2 is the same as a row of the step=2 \f(CW\*(C`PyramidRows\*(C'\fR (see Math::PlanePath::PyramidRows). Each endpoint is the same, but here it's two diagonals instead of one row. For example in the \f(CW\*(C`PyramidRows\*(C'\fR the Y=3 row runs from N=10 to N=16 ending at X=3,Y=3. Here that's in two diagonals N=10 to N=12 and then N=13 to N=16, and that N=16 endpoint is the same X=3,Y=3. .SS "Direction" .IX Subsection "Direction" Option \f(CW\*(C`direction => \*(Aqup\*(Aq\*(C'\fR reverses the order within each diagonal and counts upward from the centre to the Y axis. .PP .Vb 10 \& 8 | 25 29 34 39 45 51 58 65 73 \& | \e \e \e \e \e \e \e \& 7 | 20 24 28 33 38 44 50 57 \& | \e \e \e \e \e \e \& 6 | 16 19 23 27 32 37 43 \& | \e \e \e \e \e \& 5 | 12 15 18 22 26 31 \& | \e \e \e \e \& 4 | 9 11 14 17 21 direction => "up" \& | \e \e \e \& 3 | 6 8 10 13 \& | \e \e \& 2 | 4 5 7 \& | \e \& 1 | 2 3 \& | \& Y=0 | 1 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 4 5 6 7 8 .Ve .PP In this arrangement N=1,2,4,6,9,etc on the Y axis are alternately the squares and the pronic numbers. The squares are on even Y and pronic on odd Y. .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" \& \& 6 | 12 | 15 \& 5 | 9 13 | 11 14 \& 4 | 6 10 14 | 8 10 13 \& 3 | 4 7 11 15 | 5 7 9 12 \& 2 | 2 5 8 | 3 4 6 \& 1 | 1 3 | 1 2 \& Y=0 | 0 | 0 \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\- +\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& X=0 1 2 3 X=0 1 2 3 .Ve .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::DiagonalsOctant\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::DiagonalsOctant\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::DiagonalsOctant->new ()" .PD 0 .ie n .IP """$path = Math::PlanePath::DiagonalsOctant\->new (direction => $str, n_start => $n)""" 4 .el .IP "\f(CW$path = Math::PlanePath::DiagonalsOctant\->new (direction => $str, n_start => $n)\fR" 4 .IX Item "$path = Math::PlanePath::DiagonalsOctant->new (direction => $str, n_start => $n)" .PD Create and return a new path object. .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. .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 "N to X,Y" .IX Subsection "N to X,Y" To break N into X,Y it's convenient to take two diagonals at a time, since the length then changes by 1 each pair making a quadratic. Starting at each X=0,Y=odd just after perfect square N allows just a sqrt. .PP .Vb 1 \& Nstart = d*d+1 .Ve .PP where d numbers diagonal pairs, eg. d=3 for X=0,Y=5 going down. This is easily reversed as .PP .Vb 1 \& d = floor sqrt(N\-1) .Ve .PP The code reckons the start of the diagonal as 0.5 further back, so that N=9.5 is at X=\-.5,Y=5.5. To do that d is formed as .PP .Vb 2 \& d = floor sqrt(N\-0.5) \& = int( sqrt(int(4*$n)\-2)/2 ) .Ve .PP Taking /2 out of the sqrt helps with \f(CW\*(C`Math::BigInt\*(C'\fR which circa Perl 5.14 doesn't inter-operate with flonums very well. .PP In any case N\-Nstart is an offset into two diagonals, the first of length d many points and the second d+1. For example d=3 starting Y=5 for points N=10,11,12 followed by Y=6 N=13,14,15,16. .PP The formulas are simplified by calculating a remainder relative to the second diagonal, so it's negative for the first and positive for the second, .PP .Vb 1 \& Nrem = N \- (d*(d+1)+1) .Ve .PP d*(d+1)+1 is 1 past the pronic numbers when end each first diagonal, as described above. In any case for example d=3 is relative to N=13 making Nrem=\-3,\-2,\-1 or Nrem=0,1,2,3. .PP To include the preceding 0.5 in the second diagonal simply means reckoning Nrem>=\-0.5 as belonging to the second. In that base .PP .Vb 6 \& if Nrem >= \-0.5 \& X = Nrem # direction="down" \& Y = 2*d \- Nrem \& else \& X = Nrem + d \& Y = d \- Nrem \- 1 .Ve .PP For example N=15 Nrem=1 is the first case, X=1, Y=2*3\-1=5. Or N=11 Nrem=\-2 the second X=\-2+3=1, Y=3\-(\-2)\-1=4. .PP For \*(L"up\*(R" direction the Nrem and d are the same, but the coordinate directions reverse. .PP .Vb 6 \& if Nrem >= \-0.5 \& X = d \- Nrem # direction="up" \& Y = d + Nrem \& else \& X = \-Nrem \- 1 \& Y = 2d + Nrem .Ve .PP Another way is to reckon Nstart from the X=0,Y=even diagonals, which is then two diagonals of the same length and d formed by a sqrt inverting a pronic Nstart=d*(d+1). .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. This is so in both \*(L"down\*(R" and \*(L"up\*(R" arrangements. On that basis in a rectangle the lower left corner is the minimum N and the upper right is the maximum N. .PP If the rectangle is partly outside the covered octant then the corners must be shifted to put them in range, ie. trim off any rows or columns entirely outside the rectangle. For the lower left this means, .PP .Vb 6 \& | | / \& | | / \& +\-\-\-\-\-\-\-\- if x1 < 0 then x1 = 0 \& x1 | / increase x1 to within octant \& |/ \& + \& \& | |/ \& | | if y1 < x1 then y1 = x1 \& | /| increase y1 to bottom\-left within octant \& |/ +\-\-\-\-y1 \& + x1 .Ve .PP And for the top right, .PP .Vb 6 \& | / x2 \& | \-\-\-\-\-\-+ y2 if x2 > y2 then x2 = y2 \& | / | decrease x2 so top\-right within octant \& | / | (the end of the y2 row) \& |/ \& + .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 \& A002620 N at end each run X=k,Y=k and X=k,Y=k+1 \& direction=down, n_start=0 \& A055087 X coord, runs 0 to k twice \& A082375 Y\-X, runs k to 0 or 1 stepping by 2 \& A005563 N on X=Y diagonal, X*(X+2) \& \& direction=up \& A002620 N on Y axis, end of each run, quarter squares \& direction=up, n_start=0 \& A024206 N on Y axis (starting from n=1 is Y=0, so Y=n\-1) \& A014616 N in column X=1 (is Y axis N\-1, from N=3) \& A002378 N on X=Y diagonal, pronic X*(X+1) \& \& either direction, n_start=0 \& A055086 X+Y, k repeating floor(k/2)+1 times \& \& A004652 N start and end of each even\-numbered diagonal \& \& permutations \& A056536 N of PyramidRows in DiagonalsOctant order \& A091995 with DiagonalsOctant direction=up \& A091018 N\-1, ie. starting from 0 \& A090894 N\-1 and DiagonalsOctant direction=up \& \& A056537 N of DiagonalsOctant at X,Y in PyramidRows order \& inverse of A056536 .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::Diagonals, Math::PlanePath::DiagonalsAlternating, Math::PlanePath::PyramidRows .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2012, 2013, 2014 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 .