Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!usc!apple!sun-barr!newstop!sun!imagen!atari!portal!portal!cup.portal.com!Nagle
From: Nagle@cup.portal.com (John - Nagle)
Newsgroups: comp.graphics
Subject: Re: Request: Plotter pen vector optimization algorithm
Message-ID: <27800@cup.portal.com>
Date: 11 Mar 90 18:28:27 GMT
References: <1990Mar8.060653.14280@Octopus.COM>
Organization: The Portal System (TM)
Lines: 21


     It's been a long time since I did one of these.

     Usually, you have some source of vectors coming in that you want to
optimize.  You don't need to optimize the entire file, just a pool of
the next twenty or so vectors to be plotted.  On these, you use a
travelling-salesman type iterative improvement algorithm, based on whatever
metric you find useful.  If there's a CPU available that isn't doing anything
else, a reasonable way to do it is to keep the improvement algorithm running
constantly, steadily improving the path, and each time you need a vector,
get it from the beginning of the path in the pool as it currently stands.
Then read a new vector from the input source, tack it on to the end
of the current path, and restart the optimizer while the plotter does the
vector.  Thus, you're always optimizing a pool of modest size.  Note that
this background computation approach doesn't result in the pen taking the
identical path if you do the same plot twice, which may bother some people.

     For the purpose of optimization, never break a pen-down sequence into
parts.  

					John Nagle