search.cpan.org is shutting down
Kevin Ryde > Math-PlanePath > Math::PlanePath::Diagonals

Math-PlanePath-126.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

 Open 0
View/Report Bugs
Module Version: 126

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```

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 = d - X```

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 therefor 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

```    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

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
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```

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