1Math::PlanePath::DragonUMsiedrpoCionntt(r3i)buted Perl DMoactuhm:e:nPtlaatnieoPnath::DragonMidpoint(3)
2
6 Math::PlanePath::DragonMidpoint -- dragon curve midpoints
7
9 use Math::PlanePath::DragonMidpoint;
10 my $path = Math::PlanePath::DragonMidpoint->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is the midpoint of each segment of the dragon curve of Heighway,
15 Harter, et al, per Math::PlanePath::DragonCurve.
16 17--16 9---8 5
18 | | | |
19 18 15 10 7 4
20 | | | |
21 19 14--13--12--11 6---5---4 3
22 | |
23 20--21--22 3 2
24 | |
25 33--32 25--24--23 2 1
26 | | | |
27 34 31 26 0---1 <- Y=0
28 | | |
29 35 30--29--28--27 -1
30 |
31 36--37--38 43--44--45--46 -2
32 | | |
33 39 42 49--48--47 -3
34 | | |
35 40--41 50 -4
36 |
37 51 -5
38 |
39 52--53--54 -6
40 |
41 ..--64 57--56--55 -7
42 | |
43 63 58 -8
44 | |
45 62--61--60--59 -9
46 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
49 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1
50 The dragon curve begins as follows. The midpoints of each segment are
52 numbered starting from 0,
53 +--8--+ +--4--+
55 | | | |
56 9 7 5 3
57 | | | | |
58 +-10--+--6--+ +--2--+ rotate 45 degrees |
59 | | v
60 11 1
61 | |
62 +-12--+ *--0--+ * = Origin
63 |
64 ...
65 These midpoints are on fractions X=0.5,Y=0, X=1,Y=0.5, etc. For this
67 "DragonMidpoint" path they're turned clockwise 45 degrees and shrunk by
68 sqrt(2) to be integer X,Y values a unit apart and initial direction to
69 the right.
70 The midpoints are distinct X,Y positions because the dragon curve
72 traverses each edge only once.
73 The dragon curve is self-similar in 2^level sections due to its
75 unfolding. This can be seen in the midpoints too as for example above
76 N=0 to N=16 is the same shape as N=16 to N=32, with the latter rotated
77 90 degrees and in reverse.
78 For reference, Knuth in "Diamonds and Dragons" has a different
80 numbering for segment midpoints where the dragon orientation is
81 unchanged and instead multiply by 2 to have midpoints as integers. For
82 example the first dragon midpoint at X=1/2,Y=0 is doubled out to
83 X=1,Y=0. That can be obtained from the path here by
84 KnuthX = X - Y + 1
86 KnuthY = X + Y
87 Arms
89 Like the "DragonCurve" the midpoints fill a quarter of the plane and
90 four copies mesh together perfectly when rotated by 90, 180 and 270
91 degrees. The "arms" parameter can choose 1 to 4 curve arms,
92 successively advancing.
93 For example "arms => 4" begins as follows, with N=0,4,8,12,etc being
95 the first arm (the same as the plain curve above), N=1,5,9,13 the
96 second, N=2,6,10,14 the third and N=3,7,11,15 the fourth.
97 arms => 4
99 ...-107-103 83--79--75--71 6
101 | | |
102 68--64 36--32 99 87 59--63--67 5
103 | | | | | | |
104 72 60 40 28 95--91 55 4
105 | | | | |
106 76 56--52--48--44 24--20--16 51 3
107 | | |
108 80--84--88 17--13---9---5 12 47--43--39 ... 2
109 | | | | | |
110 100--96--92 21 6---2 1 8 27--31--35 106 1
111 | | | | | |
112 104 33--29--25 10 3 0---4 23 94--98-102 <- Y=0
113 | | | | | |
114 ... 37--41--45 14 7--11--15--19 90--86--82 -1
115 | | |
116 49 18--22--26 46--50--54--58 78 -2
117 | | | | |
118 53 89--93 30 42 62 74 -3
119 | | | | | | |
120 65--61--57 85 97 34--38 66--70 -4
121 | | |
122 69--73--77--81 101-105-... -5
123 ^
125 -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5
126 With four arms like this every X,Y point is visited exactly once,
128 because four arms of the "DragonCurve" traverse every edge exactly
129 once.
130 Tiling
132 Taking pairs of adjacent points N=2k and N=2k+1 gives little rectangles
133 with the following tiling of the plane repeating in 4x4 blocks.
134 +---+---+---+-+-+---+-+-+---+
136 | | | | | | | | | | |
137 +---+ | +---+ | +---+ | +---+
138 | | | |9 8| | | | | | |
139 +-+-+---+-+-+-+-+-+-+-+-+-+-+
140 | | | | |7| | | | | | |
141 | | +---+ | +---+ | +---+ | |
142 | | | | |6|5 4| | | | | |
143 +---+-+-+-+-+-+-+-+-+-+-+-+-+
144 | | | | | |3| | | | |
145 +---+ | +---+ | +---+ | +---+
146 | | | | | |2| | | | |
147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
148 | | | | | |0 1| | | | | | <- Y=0
149 | | +---+ | +---+ | +---+ | |
150 | | | | | | | | | | | |
151 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
152 | | | | | | | | | | |
153 +---+ | +---+ | +---+ | +---+
154 | | | | | | | | | | |
155 +---+-+-+---+-+-+---+-+-+---+
156 ^
157 X=0
158 The pairs follow this pattern both for the main curve N=0 etc shown,
160 and also for the rotated copies per "Arms" above. This tiling is in
161 the tilingsearch database as
162 <http://tilingsearch.org/HTML/data24/K02A.html>
164 Taking pairs N=2k+1 and N=2k+2, being each odd N and its successor,
166 gives a regular pattern too, but this time repeating in blocks of
167 16x16.
168 |||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--|||
170 |||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--|||
171 -||------||------||------||------||------||------||------||-----
172 -||------||------||------||------||------||------||------||-----
173 |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
174 |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
175 -----||------||------||------||------||------||------||------||-
176 -----||------||------||------||------||------||------||------||-
177 -||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||-
178 -||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||-
179 -||------||------||------||------||------||------||------||-----
180 -||------||------||------||------||------||------||------||-----
181 |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
182 |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
183 -----||------||------||------||------||------||------||------||-
184 -----||------||------||------||------||------||------||------||-
185 |||--||||||--||--||--||||||--|| ||--||||||--||--||--||||||--|||
186 |||--||||||--||--||--||||||--|| ||--||||||--||--||--||||||--|||
187 -||------||------||------||------||------||------||------||-----
188 -||------||------||------||------||------||------||------||-----
189 |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
190 |||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
191 -----||------||------||------||------||------||------||------||-
192 -----||------||------||------||------||------||------||------||-
193 -||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||-
194 -||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||-
195 -||------||------||------||------||------||------||------||-----
196 -||------||------||------||------||------||------||------||-----
197 |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
198 |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
199 -----||------||------||------||------||------||------||------||-
200 -----||------||------||------||------||------||------||------||-
201 Curve from Midpoints
203 Since the dragon curve always turns left or right, never straight ahead
204 or reverse, its segments are alternately horizontal and vertical.
205 Rotated -45 degrees for the midpoints here this means alternately
206 "opposite diagonal" and "leading diagonal". They fall on X,Y
207 alternately even or odd. So the original dragon curve can be recovered
208 from the midpoints by choosing leading diagonal or opposite diagonal
209 segment according to X,Y even or odd, which is the same as N even or
210 odd.
211 DragonMidpoint dragon segment
213 -------------- -----------------
214 "even" N==0 mod 2 opposite diagonal
215 which is X+Y==0 mod 2 too
216 "odd" N==1 mod 2 leading diagonal
218 which is X+Y==1 mod 2 too
219 /
221 3 0 at X=0,Y=0 "even", opposite diagonal
222 / 1 at X=1,Y=0 "odd", leading diagonal
223 \ etc
224 2
225 \
226 \ /
227 0 1
228 \ /
229
231 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
232 classes.
233 "$path = Math::PlanePath::DragonMidpoint->new ()"
235 Create and return a new path object.
236 "($x,$y) = $path->n_to_xy ($n)"
238 Return the X,Y coordinates of point number $n on the path. Points
239 begin at 0 and if "$n < 0" then the return is an empty list.
240 Fractional positions give an X,Y position along a straight line
242 between the integer positions.
243 "$n = $path->n_start()"
245 Return 0, the first N in the path.
246 Level Methods
248 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
249 Return "(0, 2**$level - 1)", or for multiple arms return "(0, $arms
250 * 2**$level - 1)".
251 There are 2^level segments comprising the dragon, or arms*2^level
253 when multiple arms, numbered starting from 0.
254
256 X,Y to N
257 An X,Y point is turned into N by dividing out digits of a complex base
258 i+1. This base is per the doubling of the "DragonCurve" at each level.
259 In midpoint coordinates an adjustment subtracting 0 or 1 must be
260 applied to move an X,Y which is either N=2k or N=2k+1 to the position
261 where dividing out i+1 gives the N=k X,Y.
262 The adjustment is in a repeating pattern of 4x4 blocks. Points N=2k
264 and N=2k+1 both move to the same place corresponding to N=k multiplied
265 by i+1. The adjustment pattern is a little like the pair tiling shown
266 above, but for some pairs both the N=2k and N=2k+1 positions must move,
267 it's not enough just to shift the N=2k+1 to the N=2k.
268 Xadj Yadj
270 Ymod4 Ymod4
271 3 | 0 1 1 0 3 | 1 1 0 0
272 2 | 1 0 0 1 2 | 1 1 0 0
273 1 | 1 0 0 1 1 | 0 0 1 1
274 0 | 0 1 1 0 0 | 0 0 1 1
275 +-------- +--------
276 0 1 2 3 0 1 2 3
277 Xmod4 Xmod4
278 The same tables work for both the main curve and for the rotated copies
280 per "Arms" above.
281 until -1<=X<=0 and 0<=Y<=1
283 Xm = X - Xadj(X mod 4, Y mod 4)
285 Ym = Y - Yadj(X mod 4, Y mod 4)
286 new X,Y = (Xm+i*Ym) / (i+1)
288 = (Xm+i*Ym) * (1-i)/2
289 = (Xm+Ym)/2, (Ym-Xm)/2 # Xm+Ym and Ym-Xm are both even
290 Nbit = Xadj xor Yadj # bits of N low to high
292 The X,Y reduction stops at one of the start points for the four arms
294 X,Y endpoint Arm +---+---+
296 ------------ --- | 2 | 1 | Y=1
297 0, 0 0 +---+---+
298 0, 1 1 | 3 | 0 | Y=0
299 -1, 1 2 +---+---+
300 -1, 0 3 X=-1 X=0
301 For arms 1 and 3 the N bits must be flipped 0<->1. The arm number and
303 hence whether this flip is needed is not known until reaching the
304 endpoint.
305 For bignum calculations there's no need to apply the "/2" shift in
307 newX=(Xm+Ym)/2 and newY=(Ym-Xm)/2. Instead keep a bit position which
308 is the logical low end and pick out two bits from there for the
309 Xadj,Yadj lookup. A whole word can be dropped when the bit position
310 becomes a multiple of 32 or 64 or whatever.
311 Boundary
313 Taking unit squares at each point, the boundary MB[k] of the resulting
314 shape from 0 to N=2^k-1 inclusive can be had from the boundary B[k] of
315 the plain dragon curve. Taking points N=0 to N=2^k-1 inclusive is the
316 midpoints of the dragon curve line segments N=0 to N=2^k inclusive.
317 MB[k] = B[k] + 2
319 = 4, 6, 10, 18, 30, 50, 86, 146, 246, 418, 710, 1202, ...
320 2 + x + 2*x^2
322 generating function 2 * -------------
323 1 - x - 2*x^3
324 A unit square at the midpoint is a diamond on a dragon line segment
326 / \
328 / \ midpoint m
329 *--m--* diamond on dragon curve line segment
330 \ /
331 \ /
332 A boundary segment of the dragon curve has two sides of the diamond
334 which are boundary. But when the boundary makes a right hand turn two
335 such sides touch and are therefore not midpoint boundary.
336 /^\
338 / | \ right turn
339 \ | //\ two diamond sides touch
340 \|// \
341 *<----*
342 \ /
343 \ /
344 The dragon curve at N=0 points East and the last segment N=2^k-1 to
346 N=2^k is North. Since the curve never overlaps itself this means that
347 when going around the right side of the curve there is 1 more left turn
348 than right turn,
349 lefts - rights = 1
351 The total line segments on the right is the dragon curve R[k] and there
353 are R[k]-1 turns, so the total turns lefts+rights is
354 lefts + rights + 1 = R[k]
356 So the lefts and rights are obtained separately
358 2*lefts = R[k] adding the two equations
360 2*rights = R[k] - 2 subtracting the two equations
361 The result is then
363 MR[k] = 2*R[k] - 2*rights
365 = 2*R[k] - 2*(R[k]-2)/2
366 = R[k] + 2
367 A similar calculation is made on the left side of the curve. The net
369 turn is the same and so the same lefts-rights=1 and thus from the
370 dragon curve L[k] left boundary
371 ML[k] = 2*L[k] - 2*lefts
373 = 2*L[k] - 2*(L[k]/2)
374 = L[k]
375 The total is then
377 MB[k] = MR[k] + ML[k]
379 = R[k]+2 + L[k]
380 = B[k] + 2 since B[k]=R[k]+L[k]
381 The generating function can be had from the partial fractions form of
383 the dragon curve boundary. B[k]+2 means adding 2/(1-x) which cancels
384 out the -2/(1-x) in gB(x).
385
387 The "DragonMidpoint" is in Sloane's Online Encyclopedia of Integer
388 Sequences as
389 <http://oeis.org/A073089> (etc)
391 A073089 abs(dY) of n-1 to n, so 0=horizontal,1=vertical
393 (extra initial 0)
394 A077860 Y at N=2^k, being Re(-(i+1)^k + i-1)
395 A090678 0=straight, 1=not straight (extra initial 1,1)
396 A203175 boundary of unit squares N=0 to N=2^k-1, value 4 onwards
397 A073089
399 For A073089=abs(dY), the midpoint curve is vertical when the
400 "DragonCurve" has a vertical followed by a left turn, or horizontal
401 followed by a right turn. "DragonCurve" verticals are whenever N is
402 odd, and the turn is the bit above the lowest 0 in N (per "Turn" in
403 Math::PlanePath::DragonCurve). So
404 abs(dY) = lowbit(N) XOR bit-above-lowest-zero(N)
406 The n in A073089 is offset by 2 from the N numbering of the path here,
408 so n=N+2. The initial value at n=1 in A073089 has no corresponding N
409 (it would be N=-1).
410 The mod-16 definitions in A073089 express combinations of N odd/even
412 and bit-above-low-0 which are the vertical midpoint segments. The
413 recurrence a(8n+1)=a(4n+1) acts to strip zeros above a low 1 bit,
414 n = 0b..uu0001
416 -> 0b...uu001
417 In terms of N=n-2 this reduces
419 N = 0b..vv1111
421 -> 0b...vv111
422 which has the effect of seeking a lowest 0 in the range of the mod-16
424 conditions.
425
427 Math::PlanePath, Math::PlanePath::DragonCurve,
428 Math::PlanePath::DragonRounded
429 Math::PlanePath::AlternatePaperMidpoint,
431 Math::PlanePath::R5DragonMidpoint, Math::PlanePath::TerdragonMidpoint
432
434 <http://user42.tuxfamily.org/math-planepath/index.html>
435
437 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019 Kevin
438 Ryde
439 Math-PlanePath is free software; you can redistribute it and/or modify
441 it under the terms of the GNU General Public License as published by
442 the Free Software Foundation; either version 3, or (at your option) any
443 later version.
444 Math-PlanePath is distributed in the hope that it will be useful, but
446 WITHOUT ANY WARRANTY; without even the implied warranty of
447 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
448 General Public License for more details.
449 You should have received a copy of the GNU General Public License along
451 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
452perl v5.30.1 2020-01-30Math::PlanePath::DragonMidpoint(3)