# What programmable drawing tool(s) can solve how to fill a region with a path

I've recently become interested in computer numerical control (CNC), and have been considering using METAPOST in a CNC work-flow (using pstoedit to convert .pdf (or .mp) files to G-Code). The extant opensource computer aided manufacturing (CAM) programs all seem to have difficulties with efficiency and elegance (in the sense of scientific correctness) --- if you have specific successes w/ CAM Tools to mention, please note them in the comments.

What sort of functions / modules / programs, which, given a filled region, will create a continuous, as-smooth-as-possible (i.e., not made of line segments), spiraling path which will completely fill the area w/ a circular pen of a given size and a certain minimum overlap (and which can either start from the center of the region and move out, or work its way from the outside in)? Bonus points if it's also able to accommodate holes, more bonus points if it will create a sub-paths for efficiency.

Is this possible in METAPOST? if not, what other tool(s) should I be looking at in addition to g.kov's nifty Asymptote solution (which is a great start, but uses line segments and won't instantiate new sub-regions)?

-
> "If not, what other tool(s) should I be looking at?" Perhaps this is obvious, but anyway ... There are many NC program generation packages that do this sort of thing. It's generally called "area milling", or something like that. The toolpath patterns are usually either zig-zag (moving back and forth in straight lines) or some sort of spiral, as you describe. To write this sort of code yourself, you need good 2D computational geometry functions. The basic computations are things like intersecting curves, offsetting curves, finding distances to curves, and so on. I don't think Metapost would b –  bubba Jul 26 '13 at 10:02
I've been using / trying various opensource CAM tools, and have been put off by how difficult they are to control and how inefficient the resulting G-code is. Pstoedit should handle the conversion nicely. –  WillAdams Jul 26 '13 at 10:19
For those who're curious about CNC and 3D printing, there's a Digital Fabrication StackExchange site starting up --- it needs more committers w/ 200+ rep on other sites: area51.stackexchange.com/proposals/41850/… –  WillAdams Aug 20 '13 at 13:08

This is not a complete solution, but it can be used as a starter. In this example a struct Region is defined in asydef environment. It takes two paths, out and in and constructs a spiral path between them, which makes nTurns turns around the inner path. fillreg.tex:

\documentclass{article}
\usepackage{lmodern}
\usepackage{subcaption}
\usepackage[inline]{asymptote}
\usepackage[left=2cm,right=2cm]{geometry}
\begin{asydef}
import graph;
struct Region{
guide out;
guide in;
int nPoints, nTurns, n;
guide spiral;

void unwind(){
guide g; pair p,q,r; real t,s,u;
for(int i=0;i<nTurns-1;++i){
t=i/(nTurns-1);
s=(i+1)/(nTurns-1);
p=(1-t)*point(out,0)+t*point(in,0);
r=p;
g=g--r;
for(int j=1;j<n;++j){
p=(1-t)*point(out,(real)(j*size(out)/(n-1)))
+t*point(in,(real)(j*size(in)/(n-1)));
q=(1-s)*point(out,(real)(j*size(out)/(n-1)))
+s*point(in,(real)(j*size(in)/(n-1)));
u=j/(n-1);
r=(1-u)*p+u*q;
g=g--r;
}
}
spiral=g;
}

void operator init(guide out, guide in, int nPoints=20, int nTurns=10){
this.out=out;
this.in=in;
this.nPoints=nPoints;
this.nTurns=nTurns;
this.n=max(size(out),size(in))*nPoints;
unwind();
}
};

void draw(Region R, pen p=currentpen){
draw(R.out,p);
draw(R.in,p);
draw(R.spiral,p);
};
\end{asydef}

\begin{document}
%
\begin{figure}
\captionsetup[subfigure]{justification=centering}
\centering
\begin{subfigure}{0.49\textwidth}
\begin{asy}
size(200);
Region R=Region(
rotate(135)*box((-2,-2),(2,2)),shift(0.2,0.4)*scale(0.618,0.382)*unitcircle
,nPoints=80
,nTurns=8
);
draw(R, darkblue+2bp);
\end{asy}
\caption{$\mathrm{nTurns}=8$.}
\label{fig:1a}
\end{subfigure}
%
\begin{subfigure}{0.49\textwidth}
\begin{asy}
size(200);
Region R=Region(
rotate(135)*box((-2,-2),(2,2)),shift(0.2,0.4)*scale(0.618,0.382)*unitcircle
,nPoints=80
,nTurns=80
);
draw(R, orange+2bp);
\end{asy}
\caption{$\mathrm{nTurns}=80$.}
\label{fig:1b}
\end{subfigure}
%
\caption{A region filled with a spiral path.}
\end{figure}
%
%
\begin{figure}
\captionsetup[subfigure]{justification=centering}
\centering
\begin{subfigure}{0.3\textwidth}
\begin{asy}
size(200);
guide out=(50,-1)..(50,33)..(7,53)..(-11,2)..(-42,-36)..(28,-37)..cycle;
guide in=(34,0)..(24,23)..(16,6)..(2,-8)..(12,-13)..cycle;
Region R=Region(out,in,nPoints=80,nTurns=8);
draw(R, darkblue+2bp);
\end{asy}
\caption{$\mathrm{nTurns}=8$.}
\label{fig:2a}
\end{subfigure}
%
\begin{subfigure}{0.3\textwidth}
\begin{asy}
size(200);
guide out=(50,-1)..(50,33)..(7,53)..(-11,2)..(-42,-36)..(28,-37)..cycle;
guide in=(34,0)..(24,23)..(16,6)..(2,-8)..(12,-13)..cycle;
Region R=Region(out,in,nPoints=80,nTurns=40);
draw(R, orange+2bp);
\end{asy}
\caption{$\mathrm{nTurns}=40$.}
\label{fig:2b}
\end{subfigure}
%
\begin{subfigure}{0.3\textwidth}
\begin{asy}
size(200);
guide out=(50,-1)..(50,33)..(7,53)..(-11,2)..(-42,-36)..(28,-37)..cycle;
guide in=(34,0)..(24,23)..(16,6)..(2,-8)..(12,-13)..cycle;
Region R=Region(out,in,nPoints=80,nTurns=60);
draw(R, orange+2bp);
\end{asy}
\caption{$\mathrm{nTurns}=60$.}
\label{fig:3b}
\end{subfigure}
%
\caption{A region filled with a spiral path.}
\end{figure}
\end{document}


To process it with latexmk, create file latexmkrc:

sub asy {return system("asy '\$_[0]'");}

and run latexmk -pdf fillreg.tex.
@WillAdams: That was an intentional choice for simplicity. Procedure unwind() calculates a sequence of points r along a spiral and builds a path g of linear segments from them, but these points can be used for any kind of sophisticated optimisations. For example, you can collect all the r points in an array and then, say, build an optimized (shorter) sequence of cubic Bezier segments. –  g.kov Jul 26 '13 at 12:18