Math::PlanePath::HypotOctant -- octant of points in order of hypotenuse distance
use Math::PlanePath::HypotOctant; my $path = Math::PlanePath::HypotOctant->new; my ($x, $y) = $path->n_to_xy (123);
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).
In general the X,Y points are the sums of two squares X^2+Y^2 taken in increasing order of that hypotenuse, but only the "primitive" X,Y combinations, primitive in the sense of excluding mere negative X or Y or swapped Y,X.
Points with the same distance from the origin are taken in anti-clockwise order from the X axis, which means by increasing Y. Points the same distance arise 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 it at the same distance. For example 5^2 == 4^2 + 3^2 has N=14 at X=5,Y=0 and N=15 at X=4,Y=3, both 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.
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::HypotOctant->new ()
Create and return a new hypot octant path object.
($x,$y) = $path->n_to_xy ($n)
Return the X,Y coordinates of point number
$non the path.
$n < 1the 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
$nis not an integer. Successive points are a fair way apart, so it may not make much sense to say give an X,Y position in between the integer
$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,$ywithin that square returns N.
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.
n_to_xy an array is built and re-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.
Copyright 2011 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/>.