Code for Electronic Supplement

The Turtle.m Package

BeginPackage["Turtle`", "ComputationalGeometry`"];
CurveDepth::"usage"="CurveDepth is an option to TSPSpaceFillingCurve that specifies the depth of the space-filling curve approximation to use when estimating the position of points on the curve.";
FractalTurtle::"usage"="FractalTurtle[r, s, d, a] creates (in \"TurtlePath\") and shows the list of points that a turtle would make if it starts from s and then applies the rewrite rule d times. The size of the turns is set by a. Strings can involve F, B, +, -, and i, which instruct the turtle to move forward, move back, turn left, turn right, and roll over, respectively. The characters [ (push) and ] (pop) can also be used to store a location in a stack and pop back to it.";
RandomPoints::"usage"="RandomPoints[n] gives n random points in the unit square.";
ShowLabeledPoints::"usage"="ShowLabeledPoints[p] shows the points in p in a large size with random soft colors and the labels inside the points.";
StartPosition::"usage"="StartPosition is an option to FractalTurtle that specifies the point at which the turtle starts its journey.";
StartDirection::"usage"="StartDirection is an option to FractalTurtle that specifies the initial direction the turtle faces. It must be a unit vector.";
TerminalSubstitution::"usage"="TerminalSubstitution is an option to FractalTurtle that causes one additional substitution (or many if it is set to be a list) to be made after the specified depth is reached.";
TSPSpaceFillingCurve::"usage"="TSPSpaceFillingCurve[p] uses a Hilbert space-filling curve to come up with a traveling salesman tour through the given points that is, on average, not too far from optimal.";
TourCost::"usage"="TourCost[tour,points] gives the sum of the straight-line lengths corresponding to a trip through the points in data in the order determined by tour.";
TurtleStep::"usage"="TurtleStep is an option to FractalTurtle that specifies the length of each turtle step.";
TurtlePath::"usage"="TurtlePath is where the points of the turtle's path are stored by FractalTurtle.";
LuxembourgCities::usage = "LuxembourgCities contains coordinates for the 634 cities of Luxembourg.";
SaveImages::usage = "SaveImages is an option to TSPCCA that saves snapshots of the algorithm in CCAImages.";
TSPCCA::usage = "TSPCCA[pts] returns the TSP tour generated by the CCA method.";
TSPOrZweig::usage = "TSOrZweig[pts] returns the TSP tour generated by using the OrZweig improvement method, and starting with the CCA method.";
StartTour::usage = "StartTour is an option to TSPOrZweig that specifies the tour to be improved in the form of a permutation.";
CCAImages::usage = "CCAImages is the location of any saved images from TSPCCA.";
OZImages::usage = "OZImages is the location of any saved images from TSPOZ.";
MainPointStyle::usage = "MainPointStyle is an option to TSPCCA that sets the style of the points on the tour in the saved images.";
PointStyle::usage = "PointStyle is an option to TSPOrZweig that sets the style of the points in the saved images.";
InteriorPointStyle::usage = "InteriorPointStyle is an option to TSPCCA that sets the style of the interior points, those not yet on the tour, in the saved images.";

Begin["`Private`"];

angle=Compile[{{p,_Real,1},{q,_Real,1},{r,_Real,1}},ArcCos[(((r-q).(p-q))/(Sqrt[(r-q).(r-q) (p-q).(p-q)]))]];
EuclideanDistanceFcn=Compile[{{p,_Real,1},{q,_Real,1}},(Sqrt[(p-q).(p-q)])];
extend[x_]:=Append[x,x[[1]]];

