Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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)?

share|improve this question
    
> "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

1 Answer 1

enter image description here enter image description here

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]'");}
add_cus_dep("asy","eps",0,"asy");
add_cus_dep("asy","pdf",0,"asy");
add_cus_dep("asy","tex",0,"asy");

and run latexmk -pdf fillreg.tex.

share|improve this answer
    
Wow. I'm having a few difficulties w/ getting the code to run (to say nothing of puzzling out how to follow it), but did managed to get the first two (Figure 1a and 1b) to process --- the problem is, they're made up of short line segments, which is the sort of thing I'm trying to avoid. Looking at your code, it looks as if that was an intentional choice (for efficiency?). Worst case though is I'll just convert the entire path to curves, then simplify it. Thanks! –  WillAdams Jul 26 '13 at 11:55
    
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.