NAME
Math::PlanePath::BetaOmega  2x2 halfplane traversal
SYNOPSIS
use Math::PlanePath::BetaOmega;
my $path = Math::PlanePath::BetaOmega>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This is an integer version of the BetaOmega curve
JensMichael Wierum, "Definition of a New Circular SpaceFilling Curve: BetaOmegaIndexing", Technical Report TR00102, Paderborn Center for Parallel Computing, March 2002.
The curve form here makes a 2x2 selfsimilar traversal of the half plane X>=0.
5 2526 2930 3334 3738
       
4 24 2728 3132 3536 39
 
3 23 201918 454443 40
     
2 2221 1617 4647 4241
 
1 1 2 1514 4948 5354
     
Y=0> 0 3 1213 505152 55
  
1 5 4 1110 616059 56
    
2 6 7 8 9 6263 5857

3 ...
X=0 1 2 3 4 5 6 7
Each level extends square parts 2^level x 2^level alternately up or down. The initial N=0 to N=3 extends upwards from Y=0 and exits the block downwards at N=3. N=4 extends downwards and goes around back upwards to exit N=15. N=16 then extends upwards through to N=63 which exits downwards, etc.
The curve is named for the two base shapes
Beta Omega
** **
   
* * * *

The beta is made from three betas and an omega subparts. The omega is made from four betas. In each case the subparts are suitably rotated, transposed or reversed, so expanding to
Beta = 3*Beta+Omega Omega = 4*Beta
**** ****
   
** ** ** **
   
* * ** * * * *
      
** ** ** **

The subparts represent successive eversmaller substitutions. They have the effect of making the start a beta going alternately up or down. For this integer version the start direction is kept fixed as a beta going upwards and the higher levels then alternate up and down from there.
Level Ranges
Reckoning the initial N=0 to N=3 as level 1, a replication level extends to
Nlevel = 4^level  1
Xmin = 0
Xmax = 2^level  1
Ymin =  (4^floor(level/2)  1) * 2 / 3
= binary 1010...10
Ymax = (4^ceil(level/2)  1) / 3
= binary 10101...01
height = Ymax  Ymin = 2^level  1
The Y range increases alternately above and below by a power of 2, so the result for Ymin and Ymax is a 1 bit going alternately to Ymax and Ymin, starting with Ymax for level 1.
level Ymin binary Ymax binary
  
0 0 0
1 0 0 1 = 1
2 2 = 10 1 = 01
3 2 = 010 5 = 101
4 10 = 1010 5 = 0101
5 10 = 01010 21 = 10101
6 42 = 101010 21 = 010101
7 42 = 0101010 85 = 1010101
The power of 4 divided by 3 formulas above for Ymin/Ymax have the effect of producing alternating bit patterns like this.
For odd levels Ymin/height approaches 1/3 and Ymax/height approaches 2/3, ie. the start point is about 1/3 up the total extent. For even levels it's the other way around, with Ymin/height approaching 2/3 and Ymax/height approaching 1/3.
Closed Curve
Wierum's idea for the curve is a closed square made from four betas,
** **
   
* * * *
 
 
* * * *
   
** **
And at the next expansion level
**** ****
   
** ** ** **
   
** * * * * **
     
** ** ** **
 
 
** ** ** **
     
** * * * * **
   
** ** ** **
   
**** ****
The code here could be used for that by choosing a level and applying four copies of the path suitably mirrored and offset in X and Y.
For an odd level, the path N=0 to N=4^level1 here is the topright quarter, entering on the left and exiting downwards. For an even level it's the bottomright shape instead, exiting upwards. The difference arises because when taking successively greater detail subparts the initial direction alternates up or down, but in the code here it's kept fixed (as noted above).
The start point here is also fixed at Y=0, so an offset Ymin must be applied if say the centre of the sections is to be Y=0 instead of the side entry point.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::BetaOmega>new ()

Create and return a new path object.
($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. ($n_lo, $n_hi) = $path>rect_to_n_range ($x1,$y1, $x2,$y2)

The returned range is exact, meaning
$n_lo
and$n_hi
are the smallest and biggest in the rectangle.
Level Methods
($n_lo, $n_hi) = $path>level_to_n_range($level)

Return
(0, 4**$level  1)
.
FORMULAS
N to X,Y
Each 2 bits of N become a bit each for X and Y in a "U" arrangement, but which way around is determined by subpart orientation and beta/omega type per above,
beta rotation 4 of
transpose 2 of
reverse 2 of
omega rotation 4 of
transpose 2 of

total states 24 = 4*2*2 + 4*2
The omega pattern is symmetric so its reverse is the same, hence only rotate and transpose forms for it. Omitting omega reverse reduces the states from 32 to 24, saving a little space in a table driven approach. But if using separate variables for rotate, transpose and reverse then the reverse can be kept for both beta and omega without worrying that it makes no difference in the omega.
Adding bits to Y produces a positive value measured up from Ymin(level), where level is the number of base 4 digits in N. That Ymin can be incorporated by adding (2^level) for each even level. A table driven calculation can work that in as for example
digit = N base 4 digits from high to low
xbit = digit_to_x[state,digit]
ybit = digit_to_y[state,digit]
state = next_state[state,digit]
X += 2^level * xbit
Y += 2^level * (ybit  !(level&1))
The (ybit!(level&1)) means either 0,1 or 1,0. Another possibility there would be to have !(level&1) in the digit_to_y[] table, doubling the states so as to track the odd/even level within the state and having the digit_to_y[] as 1,0 in the even and 0,1 in the odd.
N to X,Y Fraction
If N includes a fractional part, it can be put on a line towards the next integer point by taking the direction as at the least significant non3 digit.
If the least significant base 4 digit is 3 then the direction along the curve is determined by the curve part above. For example at N=7 (13 base 4) it's rightwards as per the inverted beta which is the N=4 towards N=8 part of the surrounding pattern. Or likewise N=11 (23 base 4) in the N=8 to N=12 direction.
 0 12
54  
  
67 ... 48
If all digits are 3 base 4, which is N=3, N=15, N=63, etc, then the direction is down for an odd number of digits, up for an even number. So N=3 downwards, N=15 upwards, N=63 downwards, etc.
This curve direction calculation might be of interest in its own right, not merely to apply a fractional N as done in the code here. There's nothing offered for that in the PlanePath
modules as such. For it the X,Y values can be ignored just follow the state or orientations changes using the base 4 digits of N.
SEE ALSO
Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoCurve
JensMichael Wierum, "Logarithmic PathLength in SpaceFilling Curves", 14th Canadian Conference on Computational Geometry (CCCG'02), 2002.
http://www.cccg.ca/proceedings/2002/ http://www.cccg.ca/proceedings/2002/27.ps (shorter), http://www.cccg.ca/proceedings/2002/27l.ps (longer)
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.