1Math::PlanePath::BetaOmUesgear(3C)ontributed Perl DocumeMnattaht:i:oPnlanePath::BetaOmega(3)
2
6 Math::PlanePath::BetaOmega -- 2x2 half-plane traversal
7
9 use Math::PlanePath::BetaOmega;
10 my $path = Math::PlanePath::BetaOmega->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is an integer version of the Beta-Omega curve
15 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 The curve form here makes a 2x2 self-similar traversal of the half
21 plane X>=0.
22 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 X=0 1 2 3 4 5 6 7
42 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 The curve is named for the two base shapes
50 Beta Omega
52 *---* *---*
54 | | | |
55 --* * --* *--
56 |
57 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 Beta = 3*Beta+Omega Omega = 4*Beta
63 *---*---*---* *---*---*---*
65 | | | |
66 *---* *---* *---* *---*
67 | | | |
68 --* * *---* --* * * *--
69 | | | | | | |
70 *---* *---* *---* *---*
71 |
72 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 Level Ranges
80 Reckoning the initial N=0 to N=3 as level 1, a replication level
81 extends to
82 Nlevel = 4^level - 1
84 Xmin = 0
85 Xmax = 2^level - 1
86 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 height = Ymax - Ymin = 2^level - 1
93 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 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 The power of 4 divided by 3 formulas above for Ymin/Ymax have the
110 effect of producing alternating bit patterns like this.
111 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 Closed Curve
118 Wierum's idea for the curve is a closed square made from four betas,
119 *---* *---*
121 | | | |
122 * *-- --* *
123 | |
124 | |
126 * *-- --* *
127 | | | |
128 *---* *---*
129 And at the next expansion level
131 *---*---*---* *---*---*---*
133 | | | |
134 *---* *---* *---* *---*
135 | | | |
136 *---* * *-- --* * *---*
137 | | | | | |
138 *---* *---* *---* *---*
139 | |
140 | |
142 *---* *---* *---* *---*
143 | | | | | |
144 *---* * *-- --* * *---*
145 | | | |
146 *---* *---* *---* *---*
147 | | | |
148 *---*---*---* *---*---*---*
149 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 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 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
165 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
166 classes.
167 "$path = Math::PlanePath::BetaOmega->new ()"
169 Create and return a new path object.
170 "($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 "($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 Level Methods
180 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
181 Return "(0, 4**$level - 1)".
182
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 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 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 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 digit = N base 4 digits from high to low
210 xbit = digit_to_x[state,digit]
212 ybit = digit_to_y[state,digit]
213 state = next_state[state,digit]
214 X += 2^level * xbit
216 Y += 2^level * (ybit - !(level&1))
217 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 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 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 | 0 12--
235 5---4 | |
236 | | |
237 6---7-- ... 4-----8
238 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 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
250 Math::PlanePath, Math::PlanePath::HilbertCurve,
251 Math::PlanePath::PeanoCurve
252 <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.3487>
254 (cached copy)
255 Jens-Michael Wierum, "Logarithmic Path-Length in Space-Filling Curves",
257 14th Canadian Conference on Computational Geometry (CCCG'02), 2002.
258 <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
264 <http://user42.tuxfamily.org/math-planepath/index.html>
265
267 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
268 This file is part of Math-PlanePath.
270 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 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 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/>.
283perl v5.32.0 2020-07-28 Math::PlanePath::BetaOmega(3)