1Math::PlanePath::BetaOmUesgear(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::BetaOmega(3)
2
3
4

NAME

6       Math::PlanePath::BetaOmega -- 2x2 half-plane traversal
7

SYNOPSIS

9        use Math::PlanePath::BetaOmega;
10        my $path = Math::PlanePath::BetaOmega->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This is an integer version of the Beta-Omega curve
15
16           Jens-Michael Wierum, "Definition of a New Circular Space-Filling
17           Curve: Beta-Omega-Indexing", Technical Report TR-001-02, Paderborn
18           Center for Parallel Computing, March 2002.
19
20       The curve form here makes a 2x2 self-similar traversal of the half
21       plane X>=0.
22
23             5   25--26  29--30  33--34  37--38
24                  |   |   |   |   |   |   |   |
25             4   24  27--28  31--32  35--36  39
26                  |                           |
27             3   23  20--19--18  45--44--43  40
28                  |   |       |   |       |   |
29             2   22--21  16--17  46--47  42--41
30                          |           |
31             1    1-- 2  15--14  49--48  53--54
32                  |   |       |   |       |   |
33           Y=0->  0   3  12--13  50--51--52  55
34                      |   |                   |
35            -1    5-- 4  11--10  61--60--59  56
36                  |           |   |       |   |
37            -2    6-- 7-- 8-- 9  62--63  58--57
38                                      |
39            -3                       ...
40
41                X=0   1   2   3   4   5   6   7
42
43       Each level extends square parts 2^level x 2^level alternately up or
44       down.  The initial N=0 to N=3 extends upwards from Y=0 and exits the
45       block downwards at N=3.  N=4 extends downwards and goes around back
46       upwards to exit N=15.  N=16 then extends upwards through to N=63 which
47       exits downwards, etc.
48
49       The curve is named for the two base shapes
50
51                Beta                     Omega
52
53                  *---*                  *---*
54                  |   |                  |   |
55                --*   *                --*   *--
56                      |
57
58       The beta is made from three betas and an omega sub-parts.  The omega is
59       made from four betas.  In each case the sub-parts are suitably rotated,
60       transposed or reversed, so expanding to
61
62           Beta = 3*Beta+Omega      Omega = 4*Beta
63
64             *---*---*---*            *---*---*---*
65             |           |            |           |
66             *---*   *---*            *---*   *---*
67                 |   |                    |   |
68           --*   *   *---*          --*   *   *   *--
69             |   |       |            |   |   |   |
70             *---*   *---*            *---*   *---*
71                     |
72
73       The sub-parts represent successive ever-smaller substitutions.  They
74       have the effect of making the start a beta going alternately up or
75       down.  For this integer version the start direction is kept fixed as a
76       beta going upwards and the higher levels then alternate up and down
77       from there.
78
79   Level Ranges
80       Reckoning the initial N=0 to N=3 as level 1, a replication level
81       extends to
82
83           Nlevel = 4^level - 1
84           Xmin = 0
85           Xmax = 2^level - 1
86
87           Ymin = - (4^floor(level/2) - 1) * 2 / 3
88                = binary 1010...10
89           Ymax = (4^ceil(level/2) - 1) / 3
90                = binary 10101...01
91
92           height = Ymax - Ymin = 2^level - 1
93
94       The Y range increases alternately above and below by a power of 2, so
95       the result for Ymin and Ymax is a 1 bit going alternately to Ymax and
96       Ymin, starting with Ymax for level 1.
97
98           level     Ymin    binary       Ymax   binary
99           -----     --------------       -------------
100             0         0                    0
101             1         0          0         1 =       1
102             2        -2 =      -10         1 =      01
103             3        -2 =     -010         5 =     101
104             4       -10 =    -1010         5 =    0101
105             5       -10 =   -01010        21 =   10101
106             6       -42 =  -101010        21 =  010101
107             7       -42 = -0101010        85 = 1010101
108
109       The power of 4 divided by 3 formulas above for Ymin/Ymax have the
110       effect of producing alternating bit patterns like this.
111
112       For odd levels -Ymin/height approaches 1/3 and Ymax/height approaches
113       2/3, ie. the start point is about 1/3 up the total extent.  For even
114       levels it's the other way around, with -Ymin/height approaching 2/3 and
115       Ymax/height approaching 1/3.
116
117   Closed Curve
118       Wierum's idea for the curve is a closed square made from four betas,
119
120           *---*      *---*
121           |   |      |   |
122           *   *--  --*   *
123           |              |
124
125           |              |
126           *   *--  --*   *
127           |   |      |   |
128           *---*      *---*
129
130       And at the next expansion level
131
132           *---*---*---*       *---*---*---*
133           |           |       |           |
134           *---*   *---*       *---*   *---*
135               |   |               |   |
136           *---*   *   *--   --*   *   *---*
137           |       |   |       |   |       |
138           *---*   *---*       *---*   *---*
139               |                       |
140
141               |                       |
142           *---*   *---*       *---*   *---*
143           |       |   |       |   |       |
144           *---*   *   *--   --*   *   *---*
145               |   |               |   |
146           *---*   *---*       *---*   *---*
147           |           |       |           |
148           *---*---*---*       *---*---*---*
149
150       The code here could be used for that by choosing a level and applying
151       four copies of the path suitably mirrored and offset in X and Y.
152
153       For an odd level, the path N=0 to N=4^level-1 here is the top-right
154       quarter, entering on the left and exiting downwards.  For an even level
155       it's the bottom-right shape instead, exiting upwards.  The difference
156       arises because when taking successively greater detail sub-parts the
157       initial direction alternates up or down, but in the code here it's kept
158       fixed (as noted above).
159
160       The start point here is also fixed at Y=0, so an offset Ymin must be
161       applied if say the centre of the sections is to be Y=0 instead of the
162       side entry point.
163

FUNCTIONS

165       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
166       classes.
167
168       "$path = Math::PlanePath::BetaOmega->new ()"
169           Create and return a new path object.
170
171       "($x,$y) = $path->n_to_xy ($n)"
172           Return the X,Y coordinates of point number $n on the path.  Points
173           begin at 0 and if "$n < 0" then the return is an empty list.
174
175       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
176           The returned range is exact, meaning $n_lo and $n_hi are the
177           smallest and biggest in the rectangle.
178
179   Level Methods
180       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
181           Return "(0, 4**$level - 1)".
182

FORMULAS

184   N to X,Y
185       Each 2 bits of N become a bit each for X and Y in a "U" arrangement,
186       but which way around is determined by sub-part orientation and
187       beta/omega type per above,
188
189           beta rotation     4 of
190                transpose    2 of
191                reverse      2 of
192           omega rotation    4 of
193                 transpose   2 of
194                           ----
195           total states     24   = 4*2*2 + 4*2
196
197       The omega pattern is symmetric so its reverse is the same, hence only
198       rotate and transpose forms for it.  Omitting omega reverse reduces the
199       states from 32 to 24, saving a little space in a table driven approach.
200       But if using separate variables for rotate, transpose and reverse then
201       the reverse can be kept for both beta and omega without worrying that
202       it makes no difference in the omega.
203
204       Adding bits to Y produces a positive value measured up from
205       Ymin(level), where level is the number of base 4 digits in N.  That
206       Ymin can be incorporated by adding -(2^level) for each even level.  A
207       table driven calculation can work that in as for example
208
209           digit = N base 4 digits from high to low
210
211           xbit = digit_to_x[state,digit]
212           ybit = digit_to_y[state,digit]
213           state = next_state[state,digit]
214
215           X += 2^level * xbit
216           Y += 2^level * (ybit - !(level&1))
217
218       The (ybit-!(level&1)) means either 0,1 or -1,0.  Another possibility
219       there would be to have -!(level&1) in the digit_to_y[] table, doubling
220       the states so as to track the odd/even level within the state and
221       having the digit_to_y[] as -1,0 in the even and 0,1 in the odd.
222
223   N to X,Y Fraction
224       If N includes a fractional part, it can be put on a line towards the
225       next integer point by taking the direction as at the least significant
226       non-3 digit.
227
228       If the least significant base 4 digit is 3 then the direction along the
229       curve is determined by the curve part above.  For example at N=7 (13
230       base 4) it's rightwards as per the inverted beta which is the N=4
231       towards N=8 part of the surrounding pattern.  Or likewise N=11 (23 base
232       4) in the N=8 to N=12 direction.
233
234               |                 0    12--
235           5---4                 |     |
236           |                     |     |
237           6---7-- ...           4-----8
238
239       If all digits are 3 base 4, which is N=3, N=15, N=63, etc, then the
240       direction is down for an odd number of digits, up for an even number.
241       So N=3 downwards, N=15 upwards, N=63 downwards, etc.
242
243       This curve direction calculation might be of interest in its own right,
244       not merely to apply a fractional N as done in the code here.  There's
245       nothing offered for that in the "PlanePath" modules as such.  For it
246       the X,Y values can be ignored just follow the state or orientations
247       changes using the base 4 digits of N.
248

SEE ALSO

250       Math::PlanePath, Math::PlanePath::HilbertCurve,
251       Math::PlanePath::PeanoCurve
252
253           <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.3487>
254           (cached copy)
255
256       Jens-Michael Wierum, "Logarithmic Path-Length in Space-Filling Curves",
257       14th Canadian Conference on Computational Geometry (CCCG'02), 2002.
258
259           <http://www.cccg.ca/proceedings/2002/>
260           <http://www.cccg.ca/proceedings/2002/27.ps> (shorter),
261           <http://www.cccg.ca/proceedings/2002/27l.ps> (longer)
262

HOME PAGE

264       <http://user42.tuxfamily.org/math-planepath/index.html>
265

LICENSE

267       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde
268
269       This file is part of Math-PlanePath.
270
271       Math-PlanePath is free software; you can redistribute it and/or modify
272       it under the terms of the GNU General Public License as published by
273       the Free Software Foundation; either version 3, or (at your option) any
274       later version.
275
276       Math-PlanePath is distributed in the hope that it will be useful, but
277       WITHOUT ANY WARRANTY; without even the implied warranty of
278       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
279       General Public License for more details.
280
281       You should have received a copy of the GNU General Public License along
282       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
283
284
285
286perl v5.28.0                      2017-12-03     Math::PlanePath::BetaOmega(3)
Impressum