File Coverage

blib/lib/Math/PlanePath/HexArms.pm

Criterion	Covered	Total	%
statement	111	113	98.2
branch	20	22	90.9
condition	3	3	100.0
subroutine	23	23	100.0
pod	3	3	100.0
total	160	164	97.5

# Copyright 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 .


# math-image --path=HexArms --lines --scale=10
# math-image --path=HexArms --all --output=numbers_dash
# math-image --path=HexArms --values=Polygonal,polygonal=8

# Abundant: A005101
# octagonal numbers ...
# 26-gonal near vertical x2
# 152 near horizontal
#
# 2
# 164  +162
# 542  +378  +216
# 1136 +594  +216
#

package Math::PlanePath::HexArms;
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');
*_divrem_mutate = \&Math::PlanePath::_divrem_mutate;
*_sqrtint = \&Math::PlanePath::_sqrtint;

use Math::PlanePath::Base::Generic
  'round_nearest';

# uncomment this to run the ### lines
#use Devel::Comments '###';


use constant arms_count => 6;
*xy_is_visited = \&Math::PlanePath::Base::Generic::xy_is_even;

use constant x_negative_at_n => 4;
use constant y_negative_at_n => 6;
use constant dx_minimum => -2;
use constant dx_maximum => 2;
use constant dy_minimum => -1;
use constant dy_maximum => 1;
*_UNDOCUMENTED__dxdy_list = \&Math::PlanePath::_UNDOCUMENTED__dxdy_list_six;
use constant absdx_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_maximum_dxdy => (1,-1); # South-East
use constant turn_any_right => 0; # only left or straight


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

# [ 0, 1, 2, 3,],
# [ 0, 1, 3, 6 ],
# N = (1/2 d^2 + 1/2 d)
# d = -1/2 + sqrt(2 * $n + 1/4)
#   = (-1 + 2*sqrt(2 * $n + 1/4)) / 2
#   = (-1 + sqrt(8 * $n + 1)) / 2

sub n_to_xy {
  my ($self, $n) = @_;
  #### HexArms n_to_xy: $n

  if ($n < 2) {
    if ($n < 1) { return; }
    ### centre
    $n--;
    return ($n, -$n);  # from n=1 towards n=7 at x=1,y=-1
  }
  $n -= 2;

  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,6);
  ### $n

  my $d = int ((-1 + _sqrtint(8 * $n + 1)) / 2);
  ### d frac: ((-1 + _sqrtint(8 * $n + 1)) / 2)
  ### $d
  ### base: $d*($d+1)/2

  $n -= $d*($d+1)/2;
  ### remainder: $n
  ### assert: $n <= $d

  $rot += ($d % 6);
  my $x = $frac + 2 + $d + $n;
  my $y = $frac     - $d + $n;

  $rot %= 6;
  if ($rot >= 3) {
    $rot -= 3;
    $x = -$x;  # rotate 180
    $y = -$y;
  }
  if ($rot == 0) {
    return ($x,$y);
  } elsif ($rot == 1) {
    return (($x-3*$y)/2,   # rotate +60
            ($x+$y)/2);
  } else {
    return (($x+3*$y)/-2,  # rotate +120
            ($x-$y)/2);
  }
}

sub xy_to_n {
  my ($self, $x, $y) = @_;

  $x = round_nearest ($x);
  $y = round_nearest ($y);
  ### HexArms xy_to_n: "x=$x, y=$y"
  if (($x ^ $y) & 1) {
    return undef;  # nothing on odd points
  }
  if ($x == 0 && $y == 0) {
    return 1;
  }

  my $rot = 0;
  # eg. y=2 have (0<=>$y)-$y == -1-2 == -3
  if ($x < (0 <=> $y) - $y) {
    ### left diagonal half ...
    $rot = 3;
    $x = -$x;  # rotate 180
    $y = -$y;
  }
  if ($x < $y) {
    ### upper mid sixth, rot 2 ...
    $rot += 2;
    ($x,$y) = ((3*$y-$x)/2,              # rotate -120
               ($x+$y)/-2);
  } elsif ($y > 0) {
    ### first sixth, rot 1 ...
    $rot++;
    ($x,$y) = (($x+3*$y)/2,   # rotate -60
               ($y-$x)/2);
  } else {
    ### last sixth, rot 0 ...
  }
  ### assert: ($x+$y) % 2 == 0

  # diagonal down from N=2
  #     d=0  n=2
  #     d=6  n=128
  #     d=12  n=470
  # N = (3 d^2 + 3 d + 2)
  #   = ((3*$d + 3)*$d + 2)
  # xoffset = 3*($x+$y-2)
  # N + xoffset = ((3*$d + 3)*$d + 2) + 3*($x+$y-2)
  #             = (3*$d + 3)*$d + 2 + 3*($x+$y) - 6
  #             = (3*$d + 3)*$d + 3*($x+$y) - 4
  #
  my $d = ($x-$y-2)/2;
  ### xy: "$x,$y"
  ### $rot
  ### x offset: $x+$y-2
  ### x offset sixes: 3*($x+$y-2)
  ### quadratic: "d=$d  q=".((3*$d + 3)*$d + 2)
  ### d mod: $d % 6
  ### rot d mod: (($rot-$d) % 6)
  return ((3*$d + 3)*$d) + 3*($x+$y) - 4 + (($rot-$d) % 6);
}

# not exact
sub rect_to_n_range {
  my ($self, $x1,$y1, $x2,$y2) = @_;

  # d    = [ 1, 2,   3,  4,  5,   6,   7,   8,   9 ],
  # Nmax = [ 7, 19, 37, 61, 91, 127, 169, 217, 271 ]
  #   being the N=7 arm one spot before the corner of each run
  # N = (3 d^2 + 3 d + 1)
  #   = ((3*$d + 3)*$d + 1)
  #
  my $d = _rect_to_hex_radius ($x1,$y1, $x2,$y2);
  return (1,
          ((3*$d + 3)*$d + 1));
}

# hexagonal distance
sub _rect_to_hex_radius {
  my ($x1,$y1, $x2,$y2) = @_;

  $x1 = abs (round_nearest ($x1));
  $y1 = abs (round_nearest ($y1));
  $x2 = abs (round_nearest ($x2));
  $y2 = abs (round_nearest ($y2));

  # radial symmetric in +/-y
  my $y = max (abs($y1), abs($y2));

  # radial symmetric in +/-x
  my $x = max (abs($x1), abs($x2));

  return ($y >= $x
          ? $y                      # middle
          : int(($x + $y + 1)/2));  # end, round up
}

1;
__END__