view release on metacpan or  search on metacpan

lib/Math/PlanePath/AztecDiamondRings.pm  view on Meta::CPAN

    49 31 17  7  1  0  4 12 24 40
    50 32 18  8  2  3 11 23 39 59
       51 33 19  9 10 22 38 58
          52 34 20 21 37 57
             53 35 36 56
                54 55

=head1 FUNCTIONS

See L<Math::PlanePath/FUNCTIONS> for behaviour common to all path classes.

=over 4

=item C<$path = Math::PlanePath::AztecDiamondRings-E<gt>new ()>

=item C<$path = Math::PlanePath::AztecDiamondRings-E<gt>new (n_start =E<gt> $n)>

Create and return a new Aztec diamond spiral 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 < 1> the return is an empty list, it being considered the path
starts at 1.

=item C<$n = $path-E<gt>xy_to_n ($x,$y)>

Return the point number for coordinates C<$x,$y>.  C<$x> and C<$y> are
each rounded to the nearest integer, which has the effect of treating each
point in the path as a square of side 1, so the entire plane is covered.

=item C<($n_lo, $n_hi) = $path-E<gt>rect_to_n_range ($x1,$y1, $x2,$y2)>

The returned range is exact, meaning C<$n_lo> and C<$n_hi> are the smallest
and biggest in the rectangle.

=back

=head1 FORMULAS

=head2 X,Y to N

The path makes lines in each quadrant.  The quadrant is determined by the
signs of X and Y, then the line in that quadrant is either d=X+Y or d=X-Y.
A quadratic in d gives a starting N for the line and Y (or X if desired) is
an offset from there,

    Y>=0 X>=0     d=X+Y  N=(2d+2)*d+1 + Y
    Y>=0 X<0      d=Y-X  N=2d^2       - Y
    Y<0  X>=0     d=X-Y  N=(2d+2)*d+1 + Y
    Y<0  X<0      d=X+Y  N=(2d+4)*d+2 - Y

For example

    Y=2 X=3       d=2+3=5      N=(2*5+2)*5+1  + 2  = 63
    Y=2 X=-1      d=2-(-1)=3   N=2*3*3        - 2  = 16
    Y=-1 X=4      d=4-(-1)=5   N=(2*5+2)*5+1  + -1 = 60
    Y=-2 X=-3     d=-3+(-2)=-5 N=(2*-5+4)*-5+2 - (-2) = 34

The two XE<gt>=0 cases are the same N formula and can be combined with an
abs,

    X>=0          d=X+abs(Y)   N=(2d+2)*d+1 + Y

This works because at Y=0 the last line of one ring joins up to the start of
the next.  For example N=11 to N=15,

    15             2
      \
       14          1
         \
          13   <- Y=0

       12         -1
      /
    11            -2

     ^
    X=0 1  2

=head2 Rectangle to N Range

Within each row N increases as X increases away from the Y axis, and within
each column similarly N increases as Y increases away from the X axis.  So
in a rectangle the maximum N is at one of the four corners of the rectangle.

              |
    x1,y2 M---|----M x2,y2
          |   |    |
       -------O---------
          |   |    |
          |   |    |
    x1,y1 M---|----M x1,y1
              |

For any two rows y1 and y2, the values in row y2 are all bigger than in y1
if y2E<gt>=-y1.  This is so even when y1 and y2 are on the same side of the
origin, ie. both positive or both negative.

For any two columns x1 and x2, the values in the part with YE<gt>=0 are all
bigger if x2E<gt>=-x1, or in the part of the columns with YE<lt>0 it's
x2E<gt>=-x1-1.  So the biggest corner is at

    max_y = (y2 >= -y1              ? y2 ? y1)
    max_x = (x2 >= -x1 - (max_y<0)  ? x2 : x1)

The difference in the X handling for Y positive or negative is due to the
quadrant ordering.  When YE<gt>=0, at X and -X the bigger N is the X
negative side, but when YE<lt>0 it's the X positive side.

A similar approach gives the minimum N in a rectangle.

    min_y = / y2 if y2 < 0, and set xbase=-1
            | y1 if y1 > 0, and set xbase=0
            \ 0 otherwise,  and set xbase=0

    min_x = / x2 if x2 < xbase
            | x1 if x1 > xbase
            \ xbase otherwise