1Math::PlanePath::AR2W2CUusrevre(C3o)ntributed Perl DocumMeanttha:t:iPolnanePath::AR2W2Curve(3)
2
3
4

NAME

6       Math::PlanePath::AR2W2Curve -- 2x2 self-similar curve of four patterns
7

SYNOPSIS

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

DESCRIPTION

14       This is an integer version of the AR2W2 curve per
15
16           Asano, Ranjan, Roos, Welzl and Widmayer "Space-Filling Curves and
17           Their Use in the Design of Geometric Data Structures", Theoretical
18           Computer Science, volume 181, issue 1, pages 3-15, July 1997.
19
20           And in LATIN'95 Theoretical Informatics which is at Google Books
21           <http://books.google.com.au/books?id=_aKhJUJunYwC&pg=PA36>
22
23       It traverses the first quadrant in self-similar 2x2 blocks which are a
24       mixture of "U" and "Z" shapes.  The mixture is designed to improve some
25       locality measures (how big the N range for a given region).
26
27                                                |
28             7     42--43--44  47--48--49  62--63
29                     \      |   |       |   |
30             6     40--41  45--46  51--50  61--60
31                    |               |           |
32             5     39  36--35--34  52  55--56  59
33                    |   |    /      |   |   |   |
34             4     38--37  33--32  53--54  57--58
35                                 \
36             3      6-- 7-- 8  10  31  28--27--26
37                    |       |/  |   |   |       |
38             2      5-- 4   9  11  30--29  24--25
39                        |       |           |
40             1      2-- 3  13--12  17--18  23--22
41                     \      |       |   |       |
42           Y=0 ->   0-- 1  14--15--16  19--20--21
43
44                   X=0  1   2   3   4   5   6   7
45
46   Shape Parts
47       There's four base patterns A to D.  A2 is a mirror image of A1, B2 a
48       mirror of B1, etc.  The start is A1, and above that D2, then A1 again,
49       alternately.
50
51                              ^---->                                ^
52                2---3      C1 |  B2            1   3       C2    D1 |
53           A1     \           |            A2  | \ |      ---->     |
54                0---1          ^               0   2      ^    ---->
55                           D2  | B1                       |B1    B2
56                          ---->|                          |
57
58
59                1---2      C2    B1             1---2      B2    C1
60           B1   |   |     ---->---->        B2  |   |     ---->---->
61                0   3     ^        |            0   3     ^        |
62                          |D1    B2|                      |B1    D2|
63                          |        v                      |        v
64
65                             ^  \                            ^ |
66                1---2      B1|   \A1            1---2     A2/  | B2
67           C1   |   |        |    v         C2  |   |      /   v
68                0   3       ^      |            0   3     ^      \
69                           /A2   B2|                      |B1     \A1
70                          /        v                      |        v
71
72                             ^ |                              ^ \
73               1---2      A2/  | C2              1---2     C1|  \A1
74           D1  |   |       /   v            D2   |   |       |   v
75               0   3      ^     \                0   3      ^      |
76                          |D1    \A2                       /A1   D2|
77                          |       v                       /        v
78
79       For parts which fill on the right such as the B1 and B2 sub-parts of
80       A1, the numbering must be reversed.  This doesn't affect the shape of
81       the curve as such, but it matters for enumerating it as done here.
82
83   Start Shape
84       The default starting shape is the A1 "Z" part, and above it D2.  Notice
85       the starting sub-part of D2 is A1 and in turn the starting sub-part of
86       A1 is D2, so those two alternate at successive higher levels.  Their
87       sub-parts reach all other parts (in all directions, and forward or
88       reverse).
89
90       The "start_shape => $str" option can select a different starting shape.
91       The choices are
92
93           "A1"       \ pair
94           "D2"       /
95           "B2"       \ pair
96           "B1rev"    /
97           "D1rev"    \ pair
98           "A2rev"    /
99
100       B2 begins with a reversed B1 and in turn a B1 reverse begins with B2
101       (no reverse), so those two alternate.  Similarly D1 reverse starts with
102       A2 reverse, and A2 reverse starts with D1 reverse.
103
104       The curve is conceived by the authors as descending into ever-smaller
105       sub-parts and for that any of the patterns can be a top-level start.
106       But to expand outwards as done here the starting part must be the start
107       of the pattern above it, and that's so only for the 6 listed.  The
108       descent graph is
109
110                     D2rev ----->  D2 <--> A1
111                     B2rev ----->
112
113           C2rev --> A1rev ----->  B2 <--> B1rev  <----- C2
114                     C1rev ----->                 <----- A2 <-- C1
115
116                     B1 ----->  D1rev <--> A2rev
117                     D1 ----->
118
119       So for example B1 is not at the start of anything.  Or A1rev is at the
120       start of C2rev, but then nothing starts with C2rev.  Of the 16 total
121       only the three pairs shown "<-->" are cycles and can thus extend
122       upwards indefinitely.
123

FUNCTIONS

125       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
126       classes.
127
128       "$path = Math::PlanePath::AR2W2Curve->new ()"
129           Create and return a new path object.
130
131       "($x,$y) = $path->n_to_xy ($n)"
132           Return the X,Y coordinates of point number $n on the path.  Points
133           begin at 0 and if "$n < 0" then the return is an empty list.
134
135       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
136           The returned range is exact, meaning $n_lo and $n_hi are the
137           smallest and largest in the rectangle.
138
139   Level Methods
140       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
141           Return "(0, 4**$level - 1)".
142

SEE ALSO

144       Math::PlanePath, Math::PlanePath::HilbertCurve,
145       Math::PlanePath::PeanoCurve
146

HOME PAGE

148       <http://user42.tuxfamily.org/math-planepath/index.html>
149

LICENSE

151       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
152
153       This file is part of Math-PlanePath.
154
155       Math-PlanePath is free software; you can redistribute it and/or modify
156       it under the terms of the GNU General Public License as published by
157       the Free Software Foundation; either version 3, or (at your option) any
158       later version.
159
160       Math-PlanePath is distributed in the hope that it will be useful, but
161       WITHOUT ANY WARRANTY; without even the implied warranty of
162       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
163       General Public License for more details.
164
165       You should have received a copy of the GNU General Public License along
166       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
167
168
169
170perl v5.30.1                      2020-01-30    Math::PlanePath::AR2W2Curve(3)
Impressum