/ 
Math-PlanePath-76
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::DiagonalsOctant

NAME

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

SYNOPSIS

use Math::PlanePath::DiagonalsOctant;
my $path = Math::PlanePath::DiagonalsOctant->new;
my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

This path follows successive diagonals going from the Y axis down to the X=Y line to traverse an eighth of the plane.

  8 |  21 27 33 40 47 55 63 72 81
    |    \  \  \  \  \  \  \
  7 |  17 22 28 34 41 48 56 64
    |    \  \  \  \  \  \
  6 |  13 18 23 29 35 42 49
    |    \  \  \  \  \
  5 |  10 14 19 24 30 36
    |    \  \  \  \
  4 |   7 11 15 20 25
    |    \  \  \
  3 |   5  8 12 16
    |    \  \
  2 |   3  6  9
    |    \
  1 |   2  4
    |   
Y=0 |   1
    + ----------------------------
      X=0  1  2  3  4  5  6  7  8

N=1,4,9,16,etc on the X=Y leading diagonal are the perfect squares. N=2,6,12,20,etc to the left of them are the pronic numbers k*(k+1)

Direction

Option direction => 'up' reverses the order within each diagonal and counts upward from the centre to the Y axis.

  8 |  25 29 34 39 45 51 58 65 73
    |    \  \  \  \  \  \  \     
  7 |  20 24 28 33 38 44 50 57   
    |    \  \  \  \  \  \        
  6 |  16 19 23 27 32 37 43      
    |    \  \  \  \  \           
  5 |  12 15 18 22 26 31         
    |    \  \  \  \              
  4 |   9 11 14 17 21            
    |    \  \  \                 
  3 |   6  8 10 13               
    |    \  \                    
  2 |   4  5  7                  
    |    \                       
  1 |   2  3                     
    |                            
Y=0 |   1                        
    +---------------------------
      X=0  1  2  3  4  5  6  7  8

In this arrangement N=1,2,4,6,9,etc on the Y axis are the squares and pronic numbers. The squares are on even Y and pronic on odd Y.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

$path = Math::PlanePath::DiagonalsOctant->new ()

Create and return a new path object.

($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.

($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

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.

Nstart = d*d+1

where d numbers diagonal pairs, eg. d=3 for X=0,Y=5 going down. This is easily reversed as

d = floor sqrt(N-1)

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

d = floor sqrt(N-0.5)
  = int( sqrt(int(4*$n)-2)/2 )

Taking /2 out of the sqrt helps with Math::BigInt which circa Perl 5.14 doesn't inter-operate with flonums very well.

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.

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,

Nrem = N - (d*(d+1)+1)

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.

To include the preceding 0.5 in the second diagonal simply means reckoning Nrem>=-0.5 as belonging to the second. In that base

if Nrem >= -0.5
  X = Nrem            # direction="down"
  Y = 2*d - Nrem
else
  X = Nrem + d
  Y = d - Nrem - 1

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.

For "up" direction the Nrem and d are the same, but the coordinate directions reverse.

if Nrem >= -0.5
  X = d - Nrem        # direction="up"
  Y = d + Nrem
else
  X = -Nrem - 1
  Y = 2d + Nrem

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).

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 "down" and "up" arrangements. On that basis for a rectangle the lower left corner is the minimum N and the upper right is the maximum N.

If the rectangle is partly outside the covered octant then the corners must be shifted to put them in range.

    |    /
  +---- /
  | |  /        if x1 < 0 then x1 = 0
  +---/         increase x1 to within octant
x1  |/
    +      

    |  |/
    |  |          if y1 < x1 then y1 = x1
    | /|          increase y1 to bottom-left within octant  
    |/ +----y1 
    +  x1

    |    /  x2  
    | ------+ y2    if x2 > y2 then x2 = y2
    |  /    |       decrease x2 so top-right within octant
    | /     |        (the end of the y2 row)
    |/
    +

SEE ALSO

Math::PlanePath, Math::PlanePath::Diagonals, Math::PlanePath::DiagonalsAlternating

HOME PAGE

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

LICENSE

Copyright 2012 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/>.