File Coverage

blib/lib/Math/PlanePath/Staircase.pm

Criterion	Covered	Total	%
statement	68	91	74.7
branch	5	22	22.7
condition	1	12	8.3
subroutine	18	19	94.7
pod	4	4	100.0
total	96	148	64.8

# 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::Staircase;
use 5.004;
use strict;

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 Smart::Comments;


use constant class_x_negative => 0;
use constant class_y_negative => 0;
use constant n_frac_discontinuity => .5;
*xy_is_visited = \&Math::PlanePath::Base::Generic::xy_is_visited_quad1;

use constant dx_maximum => 1;
use constant dy_minimum => -1;
use constant dsumxy_minimum => -1; # straight S
use constant dsumxy_maximum => 2;  # next row
use constant ddiffxy_maximum => 1; # straight S,E
use constant dir_maximum_dxdy => (0,-1); # South

use constant parameter_info_array =>
  [
   Math::PlanePath::Base::Generic::parameter_info_nstart1(),
  ];


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

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

# start from 0.5 back
#     d = [ 0, 1,  2, 3 ]
#     n = [ 1.5, 6.5, 15.5 ]
#     n = ((2*$d - 1)*$d + 0.5)
#     d = 1/4 + sqrt(1/2 * $n + -3/16)
#
# start from integer vertical
#     d = [ 0, 1,  2,  3,  4 ]
#     n = [ 1, 2,  7, 16, 29 ]
#     n = ((2*$d - 1)*$d + 1)
#     d = 1/4 + sqrt(1/2 * $n + -7/16)
#       = [1 + sqrt(8*$n-7) ] / 4
#
sub n_to_xy {
  my ($self, $n) = @_;
  #### Staircase n_to_xy: $n

  # adjust to N=1 start
  $n = $n - $self->{'n_start'} + 1;

  my $d;
  {
    my $r = 8*$n - 3;
    if ($r < 1) {
      return;   # N < 0.5, so before start of path
    }
    $d = int( (_sqrtint($r) + 1)/4 );
  }
  ### $d
  ### base: ((2*$d - 1)*$d + 0.5)

  $n -= (2*$d - 1)*$d;
  ### fractional: $n

  my $int = int($n);
  $n -= $int;

  my $rem = _divrem_mutate ($int, 2);
  if ($rem) {
    ### down ...
    return ($int,
            -$n + 2*$d - $int);
  } else {
    ### across ...
    return ($n + $int-1,
            2*$d - $int);
  }
}

# d = [ 1  2, 3, 4 ]
# N = [ 2, 7, 16, 29 ]
# N = (2 d^2 - d + 1)
# and add 2*$d
# base = 2*d^2 - d + 1 + 2*d
#      = 2*d^2 + d + 1
#      = (2*$d + 1)*$d + 1
#
sub xy_to_n {
  my ($self, $x, $y) = @_;

  $x = round_nearest ($x);
  $y = round_nearest ($y);
  if ($x < 0 || $y < 0) {
    return undef;
  }
  my $d = int(($x + $y + 1) / 2);
  return (2*$d + 1)*$d - $y + $x + $self->{'n_start'};
}

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

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

  if ($x1 > $x2) { ($x1,$x2) = ($x2,$x1); }  # x2 > x1
  if ($y1 > $y2) { ($y1,$y2) = ($y2,$y1); }  # y2 > y1
  if ($x2 < 0 || $y2 < 0) {
    return (1, 0);   # nothing outside first quadrant
  }

  if ($x1 < 0) { $x1 *= 0; }
  if ($y1 < 0) { $y1 *= 0; }
  my $y_min = $y1;

  if ((($x1 ^ $y1) & 1) && $y1 < $y2) {  # y2==y_max
    $y1 += 1;
    ### y1 inc: $y1
  }
  if (! (($x2 ^ $y2) & 1) && $y2 > $y_min) {
    $y2 -= 1;
    ### y2 dec: $y2
  }
  return ($self->xy_to_n($x1,$y1),
          $self->xy_to_n($x2,$y2));
}

1;
__END__