File Coverage

blib/lib/Math/PlanePath/TriangleSpiral.pm

Criterion	Covered	Total	%
statement	57	91	62.6
branch	1	12	8.3
condition	0	9	0.0
subroutine	19	25	76.0
pod	6	6	100.0
total	83	143	58.0

# Copyright 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019 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 .


package Math::PlanePath::TriangleSpiral;
use 5.004;
use strict;
#use List::Util 'max';
*max = \&Math::PlanePath::_max;

use vars '$VERSION', '@ISA';
$VERSION = 128;
use Math::PlanePath;
@ISA = ('Math::PlanePath');

use Math::PlanePath::Base::Generic
  'round_nearest';
*_sqrtint = \&Math::PlanePath::_sqrtint;

# uncomment this to run the ### lines
#use Smart::Comments;


*xy_is_visited = \&Math::PlanePath::Base::Generic::xy_is_even;
use constant parameter_info_array =>
  [ Math::PlanePath::Base::Generic::parameter_info_nstart1() ];

sub x_negative_at_n {
  my ($self) = @_;
  return $self->n_start + 4;
}
sub y_negative_at_n {
  my ($self) = @_;
  return $self->n_start + 6;
}
sub _UNDOCUMENTED__dxdy_list_at_n {
  my ($self) = @_;
  return $self->n_start + 3;
}
use constant dx_minimum => -1;
use constant dx_maximum => 2;
use constant dy_minimum => -1;
use constant dy_maximum => 1;
use constant 1.02 _UNDOCUMENTED__dxdy_list => (2,0,    # E
                                               -1,1,   # NW
                                               -1,-1); # SW
use constant absdx_minimum => 1;
use constant dsumxy_minimum => -2; # SW diagonal
use constant dsumxy_maximum => 2;  # dX=+2 horiz
use constant ddiffxy_minimum => -2;  # NW diagonal
use constant ddiffxy_maximum => 2;   # dX=+2 horiz
use constant dir_maximum_dxdy => (-1,-1); # at most South-West diagonal

use constant turn_any_right => 0; # only left or straight


#------------------------------------------------------------------------------

sub new {
  my $self = shift->SUPER::new (@_);
  if (! defined $self->{'n_start'}) {
    $self->{'n_start'} = $self->default_n_start;
  }
  return $self;
}

# base at bottom right corner
#   d = [ 1,  2,  3 ]
#   n = [ 2,  11, 29 ]
#   $d = 1/2 + sqrt(2/9 * $n + -7/36)
#      = 1/2 + sqrt(8/36 * $n + -7/36)
#      = 0.5 + sqrt(8*$n + -7)/6
#      = (1 + 2*sqrt(8*$n + -7)/6) / 2
#      = (1 + sqrt(8*$n + -7)/3) / 2
#      = (3 + sqrt(8*$n - 7)) / 6
#
#   $n = (9/2*$d**2 + -9/2*$d + 2)
#      = (4.5*$d - 4.5)*$d + 2
#
# top of pyramid
#   d = [ 1,  2,  3 ]
#   n = [ 4, 16, 37 ]
#   $n = (9/2*$d**2 + -3/2*$d + 1)
# so remainder from there
#   rem = $n - (9/2*$d**2 + -3/2*$d + 1)
#       = $n - (4.5*$d*$d - 1.5*$d + 1)
#       = $n - ((4.5*$d - 1.5)*$d + 1)
#
#
sub n_to_xy {
  my ($self, $n) = @_;
  #### TriangleSpiral n_to_xy: $n

  $n = $n - $self->{'n_start'};  # starting $n==0, warn if $n==undef
  if ($n < 0) { return; }

  my $d = int ((3 + _sqrtint(8*$n+1)) / 6);
  #### $d

  $n -= (9*$d - 3)*$d/2;
  #### remainder: $n

  if ($n <= 3*$d) {
    ### sides, remainder pos/neg from top
    return (-$n,
            2*$d - abs($n));
  } else {
    ### rightwards from bottom left
    ### remainder: $n - 3*$d
    # corner is x=-3*$d
    # so -3*$d + 2*($n - 3*$d)
    #  = -3*$d + 2*$n - 6*$d
    #  = -9*$d + 2*$n
    #  = 2*$n - 9*$d
    return (2*$n - 9*$d,
            -$d);
  }
}

sub xy_to_n {
  my ($self, $x, $y) = @_;
  $x = round_nearest ($x);
  $y = round_nearest ($y);
  ### xy_to_n(): "$x,$y"

  if (($x ^ $y) & 1) {
    return undef;  # nothing on odd points
  }

  if ($y < 0 && 3*$y <= $x && $x <= -3*$y) {
    ### bottom horizontal
    # negative y, at vertical x=0
    #   [  -1, -2,   -3, -4,  -5,   -6 ]
    #   [ 8.5, 25, 50.5, 85, 128.5, 181 ]
    #   $n = (9/2*$y**2 + -3*$y + 1)
    #      = (4.5*$y*$y + -3*$y + 1)
    #      = ((4.5*$y -3)*$y + 1)
    # from which $x/2
    #
    return ((9*$y - 6)*$y/2) + $x/2 + $self->{'n_start'};

  } else {
    ### sides diagonal
    #
    # positive y, x=0 centres
    #   [ 2,  4,  6,  8 ]
    #   [ 4, 16,  37, 67 ]
    #   n = (9/8*$d**2 + -3/4*$d + 1)
    #     = (9/8*$d + -3/4)*$d + 1
    #     = (9*$d + - 6)*$d/8 + 1
    # from which -$x offset
    #
    my $d = abs($x) + $y;
    return ((9*$d - 6)*$d/8) - $x + $self->{'n_start'};
  }
}

# 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 $d = 0;
  foreach my $x ($x1, $x2) {
    foreach my $y ($y1, $y2) {
      $d = max ($d,
                1 + ($y < 0 && 3*$y <= $x && $x <= -3*$y
                     ? -$y                          # bottom horizontal
                     : int ((abs($x) + $y) / 2)));  # sides
    }
  }
  return ($self->{'n_start'},
          (9*$d - 9)*$d/2 + $self->{'n_start'});
}

1;
__END__