.\" Automatically generated by Pod::Man 4.14 (Pod::Simple 3.40) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is >0, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{\ . if \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{\ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" ======================================================================== .\" .IX Title "Math::PlanePath::KochCurve 3pm" .TH Math::PlanePath::KochCurve 3pm "2021-01-23" "perl v5.32.0" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::KochCurve \-\- horizontal Koch curve .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::KochCurve; \& my $path = Math::PlanePath::KochCurve\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is an integer version of the self-similar Koch curve, .IX Xref "Koch, Helge von" .Sp .RS 4 Helge von Koch, \*(L"Une Méthode Géométrique Élémentaire pour l'Étude de Certaines Questions de la Théorie des Courbes Planes\*(R", Acta Arithmetica, volume 30, 1906, pages 145\-174. .RE .PP It goes along the X axis and makes triangular excursions upwards. .PP .Vb 7 \& 8 3 \& / \e \& 6\-\-\-\- 7 9\-\-\-\-10 18\-... 2 \& \e / \e \& 2 5 11 14 17 1 \& / \e / \e / \e / \& 0\-\-\-\-1 3\-\-\-\- 4 12\-\-\-\-13 15\-\-\-\-16 <\- Y=0 \& \& ^ \& X=0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 .Ve .PP The replicating shape is the initial N=0 to N=4, .PP .Vb 3 \& * \& / \e \& *\-\-\-* *\-\-\-* .Ve .PP which is rotated and repeated 3 times in the same pattern to give sections N=4 to N=8, N=8 to N=12, and N=12 to N=16. Then that N=0 to N=16 is itself replicated three times at the angles of the base pattern, and so on infinitely. .PP The X,Y coordinates are arranged on a square grid using every second point, per \*(L"Triangular Lattice\*(R" in Math::PlanePath. The result is flattened triangular segments with diagonals at a 45 degree angle. .SS "Level Ranges" .IX Subsection "Level Ranges" Each replication adds 3 copies of the existing points and is thus 4 times bigger, so if N=0 to N=4 is reckoned as level 1 then a given replication level goes from .PP .Vb 2 \& Nstart = 0 \& Nlevel = 4^level (inclusive) .Ve .PP Each replication is 3 times the width. The initial N=0 to N=4 figure is 6 wide and in general a level runs from .PP .Vb 2 \& Xstart = 0 \& Xlevel = 2*3^level at N=Nlevel .Ve .PP The highest Y is 3 times greater at each level similarly. The peak is at the midpoint of each level, .PP .Vb 3 \& Npeak = (4^level)/2 \& Ypeak = 3^level \& Xpeak = 3^level .Ve .PP It can be seen that the N=6 point backtracks horizontally to the same X as the start of its section N=4 to N=8. This happens in the further replications too and is the maximum extent of the backtracking. .PP The Nlevel is multiplied by 4 to get the end of the next higher level. The same 4*N can be applied to all points N=0 to N=Nlevel to get the same shape but a factor of 3 bigger X,Y coordinates. The in-between points 4*N+1, 4*N+2 and 4*N+3 are then new finer structure in the higher level. .SS "Fractal" .IX Subsection "Fractal" Koch conceived the curve as having a fixed length and infinitely fine structure, making it continuous everywhere but differentiable nowhere. The code here can be pressed into use for that sort of construction for a given level of granularity by scaling .PP .Vb 2 \& X/3^level \& Y/3^level .Ve .PP which makes it a fixed 2 wide by 1 high. Or for unit-side equilateral triangles then apply further factors 1/2 and \fBsqrt\fR\|(3)/2, as noted in \&\*(L"Triangular Lattice\*(R" in Math::PlanePath. .PP .Vb 2 \& (X/2) / 3^level \& (Y*sqrt(3)/2) / 3^level .Ve .SS "Area" .IX Subsection "Area" The area under the curve to a given level can be calculated from its self-similar nature. The curve at level+1 is 3 times wider and higher and adds a triangle of unit area onto each line segment. So reckoning the line segment N=0 to N=1 as level=0 (which is area[0]=0), .PP .Vb 2 \& area[level] = 9*area[level\-1] + 4^(level\-1) \& = 4^(level\-1) + 9*4^(level\-2) + ... + 9^(level\-1)*4^0 \& \& 9^level \- 4^level \& = \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& 5 \& \& = 0, 1, 13, 133, 1261, 11605, 105469, ... (A016153) .Ve .PP The sides are 6 different angles. The triangles added on the sides are always the same shape either pointing up or down. Base width=2 and height=1 gives area=1. .PP .Vb 4 \& * *\-\-\-\-\-* ^ \& / \e \e / | height=1 \& / \e \e / | \& *\-\-\-\-\-* * v triangle area = 2*1/2 = 1 \& \& <\-\-\-\-\-> width=2 .Ve .PP If the Y coordinates are stretched to make equilateral triangles then the number of triangles is not changed and so the area increases by a factor of the area of the equilateral triangle, \fBsqrt\fR\|(3)/4. .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::KochCurve\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::KochCurve\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::KochCurve->new ()" Create and return a new path object. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .Sp Fractional positions give an X,Y position along a straight line between the integer positions. .ie n .IP """($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->rect_to_n_range ($x1,$y1, $x2,$y2)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)" The returned range is exact, meaning \f(CW$n_lo\fR and \f(CW$n_hi\fR are the smallest and biggest in the rectangle. .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 0, the first N in the path. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, 4**$level)\*(C'\fR. .SH "FORMULAS" .IX Header "FORMULAS" .SS "N to Turn" .IX Subsection "N to Turn" The curve always turns either +60 degrees or \-120 degrees, it never goes straight ahead. In the base 4 representation of N, the lowest non-zero digit gives the turn. The first turn is at N=1 so there's always a non-zero digit in N. .PP .Vb 6 \& low digit \& base 4 turn \& \-\-\-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\- \& 1 +60 degrees (left) \& 2 \-120 degrees (right) \& 3 +60 degrees (left) .Ve .PP For example N=8 is 20 base 4, so lowest nonzero \*(L"2\*(R" means turn \-120 degrees for the next segment. .PP If the least significant digit is non-zero then it determines the turn, making the base N=0 to N=4 shape. If the least significant is zero then the next level up is in control, eg. N=0,4,8,12,16, making a turn according to the base shape again at that higher level. The first and last segments of the base shape are \*(L"straight\*(R" so there's no extra adjustment to apply in those higher digits. .PP This base 4 digit rule is equivalent to counting low 0\-bits. A low base\-4 digit 1 or 3 is an even number of low 0\-bits and a low digit 2 is an odd number of low 0\-bits. .PP .Vb 4 \& count low 0\-bits turn \& \-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\- \& even +60 degrees (left) \& odd \-120 degrees (right) .Ve .PP For example N=8 in binary \*(L"1000\*(R" has 3 low 0\-bits and 3 is odd so turn \-120 degrees (right). .PP See \*(L"Turn\*(R" in Math::PlanePath::GrayCode for a similar turn sequence arising from binary Gray code. .SS "N to Next Turn" .IX Subsection "N to Next Turn" The turn at N+1, ie the next turn, can be found from the base\-4 digits by considering how the digits of N change when 1 is added, and the low-digit turn calculation is applied on those changed digits. .PP Adding 1 means low digit 0, 1 or 2 will become non-zero. Any low 3s wrap around to become low 0s. So the turn at N+1 can be found from the digits of N by seeking the lowest non\-3 .PP .Vb 6 \& lowest non\-3 turn \& digit of N at N+1 \& \-\-\-\-\-\-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\- \& 0 +60 degrees (left) \& 1 \-120 degrees (right) \& 2 +60 degrees (left) .Ve .SS "N to Direction" .IX Subsection "N to Direction" The total turn at a given N can be found by counting digits 1 and 2 in base 4. .PP .Vb 2 \& direction = ((count of 1\-digits in base 4) \& \- (count of 2\-digits in base 4)) * 60 degrees .Ve .PP For example N=11 is \*(L"23\*(R" in base 4, so 60*(0\-1) = \-60 degrees. .PP In this formula the count of 1s and 2s can go past 360 degrees, representing a spiralling around which occurs at progressively higher replication levels. The direction can be taken mod 360 degrees, or the count mod 6, for a direction 0 to 5 if desired. .SS "N to abs(dX),abs(dY)" .IX Subsection "N to abs(dX),abs(dY)" The direction expressed as abs(dX) and abs(dY) can be calculated simply from N modulo 3. abs(dX) is a repeating pattern 2,1,1 and abs(dY) repeating 0,1,1. .PP .Vb 5 \& N mod 3 abs(dX),abs(dY) \& \-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\-\-\- \& 0 2,0 horizontal, East or West \& 1 1,1 slope North\-East or South\-West \& 2 1,1 slope North\-West or South\-East .Ve .PP This works because the direction calculation above corresponds to N mod 3. Each N digit in base 4 becomes .PP .Vb 7 \& N digit \& base 4 direction add \& \-\-\-\-\-\-\- \-\-\-\-\-\-\-\-\-\-\-\-\- \& 0 0 \& 1 1 \& 2 \-1 \& 3 0 .Ve .PP Notice that direction == Ndigit mod 3. Then because 4==1 mod 3 the power\-of\-4 for each digit reduces down to 1, .PP .Vb 5 \& N = 4^k * digit_k + ... 4^0 * digit_0 \& N mod 3 = 1 * digit_k + ... 1 * digit_0 \& = digit_k + ... digit_0 \& same as \& direction = digit_k + ... + digit_0 taken mod 3 .Ve .SS "Rectangle to N Range \*(-- Level" .IX Subsection "Rectangle to N Range Level" An easy over-estimate of the N values in a rectangle can be had from the Xlevel formula above. If Xlevel>rectangleX then Nlevel is past the rectangle extent. .PP .Vb 1 \& X = 2*3^level .Ve .PP so .PP .Vb 2 \& floorlevel = floor log_base_3(X/2) \& Nhi = 4^(floorlevel+1) \- 1 .Ve .PP For example a rectangle extending to X=13 has floorlevel = floor(log3(13/2))=1 and so Nhi=4^(1+1)\-1=15. .PP The rounding-down of the log3 ensures a point such as X=18 which is the first in the next Nlevel will give that next level. So floorlevel=log3(18/2)=2 (exactly) and Nhi=4^(2+1)\-1=63. .PP The worst case for this over-estimate is when rectangleX==Xlevel, ie. the rectangle is just into the next level. In that case Nhi is nearly a factor 4 bigger than it needs to be. .SS "Rectangle to N Range \*(-- Exact" .IX Subsection "Rectangle to N Range Exact" The exact Nlo and Nhi in a rectangle can be found by searching along the curve. For Nlo search forward from the origin N=0. For Nhi search backward from the Nlevel over-estimate described above. .PP At a given digit position in the prospective N the sub-part of the curve comprising the lower digits has a certain triangular extent. If it's outside the target rectangle then step to the next digit value, and to the next of the digit above when past digit=3 (or below digit=0 when searching backwards). .PP There's six possible orientations for the curve sub-part. In the following pictures \*(L"o\*(R" is the start and the surrounding lines show the triangular extent. There's just four curve parts shown in each, but these triangles bound a sub-curve of any level. .PP .Vb 6 \& rot=0 \-+\- +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ \& \-\- \-\- \- .\-+\-* *\-+\-o \- \& \-\- * \-\- \-\- \e / \-\- \& \-\- / \e \-\- \-\- * \-\- \& \- o\-+\-* *\-+\-. \- \-\- \-\- \& +\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-+ rot=3 \-+\- \& \& rot=1 \& +\-\-\-\-\-\-\-\-\-+ rot=4 /+ \& | . / / | \& | / / / o| \& |*\-+\-* / / / | \& | \e / / * | \& | * / / \e | \& | / / / *\-+\-*| \& |o / / / | \& | / / . | \& +/ +\-\-\-\-\-\-\-\-\-+ \& \& +\e rot=2 +\-\-\-\-\-\-\-\-\-+ \& | \e \e o | \& |. \e \e \e | \& | \e \e \e *\-+\-*| \& | * \e \e / | \& | / \e \e * | \& |*\-+\-* \e \e \e | \& | \e \e \e .| \& | o \e rot=5 \e | \& +\-\-\-\-\-\-\-\-\-+ \e+ .Ve .PP The \*(L".\*(R" is the start of the next sub-curve. It belongs to the next digit value and so can be excluded. For rot=0 and rot=3 this means simply shortening the X range permitted. For rot=1 and rot=4 similarly the Y range. For rot=2 and rot=5 it would require a separate test. .PP Tight sub-part extent checking reduces the sub-parts which are examined, but it works perfectly well with a looser check, such as a square box for the sub-curve extents. Doing that might be easier if the target region is not a rectangle but instead some trickier shape. .SH "OEIS" .IX Header "OEIS" The Koch curve is in Sloane's Online Encyclopedia of Integer Sequences in various forms, .Sp .RS 4 (etc) .RE .PP .Vb 2 \& A335358 (X\-Y)/2 diagonal coordinate \& A335359 Y coordinate \& \& A035263 turn 1=left,0=right, by morphism \& A096268 turn 0=left,1=right, period doubling sequence \& A056832 turn 1=left,2=right, by replicate and flip last \& A309873 turn 1=left,\-1=right \& A029883 turn +/\-1=left,0=right, Thue\-Morse first differences \& A089045 turn +/\-1=left,0=right, by +/\- something \& \& A177702 abs(dX) from N=1 onwards, being 1,1,2 repeating \& A011655 abs(dY), being 0,1,1 repeating \& \& A003159 N positions of left turns, ending even number 0 bits \& A036554 N positions of right turns, ending odd number 0 bits \& A332206 N on X axis \& A001196 N segments on X axis (N and N+1 on X axis) \& \& A065359 segment direction, *60 degrees \& A229216 segment direction, 1,2,3,\-1,\-2,\-3 \& A050292 num left turns 1 to N \& A123087 num right turns 1 to N \& A020988 num left turns 1 to 4^k\-1, being 2*(4^k\-1)/3 \& A002450 num right turns 1 to 4^k\-1, being (4^k\-1)/3 \& A016153 area under the curve, (9^k\-4^k)/5 .Ve .PP For reference, A217586 is not quite the same as A096268 right turn. A217586 differs by a 0<\->1 flip at N=2^k due to different initial a(1)=1. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::KochPeaks, Math::PlanePath::KochSnowflakes, Math::PlanePath::CCurve .PP Math::Fractal::Curve .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE.\s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .