Math-PlanePath
view release on metacpan or search on metacpan
lib/Math/PlanePath/DragonCurve.pm view on Meta::CPAN
The X,Y extents of the path through to Nlevel=2^level can be expressed as a
"length" in the direction of the Xlevel,Ylevel endpoint and a "width"
across.
level even, so endpoint is a straight line
k = level/2
+--+ <- Lmax
| |
| E <- Lend = 2^k at Nlevel=2^level
|
+-----+
|
O | <- Lstart=0
| |
+--+ <- Lmin
^ ^
Wmin Wmax
Lmax = (7*2^k - 4)/6 if k even
(7*2^k - 2)/6 if k odd
Lmin = - (2^k - 1)/3 if k even
- (2^k - 2)/3 if k odd
Wmax = (2*2^k - 2) / 3 if k even
(2*2^k - 1) / 3 if k odd
Wmin = Lmin
For example level=2 is to Nlevel=2^2=4 and k=level/2=1 is odd so it measures
as follows,
4 <- Lmax = (7*2^1 - 2)/6 = 2
|
3--2
|
0--1 <- Lmin = -(2^1 - 2)/3 = 0
^ ^Wmax = (2*2^1 - 1)/3 = 1
|
Wmin = Lmin = 0
Or level=4 is to Nlevel=2^4=16 and k=4/2=2 is even. It measures as follows.
The lengthways "L" measures are in the direction of the N=16 endpoint and
the "W" measures are across.
9----8 5---4 <- Wmax = (2*2^2 - 2)/3 = 2
| | | |
10--11,7---6 3---2
| |
16 13---12 0---1
| |
15---14 <- Wmin = -(2^2 - 1)/3 = -1
^ ^Lmin = Wmin = -1
|
Lmax = (7*2^2 - 4)/6 = 4
The formulas are all integer values, but the fractions 7/6, 1/3 and 2/3 show
the limits as the level increases. If scaled so that length Lend=2^k is
reckoned as 1 unit then Lmax extends 1/6 past the end, Lmin and Wmin extend
1/3, and Wmax extends across 2/3.
+--------+ --
| - | 1/6 total length
|| | | = 1/6+1+1/3 = 3/2
|| E | --
|| |
|| |
| \ | 1
| \ |
| --\ |
| \ |
| ||
| O || --
| | ||
| | || 1/3
| ---- |
+--------+ --
1/3| 2/3
total width = 1/3+2/3 = 1
=head2 Paper Folding
The path is called a paper folding curve because it can be generated by
thinking of a long strip of paper folded in half repeatedly and then
unfolded so each crease is a 90 degree angle. The effect is that the curve
repeats in successive doublings turned by 90 degrees and reversed.
The first segment unfolds, pivoting at the "1",
2
-> |
unfold / |
===> | |
|
0-------1 0-------1
Then the same again with that L shape, pivoting at the "2", then after that
pivoting at the "4", and so on.
4
|
|
|
3--------2
2 |
| unfold ^ |
| ===> \_ |
| |
0------1 0--------1
It can be shown that this unfolding doesn't overlap itself but the corners
may touch, such as at the X=-2,Y=1 etc noted above.
=head1 FUNCTIONS
See L<Math::PlanePath/FUNCTIONS> for behaviour common to all path classes.
=over 4
=item C<$path = Math::PlanePath::DragonCurve-E<gt>new ()>
=item C<$path = Math::PlanePath::DragonCurve-E<gt>new (arms =E<gt> $int)>
Create and return a new path object.
The optional C<arms> parameter can make 1 to 4 copies of the curve, each arm
successively advancing.
=item C<($x,$y) = $path-E<gt>n_to_xy ($n)>
Return the X,Y coordinates of point number C<$n> on the path. Points begin
at 0 and if C<$n E<lt> 0> then the return is an empty list.
Fractional C<$n> gives an X,Y position along a straight line between the
integer positions.
=item C<$n = $path-E<gt>xy_to_n ($x,$y)>
Return the point number for coordinates C<$x,$y>. If there's nothing at
C<$x,$y> then return C<undef>.
The curve visits an C<$x,$y> twice for various points (all the "inside"
points). The smaller of the two N values is returned.
=item C<@n_list = $path-E<gt>xy_to_n_list ($x,$y)>
Return a list of N point numbers for coordinates C<$x,$y>.
The origin 0,0 has C<arms_count()> many N since it's the starting point for
each arm. Other points have up to two Ns for a given C<$x,$y>. If arms=4
then every C<$x,$y> except the origin has exactly two Ns.
=item C<$n = $path-E<gt>n_start()>
Return 0, the first N in the path.
=back
=head2 Level Methods
=over
=item C<($n_lo, $n_hi) = $path-E<gt>level_to_n_range($level)>
Return C<(0, 2**$level)>, or for multiple arms return C<(0, $arms *
2**$level + ($arms-1))>.
There are 2^level segments in a curve level, so 2^level+1 points numbered
from 0. For multiple arms there are arms*(2^level+1) points, numbered from
0 so n_hi = arms*(2^level+1)-1.
=back
=head1 FORMULAS
Various formulas for coordinates, lengths and area can be found in the
author's long mathematical write-up
=over
L<http://user42.tuxfamily.org/dragon/index.html>
=back
=cut
# =head2 N to X,Y
#
# The location of a given N is found from the bits of N taken high to low
#
# s = 1, X,Y=0,0
# for bits of N high to low
# (X,Y) = (X+Y+s*bit, X-Y) multiply b=1+i, add s if bit==1
# if bit above and this bit == 01 then s = -s
#
# At the high bit of N the bit above is 0, so there is a sign change s=-s at
# the highest 1 in N. The effect is a change of base from binary to base b,
# but with a sign change below each 01 bit pair. This works by considering
# the second half as a rotated reversed curve, or alternatively by maintaining
# and following a direction s.
=pod
=head2 X,Y to N
The current code uses the C<DragonMidpoint> C<xy_to_n()> by rotating -45
degrees and offsetting to the midpoints of the four edges around the target
X,Y. The C<DragonMidpoint> algorithm then gives four candidate N values and
those which convert back to the desired X,Y in the C<DragonCurve>
C<n_to_xy()> are the results for C<xy_to_n_list()>.
Xmid,Ymid = X+Y, Y-X # rotate -45 degrees
for dx = 0 or -1
for dy = 0 or 1
N candidate = DragonMidpoint xy_to_n(Xmid+dx,Ymid+dy)
Since there's at most two C<DragonCurve> Ns at a given X,Y the loop can stop
when two Ns are found.
Only the "leaving" edges will convert back to the target N, so only two of
the four edges actually need to be considered. Is there a way to identify
them? For arm 1 and 3 the leaving edges are up,down on odd points (meaning
sum X+Y odd) and right,left for even points (meaning sum X+Y even). But for
arm 2 and 4 it's the other way around. Without an easy way to determine the
arm this doesn't seem to help.
=head2 X,Y is Visited
Whether a given X,Y is visited by the curve can be determined from one or
two segments (rather then up to four for X,Y to N).
| S midpoint Xmid = X+Y
| Ymid = Y-X
*---T--X,Y--S---*
| T midpoint Xmid-1
| Ymid+1
( run in 0.422 second using v1.01-cache-2.11-cpan-df04353d9ac )