Math::PlanePath::HypotOctant(3pm)

NAME

Math::PlanePath::HypotOctant -- octant of points in order of hypotenuse distance

SYNOPSIS

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

DESCRIPTION

This path visits an octant of integer points X,Y in order of their distance from the origin 0,0. The points are a rising triangle 0<=Y<=X,

     8  |                                61
     7  |                            47  54
     6  |                        36  43  49
     5  |                    27  31  38  44
     4  |                18  23  28  34  39
     3  |            12  15  19  24  30  37
     2  |         6   9  13  17  22  29  35
     1  |     3   5   8  11  16  21  26  33
    Y=0 | 1   2   4   7  10  14  20  25  32  ...
        +---------------------------------------
         X=0  1   2   3   4   5   6   7   8

For example N=11 at X=4,Y=1 is sqrt(4*4+1*1) = sqrt(17) from the origin. The next furthest from the origin is X=3,Y=3 at sqrt(18).

This octant is "primitive" elements X^2+Y^2 in the sense that it excludes negative X or Y or swapped Y,X.

Equal Distances

Points with the same distance from the origin are taken in anti-clockwise order from the X axis, which means by increasing Y. Points with the same distance occur when there's more than one way to express a given distance as the sum of two squares.

Pythagorean triples give a point on the X axis and also above. For example 5^2 == 4^2 + 3^2 has N=14 at X=5,Y=0 simply as 5^2 = 5^2 + 0 and then N=15 at X=4,Y=3 for the triple. Both are 5 away from the origin.

Combinations like 20^2 + 15^2 == 24^2 + 7^2 occur too, and also with three or more different ways to have the same sum distance.

Even Points

Option "points => "even"" visits just the even points, meaning the sum X+Y even, so X,Y both even or both odd.

    12  |                                    66
    11  |     points => "even"            57
    10  |                              49    58
     9  |                           40    50
     8  |                        32    41    51
     7  |                     25    34    43
     6  |                  20    27    35    45
     5  |               15    21    29    37
     4  |            10    16    22    30    39
     3  |          7    11    17    24    33
     2  |       4     8    13    19    28    38
     1  |    2     5     9    14    23    31
    Y=0 | 1     3     6    12    18    26    36
        +---------------------------------------
        X=0  1  2  3  4  5  6  7  8  9 10 11 12

Even points can be mapped to all points by a 45 degree rotate and flip. N=1,3,6,12,etc on the X axis here is on the X=Y diagonal of all-points. And conversely N=1,2,4,7,10,etc on the X=Y diagonal here is on the X axis of all-points.

    all_X = (even_X + even_Y) / 2
    all_Y = (even_X - even_Y) / 2
    even_X = (all_X + all_Y)
    even_Y = (all_X - all_Y)

The sets of points with equal hypotenuse are the same in the even and all, but the flip takes them in reverse order. The first such reversal occurs at N=14 and N=15. In even-points they're at 7,1 and 5,5. In all-points they're at 5,0 and 4,3 and those two map 5,5 and 7,1, ie. the opposite way around.

Odd Points

Option "points => "odd"" visits just the odd points, meaning sum X+Y odd, so X,Y one odd the other even.

    12  |                                       66
    11  |        points => "odd"             57
    10  |                                 47    58
     9  |                              39    49
     8  |                           32    41    51
     7  |                        25    33    42
     6  |                     20    26    35    45
     5  |                  14    21    29    37
     4  |               10    16    22    30    40
     3  |             7    11    17    24    34
     2  |          4     8    13    19    28    38
     1  |       2     5     9    15    23    31
    Y=0 |    1     3     6    12    18    27    36
        +------------------------------------------
        X=0  1  2  3  4  5  6  7  8  9 10 11 12 13

The X=Y diagonal is excluded because it has X+Y even.

FUNCTIONS

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

"$path = Math::PlanePath::HypotOctant->new ()"

"$path = Math::PlanePath::HypotOctant->new (points => $str)"

Create and return a new hypot octant path object. The "points" option can be

    "all"         all integer X,Y (the default)
    "even"        only points with X+Y even
    "odd"         only points with X+Y odd

"($x,$y) = $path->n_to_xy ($n)"

Return the X,Y coordinates of point number $n on the path.

For "$n < 1" the return is an empty list, it being considered the first point at X=0,Y=0 is N=1.

Currently it's unspecified what happens if $n is not an integer. Successive points are a fair way apart, so it may not make much sense to give an X,Y position in between the integer $n.

"$n = $path->xy_to_n ($x,$y)": Return an integer point number for coordinates "$x,$y". Each integer N is considered the centre of a unit square and an "$x,$y" within that square returns N.

FORMULAS

The calculations are not very efficient currently. For each Y row a current X and the corresponding hypotenuse X^2+Y^2 are maintained. To find the next furthest a search through those hypotenuses is made seeking the smallest, including equal smallest, which then become the next N points.

For "n_to_xy()" an array is built in the object used for repeat calculations. For "xy_to_n()" an array of hypot to N gives a the first N of given X^2+Y^2 distance. A search is then made through the next few N for the case there's more than one X,Y of that hypot.

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include

<http://oeis.org/A024507> (etc)

    points="all"
      A024507   X^2+Y^2 of all points not on X axis or X=Y diagonal
      A024509   X^2+Y^2 of all points not on X axis
                  being integers occurring as sum of two non-zero squares,
                  with repetitions for multiple ways
    points="even"
      A036702   N on X=Y leading Diagonal
                  being count of points norm<=k
    points="odd"
      A057653   X^2+Y^2 values occurring
                  ie. odd numbers which are sum of two squares,
                  without repetitions

HOME PAGE

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

LICENSE

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