File Coverage

blib/lib/Math/PlanePath/DiamondArms.pm

Criterion	Covered	Total	%
statement	112	113	99.1
branch	15	16	93.7
condition			n/a
subroutine	27	27	100.0
pod	3	3	100.0
total	157	159	98.7

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


# 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 = 127;
use Math::PlanePath;
@ISA = ('Math::PlanePath');
*_divrem_mutate = \&Math::PlanePath::_divrem_mutate;
*_sqrtint = \&Math::PlanePath::_sqrtint;

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
use constant turn_any_right => 0; # only left or straight


#------------------------------------------------------------------------------
# 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 + _sqrtint(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__