# Copyright 2011, 2012, 2013, 2014, 2015 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/>.
# math-image --path=DiamondArms --lines --scale=10
# math-image --path=DiamondArms --all --output=numbers_dash
# math-image --path=DiamondArms --values=Polygonal,polygonal=8
#
# RepdigitsAnyBase fall on 14 or 15 lines ...
#
package Math::PlanePath::DiamondArms;
use 5.004;
use strict;
#use List::Util 'min', 'max';
*min = \&Math::PlanePath::_min;
*max = \&Math::PlanePath::_max;
use vars '$VERSION', '@ISA';
$VERSION = 119;
use Math::PlanePath;
@ISA = ('Math::PlanePath');
*_divrem_mutate = \&Math::PlanePath::_divrem_mutate;
use Math::PlanePath::Base::Generic
'round_nearest';
use Math::PlanePath::DiamondSpiral;
# uncomment this to run the ### lines
#use Devel::Comments;
use constant arms_count => 4;
use constant xy_is_visited => 1;
use constant x_negative_at_n => 8;
use constant y_negative_at_n => 5;
use constant dx_minimum => -1;
use constant dx_maximum => 1;
use constant dy_minimum => -1;
use constant dy_maximum => 1;
use constant _UNDOCUMENTED__dxdy_list => (1,1, # NE diagonals
-1,1, # NW
-1,-1, # SW
1,-1); # SE
use constant absdx_minimum => 1;
use constant absdy_minimum => 1;
use constant dsumxy_minimum => -2; # diagonals
use constant dsumxy_maximum => 2;
use constant ddiffxy_minimum => -2;
use constant ddiffxy_maximum => 2;
use constant dir_minimum_dxdy => (1,1); # North-East
use constant dir_maximum_dxdy => (1,-1); # South-East
#------------------------------------------------------------------------------
# 28
# 172 +144
# 444 +272 +128
# 844 +400 +128
# [ 0, 1, 2, 3,],
# [ 0, 1, 3, 6 ],
# N = (1/2 d^2 + 1/2 d)
# = (1/2*$d**2 + 1/2*$d)
# = ($d+1)*$d/2
# d = -1/2 + sqrt(2 * $n + 1/4)
# = (-1 + sqrt(8*$n + 1))/2
sub n_to_xy {
my ($self, $n) = @_;
### DiamondArms n_to_xy(): $n
if ($n < 1) {
return;
}
$n -= 1;
my $frac;
{
my $int = int($n);
$frac = $n - $int;
$n = $int; # BigFloat int() gives BigInt, use that
}
# arm as initial rotation
my $rot = _divrem_mutate($n,4);
### $n
# if (($rot%4) != 3) {
# return;
# }
my $d = int ((-1 + sqrt(8*$n + 1)) / 2);
### d frac: ((-1 + sqrt(8*$n + 1)) / 2)
### $d
### base: $d*($d+1)/2
$n -= $d*($d+1)/2;
### remainder: $n
### assert: $n <= $d
my $x = ($frac + $n) - $d;
my $y = - ($frac + $n);
### unrot: "$x,$y"
$rot = ($rot + $d) % 4;
### $rot
if ($rot == 1) {
($x,$y) = (1-$y, $x); # rotate +90 and right
} elsif ($rot == 2) {
($x,$y) = (1-$x, 1-$y); # rotate 180 and up+right
} elsif ($rot == 3) {
($x,$y) = ($y, 1-$x); # rotate +90 and up
}
return ($x,$y);
}
sub xy_to_n {
my ($self, $x, $y) = @_;
$x = round_nearest ($x);
$y = round_nearest ($y);
### DiamondArms xy_to_n: "$x,$y"
my $rot = 0;
# eg. y=2 have (0<=>$y)-$y == -1-2 == -3
if ($y >= ($x > 0)) {
### above horizontal, rot -180 ...
$rot = 2;
$x = 1-$x; # rotate 180 and offset
$y = 1-$y;
}
if ($x > 0) {
### right of vertical, rot -90 ...
$rot++;
($x,$y) = ($y,1-$x); # rotate -90 and offset
}
# horizontal negative X axis
# d = -x + -y
# d=0 n=1
# d=4 n=41
# d=8 n=145
# d=12 n=313
# N = (2 d^2 + 2 d + 1)
# = (2*$d**2 + 2*$d + 1)
# = ((2*$d + 2)*$d + 1)
#
my $d = -$x - $y;
### xy: "$x,$y"
### $d
### $rot
### base: ((2*$d + 2)*$d + 1)
### offset: -4 * $y
### rot d mod: (($rot+$d+2) % 4)
return ((2*$d + 2)*$d + 1) - 4*$y + (($rot-$d) % 4);
}
# d = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
# Nmax = [ 9, 25, 49, 81, 121, 169, 225, 289, 361 ]
# being the N=5 arm one spot before the corner of each run
# N = (4 d^2 + 4 d + 1)
# = (2d+1)^2
# = ((4*$d + 4)*$d + 1)
# or for d-1
# N = (4 d^2 - 4 d + 1)
# = (2d-1)^2
# = ((4*$d - 4)*$d + 1)
#
# not exact
sub rect_to_n_range {
my ($self, $x1,$y1, $x2,$y2) = @_;
$x1 = round_nearest ($x1);
$y1 = round_nearest ($y1);
$x2 = round_nearest ($x2);
$y2 = round_nearest ($y2);
my $x = (($x1<0) == ($x2<0) ? min(abs($x1),abs($x2)) : 0);
my $y = (($y1<0) == ($y2<0) ? min(abs($y1),abs($y2)) : 0);
my $d = max(0, $x + $y - 2);
return (((2*$d + 2)*$d + 1),
max ($self->xy_to_n($x1,$y1),
$self->xy_to_n($x1,$y2),
$self->xy_to_n($x2,$y1),
$self->xy_to_n($x2,$y2)));
}
1;
__END__
# 25 4
# / \
# 29 14 21 ... 3
# / / \ \ \
# ... 18 7 10 17 32 2
# / / \ \ \ \
# 22 11 4 3 6 13 28 1
# / / / / / /
# 26 15 8 1 2 9 24 <- Y=0
# \ \ \ \ / /
# 30 19 12 5 20 ... -1
# \ \ \ / /
# ... 23 16 31 -2
# \ /
# 27 -3
# 25 4
# / \
# 29 14 21 ... 3
# / / \ \ \
# ... 18 7 10 17 32 2
# / / \ \ \ \
# 22 11 4 3 6 13 28 1
# / / / / / /
# 26 15 8 1 2 9 24 <- Y=0
# \ \ \ \ / /
# 30 19 12 5 20 ... -1
# \ \ \ / /
# ... 23 16 31 -2
# \ /
# 27 -3
=for stopwords Math-PlanePath Ryde ie
=head1 NAME
Math::PlanePath::DiamondArms -- four spiral arms
=head1 SYNOPSIS
use Math::PlanePath::DiamondArms;
my $path = Math::PlanePath::DiamondArms->new;
my ($x, $y) = $path->n_to_xy (123);
=head1 DESCRIPTION
This path follows four spiral arms, each advancing successively in a diamond
pattern,
25 ... 4
29 14 21 36 3
33 18 7 10 17 32 2
... 22 11 4 3 6 13 28 1
26 15 8 1 2 9 24 ... <- Y=0
30 19 12 5 20 35 -1
34 23 16 31 -2
... 27 -3
^
-3 -2 -1 X=0 1 2 3 4
Each arm makes a spiral widening out by 4 each time around, thus leaving
room for four such arms. Each arm loop is 64 longer than the preceding
loop. For example N=13 to N=85 below is 84-13=72 points, and the next loop
N=85 to N=221 is 221-85=136 which is an extra 64, ie. 72+64=136.
25 ...
/ \ \
29 . 21 . . . 93
/ \ \
33 . . . 17 . . . 89
/ \ \
37 . . . . . 13 . . . 85
/ / /
41 . . . 1 . 9 . . . 81
\ \ / /
45 . . . 5 . . . 77
\ /
49 . . . . . 73
\ /
53 . . . 69
\ /
57 . 65
\ /
61
Each arm is N=4*k+rem for a remainder rem=0,1,2,3, so sequences related to
multiples of 4 or with a modulo 4 pattern may fall on particular arms.
The starts of each arm N=1,2,3,4 are at X=0 or 1 and Y=0 or 1,
..
\
4 3 .. Y=1
/ /
.. 1 2 <- Y=0
\
..
^ ^
X=0 X=1
They could be centred around the origin by taking X-1/2,Y-1/2 so for example
N=1 would be at -1/2,-1/2. But the it's done as N=1 at 0,0 to stay in
integers.
=head1 FUNCTIONS
See L<Math::PlanePath/FUNCTIONS> for behaviour common to all path classes.
=over 4
=item C<$path = Math::PlanePath::DiamondArms-E<gt>new ()>
Create and return a new path object.
=item C<($x,$y) = $path-E<gt>n_to_xy ($n)>
Return the X,Y coordinates of point number C<$n> on the path. For C<$n
E<lt> 1> the return is an empty list, as the path starts at 1.
Fractional C<$n> gives a point on the line between C<$n> and C<$n+4>, that
C<$n+4> being the next point on the same spiralling arm. This is probably
of limited use, but arises fairly naturally from the calculation.
=back
=head2 Descriptive Methods
=over
=item C<$arms = $path-E<gt>arms_count()>
Return 4.
=back
=head1 SEE ALSO
L<Math::PlanePath>,
L<Math::PlanePath::SquareArms>,
L<Math::PlanePath::DiamondSpiral>
=head1 HOME PAGE
L<http://user42.tuxfamily.org/math-planepath/index.html>
=head1 LICENSE
Copyright 2011, 2012, 2013, 2014, 2015 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/>.
=cut