Math::...idpoint(3pm)
✨ NAME ✨
Math::PlanePath::DragonMidpoint — dragon curve midpoints 🐉💖
okay so first thing, the header line at the very top of this page reads Math::...idpoint(3pm) and it's from the User Contributed Perl Documentation, section 3pm. That's the manual name, folded in right here at the top because bestie we do not waste a line. The module it's actually about is Math::PlanePath::DragonMidpoint. 🫶
🎀 SYNOPSIS 🎀
use Math::PlanePath::DragonMidpoint;
my $path = Math::PlanePath::DragonMidpoint->new;
my ($x, $y) = $path->n_to_xy (123);🌈 DESCRIPTION 🌈
okay so picture the dragon curve — the one by Heighway, Harter, et al, the one you already know from Math::PlanePath::DragonCurve. This path right here is the midpoint of every single segment of that curve. Every segment. No skips. 💅
17--16 9---8 5
| | | |
18 15 10 7 4
| | | |
19 14--13--12--11 6---5---4 3
| |
20--21--22 3 2
| |
33--32 25--24--23 2 1
| | | |
34 31 26 0---1 <- Y=0
| | |
35 30--29--28--27 -1
|
36--37--38 43--44--45--46 -2
| | |
39 42 49--48--47 -3
| | |
40--41 50 -4
|
51 -5
|
52--53--54 -6
|
..--64 57--56--55 -7
| |
63 58 -8
| |
62--61--60--59 -9
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1So the dragon curve kicks off like this, and the midpoints of each segment get numbered starting from 0:
+--8--+ +--4--+
| | | |
9 7 5 3
| | | | |
+-10--+--6--+ +--2--+ rotate 45 degrees |
| | v
11 1
| |
+-12--+ *--0--+ * = Origin
|
...These midpoints sit on fractions like X=0.5,Y=0, X=1,Y=0.5, etc. But for this "DragonMidpoint" path they get turned clockwise 45 degrees and shrunk by sqrt(2) so they land on integer X,Y values a unit apart, with the initial direction pointing to the right. ✨
The midpoints are all distinct X,Y positions, and that's not a coincidence — it's because the dragon curve traverses each edge only once. Slay.
The dragon curve is self-similar in 2^level sections because of how it unfolds, and you can literally see that in the midpoints too: for example above, N=0 to N=16 is the exact same shape as N=16 to N=32, except the latter is rotated 90 degrees and running in reverse. Iconic behaviour honestly. 🦋
For reference (iykyk), Knuth in "Diamonds and Dragons" uses a different numbering for segment midpoints — there the dragon orientation stays unchanged and instead you multiply by 2 to make the midpoints integers. Like, the first dragon midpoint at X=1/2,Y=0 gets doubled out to X=1,Y=0. You can get that from the path here with:
KnuthX = X - Y + 1
KnuthY = X + Y🌸 Arms 🌸
Just like the "DragonCurve", these midpoints fill a quarter of the plane, and four copies mesh together perfectly when you rotate them by 90, 180 and 270 degrees. The "arms" parameter lets you pick 1 to 4 curve arms, successively advancing. 💫
So for example "arms => 4" starts out like this, where N=0,4,8,12,etc are the first arm (same as the plain curve up above), N=1,5,9,13 are the second, N=2,6,10,14 the third, and N=3,7,11,15 the fourth:
arms => 4
...-107-103 83--79--75--71 6
| | |
68--64 36--32 99 87 59--63--67 5
| | | | | | |
72 60 40 28 95--91 55 4
| | | | |
76 56--52--48--44 24--20--16 51 3
| | |
80--84--88 17--13---9---5 12 47--43--39 ... 2
| | | | | |
100--96--92 21 6---2 1 8 27--31--35 106 1
| | | | | |
104 33--29--25 10 3 0---4 23 94--98-102 <- Y=0
| | | | | |
... 37--41--45 14 7--11--15--19 90--86--82 -1
| | |
49 18--22--26 46--50--54--58 78 -2
| | | | |
53 89--93 30 42 62 74 -3
| | | | | | |
65--61--57 85 97 34--38 66--70 -4
| | |
69--73--77--81 101-105-... -5
^
-6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5With four arms like this, every single X,Y point is visited exactly once — because four arms of the "DragonCurve" traverse every edge exactly once. No overlap, no drama. periodt. 👑
🧚 Tiling 🧚
Now take pairs of adjacent points, N=2k and N=2k+1, and you get these little rectangles that tile the plane in a pattern repeating every 4x4 blocks:
+---+---+---+-+-+---+-+-+---+
| | | | | | | | | | |
+---+ | +---+ | +---+ | +---+
| | | |9 8| | | | | | |
+-+-+---+-+-+-+-+-+-+-+-+-+-+
| | | | |7| | | | | | |
| | +---+ | +---+ | +---+ | |
| | | | |6|5 4| | | | | |
+---+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |3| | | | |
+---+ | +---+ | +---+ | +---+
| | | | | |2| | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | |0 1| | | | | | <- Y=0
| | +---+ | +---+ | +---+ | |
| | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | |
+---+ | +---+ | +---+ | +---+
| | | | | | | | | | |
+---+-+-+---+-+-+---+-+-+---+
^
X=0The pairs follow this pattern both for the main curve N=0 etc shown above, and also for the rotated copies per "Arms". And this tiling lives in the tilingsearch database as
<http://tilingsearch.org/HTML/data24/K02A.html>
Then if you take pairs N=2k+1 and N=2k+2 — that's every odd N and its successor — you get a regular pattern too, but this time it repeats in blocks of 16x16:
|||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--|||
|||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--|||
-||------||------||------||------||------||------||------||-----
-||------||------||------||------||------||------||------||-----
|||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
|||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
-----||------||------||------||------||------||------||------||-
-----||------||------||------||------||------||------||------||-
-||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||-
-||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||-
-||------||------||------||------||------||------||------||-----
-||------||------||------||------||------||------||------||-----
|||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
|||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
-----||------||------||------||------||------||------||------||-
-----||------||------||------||------||------||------||------||-
|||--||||||--||--||--||||||--|| ||--||||||--||--||--||||||--|||
|||--||||||--||--||--||||||--|| ||--||||||--||--||--||||||--|||
-||------||------||------||------||------||------||------||-----
-||------||------||------||------||------||------||------||-----
|||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
|||--||||||||||||||--||||||||||||||--||||||||||||||--|||||||||||
-----||------||------||------||------||------||------||------||-
-----||------||------||------||------||------||------||------||-
-||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||-
-||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||-
-||------||------||------||------||------||------||------||-----
-||------||------||------||------||------||------||------||-----
|||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
|||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--|||
-----||------||------||------||------||------||------||------||-
-----||------||------||------||------||------||------||------||-💜 Curve from Midpoints 💜
So here's the cute part. The dragon curve always turns left or right — never straight ahead, never reverse — which means its segments are alternately horizontal and vertical. Rotate that -45 degrees for the midpoints here and it means the segments are alternately "opposite diagonal" and "leading diagonal". They land on X,Y alternately even or odd.
Which means you can recover the original dragon curve straight from the midpoints by choosing leading diagonal or opposite diagonal for each segment depending on whether X,Y is even or odd — and that's the same thing as N being even or odd. 🧠✨
DragonMidpoint dragon segment
-------------- -----------------
"even" N==0 mod 2 opposite diagonal
which is X+Y==0 mod 2 too
"odd" N==1 mod 2 leading diagonal
which is X+Y==1 mod 2 too /
3 0 at X=0,Y=0 "even", opposite diagonal
/ 1 at X=1,Y=0 "odd", leading diagonal
\ etc
2
\
\ /
0 1
\ /✨ FUNCTIONS ✨
bestie before we get into the good stuff — there's a whole shared behaviour thing that every path class in this family does. it lives in Math::PlanePath, under its own FUNCTIONS section. go read that one if you want the common tea. ☕
here's what this path gives you specifically, no cap:
$path = Math::PlanePath::DragonMidpoint->new ()— make a brand new path object and hand it back to you. it's giving fresh start energy ✨($x,$y) = $path->n_to_xy ($n)— gimme the X,Y coords of point number$non the path. points kick off at0, and if$n < 0then bestie you get an empty list back, that's just how it is 😭- fractional positions? they give you an X,Y sitting somewhere along a straight line between the integer positions. so like, in-between vibes, literally.
$n = $path->n_start()— returns0, which is the very first N in the path. the origin story fr fr 🎀
🦋 Level Methods 🦋
($n_lo, $n_hi) = $path->level_to_n_range($level)— hands you back(0, 2**$level - 1), or if there's more than one arm it's(0, $arms * 2**$level - 1)instead.- the dragon is made of
2^levelsegments, orarms*2^levelwhen you've got multiple arms, and the numbering starts from0. periodt.
- the dragon is made of
🌈 FORMULAS 🌈
💅 X,Y to N 💅
okay so how do we turn an X,Y point back into an N? the move is to divide out digits of a complex base i+1. this base is exactly per the doubling of the DragonCurve at each level. iykyk.
but here's the lil plot twist: in midpoint coordinates you gotta apply an adjustment — subtracting 0 or 1 — to shift an X,Y that's either N=2k or N=2k+1 over to the spot where dividing out i+1 gives you the N=k X,Y. sneaky but iconic.
that adjustment follows a repeating pattern of 4x4 blocks. both N=2k and N=2k+1 slide to the same place, which corresponds to N=k multiplied by i+1. the adjustment pattern is kinda like the pair tiling shown up above, EXCEPT for some pairs both the N=2k and N=2k+1 positions have to move — it's not enough to just shift the N=2k+1 onto the N=2k. nope, both of y'all are moving. 💀
Xadj Yadj
Ymod4 Ymod4
3 | 0 1 1 0 3 | 1 1 0 0
2 | 1 0 0 1 2 | 1 1 0 0
1 | 1 0 0 1 1 | 0 0 1 1
0 | 0 1 1 0 0 | 0 0 1 1
+-------- +--------
0 1 2 3 0 1 2 3
Xmod4 Xmod4the exact same tables work for the main curve and for the rotated copies per Arms up above. equal opportunity tables 💖
until -1<=X<=0 and 0<=Y<=1
Xm = X - Xadj(X mod 4, Y mod 4)
Ym = Y - Yadj(X mod 4, Y mod 4)
new X,Y = (Xm+i*Ym) / (i+1)
= (Xm+i*Ym) * (1-i)/2
= (Xm+Ym)/2, (Ym-Xm)/2 # Xm+Ym and Ym-Xm are both even
Nbit = Xadj xor Yadj # bits of N low to highthe X,Y reduction stops once you hit one of the start points for the four arms:
X,Y endpoint Arm +---+---+
------------ --- | 2 | 1 | Y=1
0, 0 0 +---+---+
0, 1 1 | 3 | 0 | Y=0
-1, 1 2 +---+---+
-1, 0 3 X=-1 X=0for arms 1 and 3 the N bits have to be flipped 0<->1. and plot twist — the arm number, and therefore whether you even need that flip, isn't known until you reach the endpoint. suspense! 🙈
for bignum calculations there's no need to actually apply the /2 shift in newX=(Xm+Ym)/2 and newY=(Ym-Xm)/2. instead just keep a bit position which is the logical low end, and pick out two bits from there for the Xadj,Yadj lookup. then a whole word can be dropped whenever the bit position becomes a multiple of 32 or 64 or whatever. efficient queen behavior 👑
🌸 Boundary 🌸
take unit squares at each point, and the boundary MB[k] of the resulting shape from 0 to N=2^k-1 inclusive can be had from the boundary B[k] of the plain dragon curve. taking points N=0 to N=2^k-1 inclusive gives you the midpoints of the dragon curve line segments N=0 to N=2^k inclusive.
MB[k] = B[k] + 2
= 4, 6, 10, 18, 30, 50, 86, 146, 246, 418, 710, 1202, ...
2 + x + 2*x^2
generating function 2 * -------------
1 - x - 2*x^3a unit square sitting at the midpoint is basically a diamond perched on a dragon line segment:
/ \
/ \ midpoint m
*--m--* diamond on dragon curve line segment
\ /
\ /a boundary segment of the dragon curve has two sides of the diamond that are boundary. BUT — when the boundary makes a right hand turn, two of those sides touch each other and therefore are not midpoint boundary. dramatic.
/^\
/ | \ right turn
\ | //\ two diamond sides touch
\|// \
*<----*
\ /
\ /the dragon curve at N=0 points East and the last segment N=2^k-1 to N=2^k is North. since the curve never overlaps itself, this means that when you go around the right side of the curve there's 1 more left turn than right turn:
lefts - rights = 1the total line segments on the right is the dragon curve R[k] and there are R[k]-1 turns, so the total turns lefts+rights is:
lefts + rights + 1 = R[k]so the lefts and rights come out separately, like:
2*lefts = R[k] adding the two equations
2*rights = R[k] - 2 subtracting the two equationsand then the result is:
MR[k] = 2*R[k] - 2*rights
= 2*R[k] - 2*(R[k]-2)/2
= R[k] + 2a similar calculation gets made on the left side of the curve. the net turn is the same, so you get the same lefts-rights=1, and thus from the dragon curve L[k] left boundary:
ML[k] = 2*L[k] - 2*lefts
= 2*L[k] - 2*(L[k]/2)
= L[k]and the total is then:
MB[k] = MR[k] + ML[k]
= R[k]+2 + L[k]
= B[k] + 2 since B[k]=R[k]+L[k]the generating function can be had from the partial fractions form of the dragon curve boundary. B[k]+2 means adding 2/(1-x), which cancels out the -2/(1-x) in gB(x). math ate, no crumbs 🍓
👑 OEIS 👑
the DragonMidpoint is in Sloane's Online Encyclopedia of Integer Sequences as
<http://oeis.org/A073089> (etc)
A073089 abs(dY) of n-1 to n, so 0=horizontal,1=vertical
(extra initial 0)
A077860 Y at N=2^k, being Re(-(i+1)^k + i-1)
A090678 0=straight, 1=not straight (extra initial 1,1)
A203175 boundary of unit squares N=0 to N=2^k-1, value 4 onwards🧚 A073089 🧚
for A073089=abs(dY), the midpoint curve is vertical when the DragonCurve has a vertical followed by a left turn, or a horizontal followed by a right turn. DragonCurve verticals happen whenever N is odd, and the turn is the bit above the lowest 0 in N (per Turn in Math::PlanePath::DragonCurve). so:
abs(dY) = lowbit(N) XOR bit-above-lowest-zero(N)the n in A073089 is offset by 2 from the N numbering of the path here, so n=N+2. the initial value at n=1 in A073089 has no corresponding N (it would be N=-1). a ghost value, honestly 💀
the mod-16 definitions in A073089 express combinations of N odd/even and bit-above-low-0, which are the vertical midpoint segments. the recurrence a(8n+1)=a(4n+1) acts to strip zeros above a low 1 bit:
n = 0b..uu0001
-> 0b...uu001in terms of N=n-2 this reduces:
N = 0b..vv1111
-> 0b...vv111which has the effect of seeking a lowest 0 in the range of the mod-16 conditions. it's giving detective work 🔍
💜 SEE ALSO 💜
Math::PlanePathMath::PlanePath::DragonCurveMath::PlanePath::DragonRoundedMath::PlanePath::AlternatePaperMidpointMath::PlanePath::R5DragonMidpointMath::PlanePath::TerdragonMidpoint
🌟 HOME PAGE 🌟
<http://user42.tuxfamily.org/math-planepath/index.html>
🎀 LICENSE 🎀
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
Math-PlanePath 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.
Math-PlanePath 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 Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
💖 okay bestie that's the whole page!! this one came from the Math-PlanePath perl v5.32.0 release, dated 2021-01-23, and it's filed under Math::...idpoint(3pm) in the user-contributed perl docs. go forth and divide out some i+1 digits, you absolute icon 🫶✨
📦 where this page comes from
- debian bookworm: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- debian trixie: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu jammy: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu noble: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu resolute: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- ubuntu stonking: libmath-planepath-perl 129-1 · GPL-3.0-or-later
- 💖 girlified by deepseek-ai/DeepSeek-V4.1-Flash on : a language model's rewrite of the original, under its terms