/ 
Math-PlanePath-129
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::SquaRecurve

NAME

Math::PlanePath::SquaRecurve -- spiralling self-similar blocks

SYNOPSIS

use Math::PlanePath::SquaRecurve;
my $path = Math::PlanePath::SquaRecurve->new (k => 5);
my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

This path is the SquaRecurve of

    Douglas M. McKenna, 1978, as described in "SquaRecurves, E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid", in "The Lighter Side of Mathematics: Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and its History", Mathematical Association of America, 1994, pages 49-73, ISBN 0-88385-516-X.

Peano curve with segments going across unit squares.
Points N are opposite corners of these squares, so all are even points (X+Y
even).
  9 |      61          63          65          79          81
  8 | 60       58,62       64,68       66,78       76,80
  7 |    55,59       57,69       67,71       73,77       75,87
  6 | 54       52,56       38,70       36,72       34,74
  5 |    49,53       39,51       37,41       31,35       33,129
  4 | 48       46,50       40,44       30,42       28,32
  3 |     7,47        9,45       11,43       25,29       27,135
  2 |  6        4,8        10,14       12,24       22,26
  1 |     1,5         3,15       13,17       19,23       21,141
Y=0 |  0         2           16          18          20
    +----------------------------------------------------------
   X=0 1    2    3     4     5     6     7     8     9     10

Segments between the initial points can be illustrated,

  |         
  +---- 7,47 ---+---- 9,45 --
  |    ^ | \    |   ^  | \   
  |  /   |  \   |  /   |  v   
  | /    |   v  | /    |  ...
  6 -----+---- 4,8 ----+--
  | ^    |   /  | ^    |
  |   \  |  /   |   \  |
  |    \ | v    |    \ |
  +-----1,5 ----+---- 3,15    
  |   ^  | \    |   ^  |
  |  /   |  \   |  /   |      
  | /    |   v  | /    |      
N=0------+------2------+--

Segment N=0 to N=1 goes from the origin X=0,Y=0 up to X=1,Y=1, then N=2 is down again to X=2,Y=0, and so on. This can be compared to the PeanoCurve which goes between the middle of each square, so the midpoints of these segments.

Peano's conception of a space-filling curve is ternary digits of a fractional f which fills a unit square going from f=0 at X=0,Y=0 up to f=1 at X=1,Y=1. The integer form here does this with digits above the ternary point.

Even Radix

  , -----+--- 14, ---+----- 12, -
  | ^    |   /  | ^    |   /  |
  |   \  |  /   |   \  |  /   |
  |    \ | v    |    \ | v    |
  +---- 9,15 ---+--- 11,13 ---+--
  | ^    |   /  | ^    |   /  |
  |   \  |  /   |   \  |  /   |
  |    \ | v    |    \ | v    |
  +-----1,7 ----+---- 3,5 ----+-- 
  |    ^ | \    |   ^  | \    |              radix => 4
  |  /   |  \   |  /   |  \   |
  | /    |   v  | /    |   v  |
  8 -----+---- 6,10 ---+---- 4, -
  |   ^  | \    |   ^  | \    |
  |  /   |  \   |  /   |  \   |
  | /    |   v  | /    |   v  |
N=0------+------2------+------+---

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

$path = Math::PlanePath::SquaRecurve->new ()
$path = Math::PlanePath::SquaRecurve->new (radix => $r)

Create and return a new path object.

The optional radix parameter gives the base for digit splitting. The default is ternary, radix => 3.

($x,$y) = $path->n_to_xy ($n)

Return the X,Y coordinates of point number $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.

Fractional positions give an X,Y position along a straight line between the integer positions.

FORMULAS

N to Turn

The curve turns left or right 90 degrees at each point N >= 1. The turn is 90 degrees

turn(N) = 90 degrees * (-1)^(N + number of low ternary 0s of N)
        = -1,1,1,1,-1,-1,-1,1,-1,1,-1,-1,-1,1,1,1,-1,1

The power of -1 means left or right flip for each low ternary 0 of N, and flip again if N is odd. Odd N is an odd number of ternary 1 digits.

This formula follows from the turns in a new low base-9 digit. The start and end of the base figure are in the same directions so the turns at 9*N are unchanged. Then 9*N+r goes as r in the base figure, but flipped L<->R when N odd since blocks are mirrored alternately.

turn(9N)   = turn(N)
turn(9N+r) = turn(r)*(-1)^N         for  1 <= r <= 8

Just in terms of base 3, a single new low ternary digit is a transpose of what's above, and the base figure turns r=1,2 and L<->R when N above is odd again.

The same for any odd radix.

SEE ALSO

Math::PlanePath, Math::PlanePath::PeanoCurve

    DOI 10.1007/BF01199438 http://www.springerlink.com/content/w232301n53960133/

HOME PAGE

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 2019, 2020 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 <http://www.gnu.org/licenses/>.