TourCost[perm_, pts_] := (perm1=extend[perm];
cfcn = EuclideanDistanceFcn ;
Total[Map[cfcn[#[[1]],#[[2]]]&, Partition[pts[[perm1]], 2,1], {1}]]);

Options[TourPlot] ={PlotLabelDistanceQ->False,EdgeStyle-> {RGBColor[.5,0,0]},  PointStyle -> Automatic, PolygonStyle->Automatic, DistanceFunction->EuclideanDistance};

TourPlot[perm_, pts_, opts___] :=Module[{pr, sty, labQ},
(pr ={{ Min[First /@ pts],Max[First /@ pts]},{ Min[Last /@ pts],Max[Last /@ pts]}};
delpr = 0.08 {pr[[1,2]] - pr[[1,1]],pr[[2,2]] - pr[[2,1]]};
pr ={ {pr[[1,1]] - delpr[[1]],pr[[1,2]] + delpr[[1]]},{pr[[2,1]] - delpr[[2]],pr[[2,2]] +  delpr[[2]]}};  
{esty,labQ, psty, polysty} ={EdgeStyle,PlotLabelDistanceQ,  PointStyle, PolygonStyle} /. {opts} /. Options[TourPlot];
polysty = polysty /. {Automatic -> {RGBColor[1,1,.6]}, None->{}};
psty = psty /. Automatic -> {PointSize[If[Length[perm]>99,.005,.02]], RGBColor[0,0,.7]};
If[!ListQ[psty] , psty = {psty}];If[!ListQ[polysty] , polysty = {polysty}];
If[!ListQ[esty] , esty = {esty}];
Graphics[{If[polysty==={},{},Append[polysty, Polygon[pts[[perm]]]]],Append[esty,Line[extend[pts[[perm]]]]], Append[psty,Point /@ pts]},FilterRules[{opts}, First /@ Options[Graphics]],PlotLabel -> If[labQ,TourCost[perm,pts, opts], None],PlotRange->pr])] ;

Options[TSPOrZweig]={StartTour->Automatic,SaveImages->False,TracePrint->False,MaxIterations->Infinity};

Wrap[i_,n_] := Mod[i,n,1];

TSPOrZweig[pts_,opts___Rule]:=Module[{trQ,ans,startperm},{movQ,startperm,trQ}={SaveImages,StartTour,TracePrint}/.{opts}/.Options[TSPOrZweig];
OZImages={};
startperm=startperm/.Automatic:>TSPCCA[pts,opts][[2]];
cfcn=EuclideanDistanceFcn;
ans=fixOrZweig[startperm,pts,opts];
{TourCost[ans,pts], ans}];

Options[fixOrZweig]={TraceMovie->False,TracePrint->False,MaxIterations->Infinity};

fixOrZweig[perm_,pts_,opts___Rule]:=Module[{d,dd,dT,h,hpre,movQ,trQ,cfcn,n=Length[perm],count=0},{movQ,trQ,maxiter}={SaveImages,TracePrint,MaxIterations}/.{opts}/.Options[fixOrZweig];
cfcn=EuclideanDistanceFcn;
If[trQ,Print["Getting Delaunay triangulation"]];
dT=Last/@ComputationalGeometry`DelaunayTriangulation[pts];
If[trQ,Print["Delaunay triangulation done"]];
d[i_,j_]:=cfcn[pts[[i]],pts[[j]]];
Do[h[perm[[i]]]=perm[[Wrap[i+1,n]]];
hpre[perm[[i]]]=perm[[Wrap[i-1,n]]],{i,n}];
OrZweig3Pass[p_]:=Module[{i,j,movedata},count++;
movedata={};
If[movQ,AppendTo[OZImages, TourPlot[NestList[h,1,n-1],pts,opts]]];
If[trQ,Print[StringForm["OrZweig pass number ``; cost = ``.",count,TourCost[NestList[h,1,n-1],pts,opts]]]];
Do[bestsofar=0;
(*try 3*)start=h[i];next=h[start];last=h[next];ii=h[last];
fixedcost=d[i,start]+d[last,ii]-d[i,ii];
nbrstotry=Union[dT[[start]],dT[[last]]];
tt=Table[j=nbrstotry[[jj]];
If[j==start||j==next||j==i||j==last,-fixedcost-1,d[j,h[j]]-d[j,last]-d[start,h[j]]],{jj,1,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j3=nbrstotry[[jj]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j3,start,i,last,next},{last,h[j3],ii,next,start}}]];
(*try 3 before*)tt=Table[j=hpre[nbrstotry[[jj]]];
If[j==start||j==next||j==i||j==last,-fixedcost-1,d[j,h[j]]-d[j,last]-d[start,h[j]]],{jj,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j3=hpre[nbrstotry[[jj]]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j3,start,i,last,next},{last,h[j3],ii,next,start}}]];
(*try 3 reversed*)tt=Table[j=nbrstotry[[jj]];
If[j==start||j==next||j==i||j==last,-fixedcost-1,d[j,h[j]]-d[j,start]-d[last,h[j]]],{jj,1,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j3=nbrstotry[[jj]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j3,i,last},{start,ii,h[j3]}}]];
(*try 3 reversed before*)tt=Table[j=hpre[nbrstotry[[jj]]];
If[j==start||j==next||j==i||j==last,-fixedcost-1,d[j,h[j]]-d[j,start]-d[last,h[j]]],{jj,1,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j3=hpre[nbrstotry[[jj]]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j3,i,last},{start,ii,h[j3]}}]];
(*try 2*)fixedcost=d[i,start]+d[next,last]-d[i,last];
nbrstotry=Union[dT[[start]],dT[[next]]];
tt=Table[j=nbrstotry[[jj]];
If[j==start||j==next||j==i,-fixedcost-1,d[j,h[j]]-d[j,next]-d[start,h[j]]],{jj,1,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j2=nbrstotry[[jj]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j2,start,i,next},{next,h[j2],last,start}}]];
(*try 2 before*)tt=Table[j=hpre[nbrstotry[[jj]]];
If[j==start||j==next||j==i,-fixedcost-1,d[j,h[j]]-d[j,next]-d[start,h[j]]],{jj,1,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j2=hpre[nbrstotry[[jj]]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j2,start,i,next},{next,h[j2],last,start}}]];
(*try 2 reversed*)tt=Table[j=nbrstotry[[jj]];
If[j==start||j==next||j==i,-fixedcost-1,d[j,h[j]]-d[j,start]-d[next,h[j]]],{jj,1,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j2=nbrstotry[[jj]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j2,i,next},{start,last,h[j2]}}]];
(*try 2 reversed before*)tt=Table[j=hpre[nbrstotry[[jj]]];
If[j==start||j==next||j==i,-fixedcost-1,d[j,h[j]]-d[j,start]-d[next,h[j]]],{jj,Length[nbrstotry]}];
jj=Ordering[tt,-1][[1]];j2=hpre[nbrstotry[[jj]]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j2,i,next},{start,last,h[j2]}}]];
(*try 1*)fixedcost=d[i,start]+d[start,next]-d[i,next];
tt=Table[j=dT[[start,jj]];
If[j==start||j==i,-fixedcost-1,d[j,h[j]]-d[j,start]-d[start,h[j]]],{jj,Length[dT[[start]]]}];
jj=Ordering[tt,-1][[1]];j1=dT[[start,jj]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,bestsofar=bb;
movedata=Transpose[{{j1,start,i},{start,h[j1],next}}]];
(*try 1 before*)tt=Table[j=hpre[dT[[start,jj]]];
If[j==start||j==i,-fixedcost-1,d[j,h[j]]-d[j,start]-d[start,h[j]]],{jj,Length[dT[[start]]]}];
jj=Ordering[tt,-1][[1]];j1=hpre[dT[[start,jj]]];
If[(bb=fixedcost+tt[[jj]])>0&&bb>bestsofar,movedata=Transpose[{{j1,start,i},{start,h[j1],next}}]];
Scan[(h[#[[1]]]=#[[2]];hpre[#[[2]]]=#[[1]])&,movedata],{i,n}];
NestList[h,1,n-1]];
FixedPoint[OrZweig3Pass,perm,maxiter]];

Options[TSPCCA] = {SaveImages->False, TraceStep->1, MainPointStyle->{Red,PointSize[0.02]}, InteriorPointStyle ->{Blue,PointSize[.02]}};
TSPCCA[pts_, opts___] := Module[{n=Length[pts],d, ans,h, cfcn},
{movQ,step, psty, ipsty}={SaveImages, TraceStep,MainPointStyle, InteriorPointStyle} /. {opts} /. Options[TSPCCA];
If[!ListQ[psty], psty = {psty}];If[!ListQ[ipsty], ipsty = {ipsty}];
CCAImages={};
cfcn = EuclideanDistanceFcn;
dd=Outer[cfcn,pts,pts,1];
 d[i_Integer,j_Integer] := cfcn[pts[[i]],pts[[j]]];
ans=ConvexHull[pts];
done=Length[ans];
unp=n-done; unplaced = Complement[Range[n], ans];
If[unp==0, Return[ans]];
(* first pass*) 
Scan[(intpt=#;
tt=Table[d[ans[[i]], intpt]+d[ans[[i+1/. done+1->1]], intpt]-d[ans[[i]], ans[[i+1/. done+1->1]]] ,
{i, Length[ans]}];
pos=Ordering[tt,1][[1]];
h[intpt]=pos;
hangle[intpt]=angle[pts[[ans[[pos]]]], pts[[intpt]],pts[[ans[[pos+1/. done+1->1]]]]] )&,unplaced];

If[movQ ,AppendTo[CCAImages,Graphics[{ Line[pts[[extend[ans]]]],Append[psty,Point /@ pts],Append[ipsty, Point /@ pts[[unplaced]]],
Table[pts[[u=unplaced[[i]]]];
{Line[{pts[[ ans[[h[u]+1/. Length[ans]+1->1]]]],pts[[u]],pts[[ ans[[h[u]]]]]}]}, {i,Length[unplaced]} ]}, Sequence@@FilterRules[{opts},First /@ Options@Graphics], PlotRange->All]]];

tt=Map[hangle ,unplaced];
pos=Ordering[tt,-1][[1]];
best =  unplaced[[pos]];
insertafter=h[best];
ans = Insert[ans, best,  insertafter+1  ];done++;
unplaced =Delete[unplaced, pos];
(* now proceed by updates *) 

Do[
(* renumber because of added best *)
Scan[If[h[#] ≥insertafter+1 , h[#]++]&, unplaced];

(* update the bests; First update those whose edge has disappeared *) 
 Scan[(intpt=#;
If[h[intpt] ==insertafter ,
tt=Table[
d[aa=ans[[i]],intpt]+d[aaa=ans[[i+1/. done+1->1]], intpt]-d[aa, aaa] ,
{i, done}];
pos=Ordering[tt,1][[1]];
h[intpt] =pos;
hangle[intpt] = angle[pts[[ans[[pos]]]], pts[[intpt]],pts[[ans[[pos+1/. done+1->1]]]]] ])&, unplaced];

(* now the rest by just two checks *) 
Scan[(intpt=#;
If[h[intpt]≠insertafter,
If[(d[ans[[insertafter]],intpt]+d[ans[[insertafter+1/. done+1->1]],intpt]-d[ans[[insertafter+1/. done+1->1]],ans[[insertafter]]] )<
(d[ans[[h[intpt]]],intpt]+d[ans[[h[intpt]+1/. done+1->1]],intpt]-d[ans[[h[intpt]]],ans[[h[intpt]+1/. done+1->1]]] ),   
h[intpt] = insertafter;
 hangle[intpt] = angle[pts[[ans[[insertafter]]]],pts[[intpt]],pts[[ans[[insertafter+1/.done+1->1]]]]]];
If[(d[ans[[insertafter+1]],intpt]+d[ans[[insertafter+2/. done+1->1]],intpt]-d[ans[[insertafter+2/. done+1->1]],ans[[insertafter+1]]] )<
(d[ans[[h[intpt]]],intpt]+d[ans[[h[intpt]+1/. done+1->1]],intpt]-d[ans[[h[intpt]]],ans[[h[intpt]+1/. done+1->1]]] ),  
 h[intpt] = insertafter+1;
 hangle[intpt] = angle[pts[[ans[[insertafter+1]]]],pts[[intpt]],pts[[ans[[insertafter+2/.done+1->1]]]]]]])&, unplaced];

If[movQ && Mod[k,step]==0, AppendTo[CCAImages,Graphics[{ Line[pts[[extend[ans]]]],Append[psty, Point /@ pts],Append[ipsty, Point /@ pts[[unplaced]] ],
Table[u=unplaced[[i]];
Line[{pts[[ ans[[h[u]+1/. Length[ans]+1->1]]]],pts[[u]],pts[[ ans[[h[u]]]]]}], {i,Length[unplaced]} ]}, Sequence@@FilterRules[{opts},First /@ Options[Graphics]], PlotRange->All]]];

pos=Ordering[Map[hangle,unplaced],-1][[1]];
best = unplaced[[pos]];
insertafter = h[best];
ans = Insert[ans, best,  insertafter+1];done++;
unplaced =Delete[unplaced, pos],
 {k,  2,unp}]; 

If[movQ,AppendTo[CCAImages,Graphics[{Line[pts[[extend[ans]]]],Append[psty, Point /@ pts]},Sequence@@FilterRules[{opts},First /@ Options@Graphics], PlotRange->All]]];
 {TourCost[ans,pts], ans}];


Options[FractalTurtle]={StartPosition->{0,0},StartDirection->{1,0},TurtleStep->1,TerminalSubstitution->None,PlotStyle->Thickness[0.01]};

FractalTurtle[r_,s_String,depths_List,angle_,opts___]:=GraphicsGrid[Map[FractalTurtle[r,s,#1,angle,opts]&,depths,{Depth[depths]-1}]];

FractalTurtle[rewrite_,start_String,depth_Integer,angle_,opts___]:=Module[{turtle,s,dir,scale,i=1,rotateleft,rotateright,stack,gg,ang= N[angle Degree]},
inds={1};
{startingPt,dir,ts,term,sty}={StartPosition,StartDirection,TurtleStep,TerminalSubstitution,PlotStyle}/.{opts}/.Options[FractalTurtle];
stack={{startingPt,dir}};
{rotleft, rotright}=RotationTransform /@({1,-1} ang);
If[!ListQ[sty],sty={sty}/.{Automatic}->{}];
s=Nest[StringReplace[#,rewrite]&,start,depth];
If[term=!=None,s=StringReplace[s,term]];
s=Characters[s];

TurtlePath=Reap[Sow[lastpt=startingPt];
Do[Which[
c=="+",dir=rotleft[dir],
c=="-",dir=rotright[dir],
c=="F", i++;Sow[lastpt+=ts dir],
c=="B", i++;Sow[lastpt-=ts dir],
c=="i",{rotleft,rotright}={rotright,rotleft},
c=="[",(stack=Prepend[stack,{lastpt,dir}]),
c=="]",(i++;dir=stack[[1,2]];Sow[lastpt=stack[[1,1]]];stack=Rest[stack];inds=Append[inds,i]) ],
 {c, s}]][[2,1]];
gg=Graphics[If[inds=={1},{Append[sty,Line[TurtlePath]]},TurtlePath=(TurtlePath[[Range[#[[1]],#[[2]]-1]]]&)/@Partition[inds,2,1];
Join[sty,Line/@TurtlePath]],
Sequence@@FilterRules[{opts},First/@Options[Graphics]],PlotRange->All];
{{x0,x1},{y0,y1}}=PlotRange[gg];
Show[gg,Sequence@@FilterRules[{opts},First/@Options[Graphics]],PlotRange->{{x0,x1}+{-0.1,0.1} (x1-x0),{y0,y1}+{-0.1,0.1} (y1-y0)},Frame->True,FrameTicks->None]];

position[{x_,y_},k_Integer]:=Which[x<0.5&&y<0.5,Mod[0.875+(1/4) position[{1-2 x,1-2 y},k-1],1],x<0.5&&y≥0.5,0.125+(1/4) position[{2 y-1,1-2 x},k-1],x≥0.5&&y≥0.5,0.375+(1/4) position[{2 x-1,2 y-1},k-1],True,0.625+(1/4) position[{1-2 y,2 x-1},k-1]]
position[{x_,y_},-1]:=1

tspSF[pointList_,k_Integer]:=First[Thread[Sort[({#1,position[#1,k]}&)/@pointList,#1[[2]]<#2[[2]]&]]];

Options[TSPSpaceFillingCurve]={CurveDepth->10};

TSPSpaceFillingCurve[pts_,opts___]:=Module[{ans=dep,trQ},{dep}={CurveDepth}/.{opts}/.Options[TSPSpaceFillingCurve];
tour=tspSF[pts,dep];
ans=Flatten[Position[pts,#,{1},1]&/@tour];
{TourCost[ans, pts], ans}];

ShowLabeledPoints[pts_]:=Graphics[{{AbsolutePointSize[16],({RGBColor@@RandomReal[{.4,1}, {13}],Point[#]}&)/@pts},MapIndexed[Text[#2[[1]],#1+{.005,0}]&,pts]},BaseStyle->{"Times-Bold",12},PlotRange->{{-0.03,1.03},{-0.03,1.03}}]

LuxembourgCities={{6.0330556`,49.4608333`},{6.3658333`,49.4716667`},{6.079444400000001`,49.4744444`},{6.0422222`,49.4758333`},{6.0875`,49.4805556`},{6.0977778`,49.4847222`},{6.3230556`,49.485277800000006`},{6.2916666999999995`,49.4869444`},{6.3516667`,49.4886111`},{6.0397222`,49.489166700000006`},{6.0925`,49.491111100000005`},{6.0694444`,49.492777800000006`},{5.9805556`,49.4958333`},{6.3527778`,49.5013889`},{6.2811111`,49.505`},{6.3163889`,49.5052778`},{6.0127778`,49.5063889`},{6.1505556`,49.506666700000004`},{6.2875000000000005`,49.5075`},{6.0561111`,49.5091667`},{5.9436111`,49.510277800000004`},{6.2572222`,49.5105556`},{5.8738889`,49.5111111`},{6.356944400000001`,49.5116667`},{5.9294444`,49.5127778`},{5.896111100000001`,49.513611100000006`},{6.1916667`,49.515`},{5.8500000000000005`,49.5166667`},{6.1666666999999995`,49.5166667`},{6.065`,49.5169444`},{6.1027778`,49.5186111`},{6.078333300000001`,49.5197222`},{6.2983333`,49.52`},{6.1866667`,49.5208333`},{6.2247222`,49.52277780000001`},{6.3422222`,49.523888899999996`},{5.8913889`,49.5241667`},{5.9661111`,49.5241667`},{6.129722200000001`,49.5244444`},{5.8375`,49.525`},{6.0422222`,49.525`},{5.9405556`,49.525555600000004`},{6.3538889`,49.5280556`},{6.010833300000001`,49.5294444`},{6.1202778`,49.53027780000001`},{6.355`,49.5308333`},{5.8472222`,49.531111100000004`},{6.2483333000000005`,49.5325`},{6.3552778`,49.5325`},{5.988333300000001`,49.5330556`},{5.9`,49.5333333`},{6.3166667`,49.5333333`},{6.0808333`,49.5336111`},{6.146944400000001`,49.5355556`},{5.893055599999999`,49.5361111`},{6.0294444`,49.5363889`},{6.2841667`,49.5380556`},{6.1291667`,49.540277800000005`},{6.2008333`,49.5408333`},{6.259722200000001`,49.5408333`},{6.0216667`,49.5413889`},{6.15`,49.5422222`},{6.1377778`,49.5444444`},{6.327500000000001`,49.5444444`},{6.3669444`,49.545`},{5.840833300000001`,49.5463889`},{5.8563889`,49.5463889`},{5.9288889000000005`,49.5480556`},{6.2091667`,49.5486111`},{6.016944400000001`,49.5488889`},{6.317222200000001`,49.5488889`},{6.0002778`,49.5494444`},{6.3158333`,49.5527778`},{6.3291667`,49.5538889`},{6.2875000000000005`,49.555`},{5.8805556`,49.5583333`},{5.9805556`,49.5588889`},{6.112222200000001`,49.561111100000005`},{6.2216667`,49.5619444`},{6.0088889`,49.5625`},{6.1538889`,49.562777800000006`},{6.364444400000001`,49.562777800000006`},{6.1636111`,49.565`},{5.8866667`,49.5658333`},{5.9333333`,49.566666700000006`},{6.1166667`,49.566666700000006`},{5.9102778`,49.5675`},{6.285`,49.5677778`},{6.1513889`,49.5680556`},{6.0652778`,49.5683333`},{6.2805556`,49.5708333`},{6.248611100000001`,49.572777800000004`},{6.2755556`,49.574444400000004`},{6.0347222`,49.5747222`},{5.9838889`,49.5758333`},{5.9108333`,49.5775`},{6.0588889`,49.5783333`},{5.9669444`,49.5813889`},{6.2266667`,49.581944400000005`},{5.9563889`,49.5825`},{6.3591667`,49.5838889`},{6.1736111000000005`,49.584166700000004`},{6.2555556`,49.58527780000001`},{6.1230556`,49.5855556`},{5.9833333`,49.5883333`},{6.106944400000001`,49.5894444`},{6.3161111000000005`,49.59`},{6.15`,49.5944444`},{6.26`,49.5963889`},{5.8758333`,49.5966667`},{6.3680556`,49.5986111`},{6.3877778`,49.599722199999995`},{6.15`,49.6`},{6.1666666999999995`,49.6`},{6.25`,49.6`},{5.948333300000001`,49.6022222`},{6.1241667`,49.6025`},{6.0955556`,49.6033333`},{5.9008333`,49.6036111`},{6.2588889`,49.6058333`},{6.168611100000001`,49.6069444`},{6.3258333`,49.6069444`},{5.9322222`,49.607222199999995`},{6.4058333`,49.6083333`},{6.05`,49.6111111`},{6.1361111`,49.6113889`},{6.13`,49.6116667`},{6.2188889`,49.6133333`},{5.9902778`,49.6163889`},{6.1566667`,49.6163889`},{5.9525`,49.6166667`},{6.1333333`,49.6166667`},{6.1666666999999995`,49.6166667`},{6.2166667`,49.6166667`},{6.2333333`,49.6166667`},{6.2666667`,49.6166667`},{6.3938889`,49.6172222`},{6.3544444`,49.6191667`},{6.24`,49.6194444`},{6.073333300000001`,49.6205556`},{6.2686111`,49.6205556`},{6.1216667`,49.6208333`},{6.1077778`,49.6227778`},{6.1363889`,49.623611100000005`},{6.1494444`,49.6238889`},{6.2027778`,49.6238889`},{6.4216667`,49.6244444`},{6.3369444`,49.6263889`},{6.0233333`,49.6275`},{6.1044444`,49.6280556`},{6.2780556`,49.6286111`},{6.1319444`,49.6288889`},{6.2675`,49.629166700000006`},{6.1391667`,49.629722199999996`},{5.8913889`,49.6308333`},{5.9177778`,49.6313889`},{6.4036111`,49.6313889`},{6.1191667`,49.631666700000004`},{6.220833300000001`,49.6325`},{6.2`,49.6333333`},{6.3558333000000005`,49.6344444`},{6.2394444`,49.6419444`},{5.9844444`,49.644444400000005`},{5.9908333`,49.645`},{5.9163889`,49.6463889`},{6.4005556`,49.646666700000004`},{6.26`,49.6475`},{6.1283333`,49.6491667`},{5.9316667`,49.6494444`},{6.05`,49.65`},{6.235`,49.6508333`},{6.3036111`,49.6508333`},{6.1413889`,49.6527778`},{6.2411111`,49.653611100000006`},{6.4344444`,49.6555556`},{6.049722200000001`,49.6566667`},{6.1275`,49.6569444`},{6.2336111`,49.6569444`},{6.0002778`,49.6572222`},{6.0822222`,49.6583333`},{6.1372222`,49.6583333`},{6.3647222`,49.6583333`},{5.9816667`,49.6602778`},{5.9191667`,49.6613889`},{6.3436111`,49.661666700000005`},{6.3027778`,49.6625`},{6.0730556`,49.6644444`},{6.4166666999999995`,49.6666667`},{6.0358333`,49.6683333`},{6.3302778`,49.6683333`},{6.1422222`,49.6686111`},{5.9652778`,49.669722199999995`},{5.95`,49.67`},{6.4008333`,49.673333299999996`},{6.3205556`,49.6747222`},{6.441944400000001`,49.6747222`},{6.0088889`,49.6752778`},{6.2472222`,49.6755556`},{6.3155556`,49.6761111`},{6.1238889`,49.676944400000004`},{6.3594444`,49.6777778`},{6.13`,49.680277800000006`},{6.2891667`,49.682500000000005`},{6.1416667`,49.6830556`},{5.9333333`,49.6833333`},{5.95`,49.6833333`},{6.3500000000000005`,49.6833333`},{5.8786111000000005`,49.6855556`},{6.1852778`,49.6866667`},{6.1436111`,49.6872222`},{6.3655555999999995`,49.687777800000006`},{5.9147222`,49.6886111`},{6.2483333000000005`,49.6888889`},{6.0591667`,49.6911111`},{6.3883333`,49.6913889`},{6.0022222`,49.691944400000004`},{6.442222200000001`,49.6938889`},{6.0694444`,49.6944444`},{6.1425`,49.6947222`},{5.870555599999999`,49.69527780000001`},{5.9202778`,49.6961111`},{6.4813889`,49.6961111`},{6.1316667`,49.6966667`},{6.1705556`,49.6972222`},{6.1975`,49.6975`},{6.2197222000000005`,49.697777800000004`},{5.9`,49.7`},{5.9833333`,49.7`},{6.1166667`,49.7`},{6.283333300000001`,49.7`},{6.4333333`,49.7`},{5.9672222`,49.701111100000006`},{6.0188889`,49.7013889`},{5.9163889`,49.701666700000004`},{6.0433333000000005`,49.7025`},{6.3747222`,49.70277780000001`},{6.4263889`,49.70277780000001`},{6.3405556`,49.7066667`},{6.2530556`,49.7072222`},{5.988333300000001`,49.709722199999995`},{6.0616667`,49.71`},{6.5002778`,49.71`},{6.3105556`,49.711388899999996`},{6.050833300000001`,49.713055600000004`},{6.2166667`,49.7155556`},{6.1336111`,49.7158333`},{6.4363889`,49.716111100000006`},{6.49`,49.7163889`},{6.1333333`,49.716666700000005`},{6.1833333`,49.716666700000005`},{6.2166667`,49.716666700000005`},{6.3666667`,49.716666700000005`},{5.95`,49.7175`},{6.1202778`,49.7175`},{6.0102778`,49.71777780000001`},{6.355`,49.71777780000001`},{6.0922222`,49.718888899999996`},{6.2`,49.7197222`},{5.9072222000000005`,49.722500000000004`},{5.9275`,49.7227778`},{6.3025`,49.7233333`},{6.3425`,49.7236111`},{5.9177778`,49.724722199999995`},{5.9644444000000005`,49.7255556`},{5.8411111`,49.726111100000004`},{6.1169444`,49.726388899999996`},{5.9863889`,49.7272222`},{6.3938889`,49.7272222`},{6.2102778`,49.7283333`},{6.231944400000001`,49.7288889`},{5.8438889`,49.7302778`},{5.8872222`,49.7305556`},{6.1333333`,49.7333333`},{6.2166667`,49.7333333`},{6.3194444`,49.7341667`},{6.3361111`,49.7344444`},{6.2872222`,49.7347222`},{5.8986111`,49.7361111`},{6.0230556`,49.7361111`},{6.2672222`,49.7383333`},{6.5`,49.7383333`},{6.345`,49.7388889`},{5.9705556`,49.739444400000004`},{5.8566667`,49.739722199999996`},{6.1872222`,49.739722199999996`},{6.1144444`,49.7416667`},{6.4277778`,49.7416667`},{6.0186111`,49.7419444`},{5.9261111`,49.7422222`},{6.48`,49.7422222`},{6.115`,49.7438889`},{6.1708333`,49.7441667`},{6.328333300000001`,49.7441667`},{5.971944400000001`,49.7461111`},{6.3636111`,49.7461111`},{6.465`,49.7461111`},{6.2602778`,49.746666700000006`},{6.106111100000001`,49.7488889`},{6.0830556`,49.7497222`},{5.8500000000000005`,49.75`},{6.`,49.75`},{6.2`,49.75`},{6.3061111`,49.750277800000006`},{6.3286111`,49.750277800000006`},{6.0083333`,49.7508333`},{5.9575000000000005`,49.7516667`},{6.5138889`,49.754166700000006`},{5.9122222`,49.7552778`},{6.1608333`,49.7563889`},{6.3533333`,49.75777780000001`},{6.4786111`,49.7580556`},{5.8269444`,49.7583333`},{6.1169444`,49.7583333`},{6.0411111`,49.7591667`},{6.2397222`,49.7591667`},{6.3877778`,49.7591667`},{6.1888889`,49.7616667`},{6.3033333`,49.761944400000004`},{6.0338889`,49.7625`},{6.2413889000000005`,49.7625`},{5.857222200000001`,49.7638889`},{5.890833300000001`,49.7655556`},{6.221944400000001`,49.7658333`},{5.8666667`,49.7666667`},{6.45`,49.7666667`},{6.4988889`,49.7672222`},{6.1166667`,49.768055600000004`},{5.82`,49.7686111`},{5.982222200000001`,49.7697222`},{6.1091667`,49.7702778`},{6.3041667`,49.7708333`},{6.3383333`,49.7730556`},{5.9280555999999995`,49.773611100000004`},{5.955555599999999`,49.7741667`},{6.3605556`,49.775`},{6.0155556`,49.775277800000005`},{6.5152778`,49.7763889`},{6.2211111`,49.7769444`},{6.1505556`,49.7775`},{6.4722222`,49.7775`},{6.499444400000001`,49.7777778`},{5.8950000000000005`,49.7783333`},{6.1166667`,49.7788889`},{6.4413889`,49.7788889`},{5.8094444`,49.779722199999995`},{5.9352778`,49.779722199999995`},{6.2736111`,49.781111100000004`},{5.9044444`,49.7838889`},{6.3108333000000005`,49.7847222`},{6.0961111`,49.786666700000005`},{6.174722200000001`,49.7869444`},{6.0694444`,49.7875`},{6.2866667`,49.788888899999996`},{5.8577778`,49.7891667`},{5.839722200000001`,49.7894444`},{6.3883333`,49.79`},{5.9347222`,49.7911111`},{6.1327778`,49.7919444`},{5.975833300000001`,49.7922222`},{5.8216667`,49.7944444`},{5.9411111000000005`,49.79527780000001`},{6.1555556`,49.7966667`},{5.9538889`,49.7972222`},{6.1591667`,49.797777800000006`},{6.5041667`,49.797777800000006`},{5.8352778`,49.7986111`},{6.0861111`,49.7994444`},{5.8666667`,49.800000000000004`},{6.1000000000000005`,49.800000000000004`},{5.9391666999999995`,49.801666700000006`},{6.2183333`,49.801944400000004`},{6.`,49.8030556`},{6.2538889`,49.8041667`},{6.4222222`,49.8055556`},{5.7916666999999995`,49.8072222`},{5.8666667`,49.81`},{6.0972222`,49.8102778`},{5.918611100000001`,49.8105556`},{6.4783333`,49.8113889`},{5.765833300000001`,49.8116667`},{6.2825`,49.8125`},{6.0891667`,49.8136111`},{6.3502778`,49.8136111`},{5.8747222`,49.8141667`},{5.8666667`,49.816666700000006`},{5.95`,49.816666700000006`},{6.1166667`,49.816666700000006`},{6.25`,49.816666700000006`},{6.3`,49.816666700000006`},{6.0880556`,49.816944400000004`},{6.0202778`,49.818611100000005`},{5.8558333000000005`,49.8222222`},{5.8883333`,49.8230556`},{5.7511111`,49.825`},{6.0913889`,49.8269444`},{5.9358333000000005`,49.827222199999994`},{5.9672222`,49.82777780000001`},{5.7647222000000005`,49.8286111`},{6.2227778`,49.8294444`},{6.1719444`,49.83`},{5.8544444`,49.830555600000004`},{6.0986111`,49.830555600000004`},{5.845`,49.8308333`},{6.0930556`,49.831944400000005`},{6.0166667`,49.8333333`},{6.1000000000000005`,49.8333333`},{6.1833333`,49.8333333`},{6.3827778`,49.8333333`},{6.0075`,49.8338889`},{5.7427778`,49.834722199999995`},{6.3313889`,49.835`},{6.2916666999999995`,49.8358333`},{5.7891667`,49.836111100000004`},{5.9063889`,49.8366667`},{5.8402778`,49.838055600000004`},{6.2041667`,49.8430556`},{6.268055599999999`,49.843611100000004`},{6.2497222`,49.8444444`},{6.1041666999999995`,49.847500000000004`},{6.0355555999999995`,49.8480556`},{6.1166667`,49.85`},{5.9013889`,49.85027780000001`},{5.7933333000000005`,49.8516667`},{6.134722200000001`,49.8519444`},{5.9158333`,49.8530556`},{6.1872222`,49.8530556`},{6.3191667`,49.8536111`},{6.095`,49.8544444`},{5.9036111`,49.8555556`},{6.0472222`,49.8555556`},{5.8805556`,49.857222199999995`},{5.825`,49.8575`},{5.9613889`,49.8591667`},{5.8511111`,49.8594444`},{6.2880556`,49.860277800000006`},{5.8438889`,49.8613889`},{6.1147222`,49.864722199999996`},{5.8333333000000005`,49.8666667`},{6.1833333`,49.8666667`},{6.2166667`,49.8666667`},{6.2333333`,49.8666667`},{5.7733333`,49.8669444`},{6.1825`,49.8669444`},{6.1558333`,49.867777800000006`},{6.2394444`,49.867777800000006`},{6.2677778`,49.8686111`},{5.9030556`,49.8705556`},{5.9725`,49.871944400000004`},{5.9311111`,49.8730556`},{6.2180556`,49.8766667`},{5.8872222`,49.8775`},{6.221944400000001`,49.8802778`},{6.0988889`,49.8830556`},{5.9`,49.8833333`},{6.1666666999999995`,49.8833333`},{6.2`,49.8833333`},{6.2333333`,49.8833333`},{6.2580556`,49.8838889`},{5.9366667`,49.8861111`},{5.8163889`,49.8877778`},{6.0677778`,49.8880556`},{5.9788889`,49.8888889`},{6.1652778`,49.8919444`},{6.044722200000001`,49.8936111`},{6.1636111`,49.894444400000005`},{6.1833333`,49.8975`},{5.8202778`,49.8983333`},{6.2052778`,49.898888899999996`},{5.8127778`,49.8991667`},{5.9`,49.9`},{5.95`,49.9`},{6.05`,49.9`},{6.0919444`,49.9`},{6.2091667`,49.9`},{5.8586111`,49.9008333`},{6.0372222`,49.9008333`},{5.884722200000001`,49.9016667`},{5.78`,49.9030556`},{6.135`,49.9033333`},{5.8880555999999995`,49.903611100000006`},{5.9622222`,49.903611100000006`},{5.890833300000001`,49.9094444`},{5.8775`,49.910000000000004`},{6.067222200000001`,49.910000000000004`},{5.9363889`,49.9113889`},{5.995555599999999`,49.9113889`},{6.140000000000001`,49.9125`},{6.1961111`,49.9155556`},{5.783333300000001`,49.9166667`},{6.`,49.9166667`},{6.011944400000001`,49.9169444`},{6.2277778`,49.9172222`},{6.0866667`,49.9186111`},{6.038333300000001`,49.921111100000005`},{5.9030556`,49.9213889`},{5.9683333`,49.9216667`},{5.8494444`,49.9219444`},{6.0541667`,49.9225`},{5.8786111000000005`,49.9230556`},{5.8722222`,49.923333299999996`},{5.9975000000000005`,49.923333299999996`},{6.1302778`,49.9244444`},{6.1736111000000005`,49.926666700000006`},{6.0372222`,49.930833299999996`},{5.79`,49.9313889`},{6.0636111`,49.9330556`},{5.8`,49.9333333`},{6.0666667`,49.9333333`},{6.2166667`,49.9333333`},{5.941944400000001`,49.9338889`},{6.2088889`,49.935`},{5.975833300000001`,49.9352778`},{6.1016667`,49.9369444`},{6.1561111`,49.9386111`},{5.8827778`,49.9413889`},{5.7858333`,49.944166700000004`},{6.0816666999999995`,49.9472222`},{5.9791666999999995`,49.9475`},{6.129444400000001`,49.9483333`},{5.8`,49.95`},{6.0666667`,49.95`},{5.7961111`,49.9505556`},{5.856111100000001`,49.952222199999994`},{6.0200000000000005`,49.95277780000001`},{6.106944400000001`,49.9547222`},{5.924722200000001`,49.9558333`},{5.8608333`,49.96027780000001`},{6.192222200000001`,49.96027780000001`},{6.143055599999999`,49.9608333`},{5.9816667`,49.9625`},{6.1241667`,49.9636111`},{5.8266667`,49.965`},{6.1677778`,49.967222199999995`},{5.8902778`,49.96777780000001`},{5.931944400000001`,49.968888899999996`},{5.9230556`,49.9691667`},{5.8372222`,49.97`},{6.009722200000001`,49.9711111`},{5.941944400000001`,49.9727778`},{6.0916667`,49.9730556`},{5.8438889`,49.974166700000005`},{6.0541667`,49.974722199999995`},{5.9486111`,49.9780556`},{5.9108333`,49.9797222`},{5.9061111`,49.981666700000005`},{6.0144444`,49.983611100000005`},{5.8725000000000005`,49.9844444`},{6.073333300000001`,49.985`},{6.1266666999999995`,49.985277800000006`},{5.9991667`,49.9888889`},{5.8575`,49.9905556`},{6.0130555999999995`,49.9944444`},{5.9488889`,49.9977778`},{5.9927778`,49.9994444`},{6.1455556`,50.0016667`},{6.1466667`,50.0072222`},{5.8522222`,50.010277800000004`},{6.0266667`,50.0105556`},{5.8436111`,50.0116667`},{6.0527778`,50.0122222`},{6.0913889`,50.0127778`},{5.964722200000001`,50.0133333`},{5.8897222000000005`,50.015`},{5.8608333`,50.0166667`},{6.0061111`,50.017777800000005`},{6.0933333`,50.017777800000005`},{5.9488889`,50.018055600000004`},{5.9680556`,50.019444400000005`},{5.9113889`,50.0213889`},{6.0666667`,50.0288889`},{6.0386111`,50.0336111`},{6.0713889`,50.0361111`},{5.8708333`,50.036666700000005`},{6.1311111`,50.036666700000005`},{5.9894444`,50.0383333`},{6.0797222`,50.0391667`},{6.0175`,50.0408333`},{5.8780556`,50.046111100000005`},{5.9041667`,50.046111100000005`},{5.9341667`,50.0463889`},{6.0747222`,50.051666700000006`},{5.9191667`,50.0533333`},{6.061944400000001`,50.0533333`},{6.0313889`,50.0547222`},{6.083611100000001`,50.055833299999996`},{5.8980556`,50.057777800000004`},{6.0375000000000005`,50.057777800000004`},{6.0663889`,50.0583333`},{5.941944400000001`,50.06`},{5.9558333`,50.0622222`},{6.0036111000000005`,50.062777800000006`},{5.8830556`,50.0644444`},{5.9638889`,50.0655556`},{6.0705556`,50.0694444`},{5.9780556`,50.07`},{6.0688889`,50.0752778`},{6.0466667`,50.0755556`},{5.9580556`,50.0788889`},{5.9755556`,50.08`},{5.9216667`,50.080555600000004`},{6.`,50.0833333`},{6.0600000000000005`,50.0833333`},{5.9925`,50.0838889`},{5.9566666999999995`,50.093611100000004`},{6.0591667`,50.0961111`},{6.0880556`,50.0961111`},{5.9730555999999995`,50.0972222`},{5.9975000000000005`,50.0994444`},{5.9233333`,50.099722199999995`},{6.1130556`,50.102777800000005`},{5.9461111`,50.1044444`},{6.0077778`,50.107222199999995`},{5.9233333`,50.1080556`},{5.9927778`,50.1175`},{5.9791666999999995`,50.1180556`},{6.0386111`,50.1188889`},{6.0833333000000005`,50.1191667`},{6.0002778`,50.1211111`},{6.0494444000000005`,50.123611100000005`},{6.0636111`,50.1241667`},{6.11`,50.1244444`},{6.0666667`,50.1333333`},{6.0191666999999995`,50.1336111`},{6.075`,50.1372222`},{6.0238889`,50.1405556`},{5.9838889`,50.1458333`},{6.0133333`,50.1491667`},{6.05`,50.15`},{6.0533333`,50.1555556`},{5.9786111`,50.1566667`},{6.1088889`,50.1608333`},{6.015000000000001`,50.1647222`},{6.0888889`,50.1655556`},{6.0252778`,50.1816667`}};


End[];EndPackage[];

The Recursive Turtle

Code for COA

Code For COA, top

Code For COA, bottom

.  The Literate Turtle

Nest[StringReplace[#,"F"->"F+F--F+F"]&,"F",3]

Options[FractalTurtleBasic]={PlotStyle->Thickness[0.01]};
FractalTurtleBasic[rewrite_,start_String,d_Integer,angle_,opts___]:=Module[
{dir={1,0},rotleft,rotright, sty, lastpt, chars, ang=N[angle Degree]},
sty=PlotStyle/.{opts}/.Options[FractalTurtleBasic];
If[!ListQ[sty], sty = {sty}];
{rotleft, rotright}=RotationTransform /@ ({-1,1} ang);
chars= Characters[Nest[StringReplace[#,rewrite]&,start,d]];
pts=Reap[Sow[lastpt={0,0}][[1]];
Do[Which[
c=="+",dir=rotleft[dir],
c=="-",dir=rotright[dir],
c=="F",Sow[lastpt+=dir],
c=="B",Sow[lastpt-=dir],
c=="i",{rotleft,rotright}={rotright,rotleft}],{c,chars}]][[2]];
Graphics[Append[sty, Line[pts]],Sequence@@FilterRules[{opts},Options[Graphics]],PlotRange->All]]

FractalTurtleBasic[r_,s_String,depths_List,angle_, opts___]:=GraphicsGrid[Map[FractalTurtleBasic[r,s,#,angle, opts]&,depths,{Depth[depths]-1}]]

FractalTurtleBasic["F"->"F-F++F-F","F++F++F",{{0,1,2},{3,4,5}},60]

FractalTurtleBasic["F"->"F+F--F+F","F++F++F",{{2,3,4}},60]

Grid[Partition[
Table[FractalTurtle["X"->"XX","X",i,90,
		StartDirection->{1,1},TurtleStep->(2^(-(i+1))),TerminalSubstitution->"X"->"F-F+",Frame->False,Axes->Automatic,PlotRange->{0,0.55}],{i,0,3}],2]]

.  Space-Filling Curves

Code for Figure

i=3;FractalTurtle["X"->"+iXiF-XFX-FiXi+","X",i,90,StartPosition->(({2,2})^(-(i+1))),TurtleStep->(2^(-i)),PlotRange->{{0,1},{0,1}},Ticks->{Range[0.25,1,0.25],Range[0.25,1,0.25]}]

n=6;
FractalTurtle["X"->"+iXiF-XFX-FiXi+","X",n,90,StartPosition->(({2,2})^(-(n+1))),TurtleStep->(2^(-n))];
Graphics[Line[Transpose[{Range[0,1-(4^(-n)),(4.^(-n))],First[Transpose[TurtlePath]]}]],Axes->Automatic,AspectRatio->0.6,AxesLabel->{"t","x(t)"}]

GraphicsGrid[Partition[Table[FractalTurtle["X"->"iXiXX++iXi++","X",n,90,TerminalSubstitution->{"X"->"F-F+"},StartDirection->(({1,1})/(Sqrt[2])),TurtleStep->(2^(-(n+(1/2)))),Axes->Automatic,Frame->False,Ticks->{Range[0,1,0.25],Range[0,1,0.25]},PlotRange->{0,1}],{n,0,5}],3]]

Row[Table[FractalTurtle["X"->"+iXi--X+XiXi-","X",n,90,TurtleStep->(2^(-(n+1))),
		TerminalSubstitution->("X" -> "+F-FF-F"), PlotRange -> {{0,1}, {0,1}}, Axes->Automatic, AxesStyle->GrayLevel[0.6],  Frame->False,Ticks->{Range[0,1,0.25],Range[0,1,0.25]}], {n,0,3}]]

n=7;
FractalTurtle["X"->"+iXiF-XFX-FiXi+","X",n,90,StartPosition->(({2,2})^(-(n+1))),TurtleStep->(2^(-n))];
Graphics3D[{Line[Flatten/@Transpose[{Range[0,1-(4^(-n)),(4.^(-n))],TurtlePath}]]},Axes->Automatic,AxesLabel->{"t","x","y"}, BoxRatios->{3,1,1}]

GraphicsGrid[Partition[Table[FractalTurtle["X"->"XF-F+F-XF+F+XF-F+F-X","F+XF+F+XF",n,90,
		TurtleStep->((2^(-(n+1)))/(Sqrt[2])),Frame->False,
		StartDirection->(({1,1})/(Sqrt[2])),StartPosition->{1-(2^(-n-1)),(2^(-n-2))} ,
		PlotRange->{{0,1},{0,1}}],{n,1,4}],2]]

GraphicsRow[Table[FractalTurtle["X"->"XFiXiFX+F+iXiFXFiXi-F-XFiXiFX","X",n,90,TurtleStep->(3^(-n)),
		StartPosition->(({3,3})^(-n))/2, Frame->False],{n,1,3}]]

base2Digits[t_]:=RealDigits[N[t,50],2,50,-1][[1]]
CantorMapping[t_]:=Module[{ones=Flatten[Position[base2Digits[t],1]]},ones={Select[ones,OddQ],Select[ones,EvenQ]};
Total/@{(2^(-(1/2) (ones[[1]]+1))),(2^(-((ones[[2]])/2)))}]
CantorMapping[1|1.]={0,1};

CantorImage[n_]:=Graphics[{Thickness[0.01],Line[CantorMapping/@Range[0.,1,1/n]]},Axes->None,Frame->True,PlotRange->{{0,1},{0,1}},PlotRangePadding->0.05,FrameTicks->Join[Array[Range[0,1,0.25]&,2],{None,None}]];

GraphicsGrid[Partition[Table[CantorImage[(2^i)],{i,2,7}],3]]

.  A Surprising Application

The CCA Method

SeedRandom[2];pts=RandomReal[{0,1},{20,2}];
TSPCCA[pts,SaveImages->True]

Manipulate[Show[CCAImages[[i]]],{i,1,Length[CCAImages],1}]

TSPOrZweig[pts,SaveImages->True ]

GraphicsRow[OZImages]

FindShortestTour[pts][[1]]

LuxTourCCA=TSPCCA[LuxembourgCities];
LuxTourCCA[[1]]

LuxTourCCAOZ=TSPOrZweig[LuxembourgCities,StartTour->LuxTourCCA[[2]]];
LuxTourCCAOZ[[1]]

Graphics[{{Lighter[Yellow],EdgeForm[Black],Polygon[LuxembourgCities[[Append[LuxTourCCAOZ[[2]],LuxTourCCAOZ[[2,1]]]]]]},
Point[LuxembourgCities[[LuxTourCCAOZ[[2]]]]]},Frame->True,PlotLabel->LuxTourCCAOZ[[1]]]

The Obsessive Traveling Salesman

SeedRandom[1];pts=RandomReal[{0,1},{30,2}];
Graphics[{EdgeForm[Thickness[0.002]],
FaceForm[RGBColor[1,1,.6]],Table[Disk[p,0.035], {p,pts}],MapIndexed[Text[#2[[1]],#1]&,pts]},Frame->True,FrameTicks->None,PlotRange->{{-0.1,1.1},{-0.1,1.1}},BaseStyle->Bold]

tourSF=TSPSpaceFillingCurve[pts]

Graphics[{Thickness[0.008],PointSize[0.03],Point[pts[[tourSF[[2]]]]],Line[pts[[Append[tourSF[[2]],tourSF[[2,1]]]]]]},Frame->True,PlotLabel->tourSF[[1]]]

tourSFOZ=TSPOrZweig[pts,StartTour -> tourSF[[2]]];
Graphics[{Thickness[0.008],PointSize[0.02],Point[pts[[tourSFOZ[[2]]]]],Line[pts[[Append[tourSFOZ[[2]],tourSFOZ[[2,1]]]]]]},Frame->True,PlotLabel->tourSFOZ[[1]]]

FindShortestTour[pts][[1]]

{xmin,xmax}=({Min[#],Max[#]}&)[First/@LuxembourgCities];
{ymin,ymax}=({Min[#],Max[#]}&)[Last/@LuxembourgCities];
pts=LuxembourgCities/.{x_,y_}:>{((x-xmin)/(xmax-xmin)),((y-ymin)/(ymax-ymin))};

{cost,tour}=TSPOrZweig[pts,StartTour->TSPSpaceFillingCurve[pts][[2]]];
cost

TourCost[tour,LuxembourgCities]

More Earth Data

CountryData["Luxembourg","Population"]

CountryData["Luxembourg","SchematicPolygon"]

(europe = Select[CountryData["Europe"], CountryData[#, "Population"]≥ 10000 &]) //Short

capitals=Table[CountryData[c,"CapitalCity"][[{1,3}]], {c,europe}];
capitals[[14]]

capitalLocs=(Reverse[CityData[#,"Coordinates"]]&)/@capitals;
capitalLocs[[14]]

tsp=FindShortestTour[capitalLocs]
tour=tsp[[2]];

Total[Norm/@Differences [capitalLocs[[Append[tour,tour[[1]]]]]]]

EuropeMap={EdgeForm[Thickness[0.001]],RGBColor[1,0.4,0.6],Table[CountryData[nation,"SchematicPolygon"],{nation,europe}]};
Graphics[{EuropeMap,{Thick,Line[capitalLocs[[Append[tour,tour[[1]]]]]]},{EdgeForm[Thickness[0.002]],White,(Disk[#,0.7]&)/@capitalLocs}},PlotRange->{{-28,43},{32,73}}]

SC[{lat_,lon_}]:=r {Cos[lon °] Cos[lat °],Sin[lon  °] Cos[lat  °],Sin[lat °]};
r=6378.7;
places=CountryData["Countries"];
centers=Map[CountryData[#,"CenterCoordinates"]&,places];
distfun[{lat1_,lon1_},{lat2_,lon2_}]:=VectorAngle[SC[{lat1,lon1}],SC[{lat2,lon2}]]r;

{dist,route}=FindShortestTour[centers,DistanceFunction->distfun];

surfaceCenters=Map[SC,centers[[route]]];
GreatCircleArc[{lat1_,lon1_},{lat2_,lon2_}]:=Module[{u=SC[{lat1,lon1}],v=SC[{lat2,lon2}],a},
a=VectorAngle[u,v];
Table[RotationTransform[θ,{u,v}][u],{θ,0,a,(a/(Ceiling[10 a]))}]]

tourLine=Apply[GreatCircleArc,Partition[centers[[route]],2,1],{1}];

Graphics3D[{Sphere[{0,0,0},0.99 r],Map[Line[Map[SC,CountryData[#,"SchematicCoordinates"],{2}]]&,places],{Red,Thick,Line[tourLine]},{Yellow,PointSize[Medium],Map[Tooltip[Point[SC[CountryData[#,"CenterCoordinates"]]],#]&,places]}},Boxed->False]

.  Trees, Mathematical and Botanical

n=4;
FractalTurtle["F"->"F[+F][-F]","FB",n,(180/13),StartDirection->{0,1}]

FractalTurtle["F"->"F[+F]F[-F]F","F",5,180/7,StartDirection->{0,1}]

FractalTurtle["F"->"FF+[+F-F-F]-[-F+F+F]","F",4,180/8,StartDirection->{0,1}]

n=3;
FractalTurtle[{"A"->"X+X+X+X+X+X+","Y"->"[F+F+F+F[---Y]+++++F++++++++F-F-F-F]","X"->"[F+F+F+F[---X-Y]+++++F++++++++F-F-F-F]"},"AAAA",n,15]