Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ukma!rutgers!att!cbnews!maddog
From: maddog@cbnews.ATT.COM (john.j.tupper)
Newsgroups: comp.graphics
Subject: Re: plotter optimizing algorithm
Message-ID: <5898@cbnews.ATT.COM>
Date: 25 Apr 89 15:09:40 GMT
References: <633@jc3b21.UUCP> <863@mplvax.EDU> <SARREL.89Apr24143841@dory.cis.ohio-state.edu>
Reply-To: maddog@cbnews.ATT.COM (john.j.tupper)
Distribution: na
Organization: AT&T Bell Laboratories
Lines: 36

In article <SARREL.89Apr24143841@dory.cis.ohio-state.edu> sarrel@dory.cis.ohio-state.edu (Marc Sarrel) writes:
>In article <863@mplvax.EDU> cdl@mplvax.EDU (Carl Lowenstein) writes:
>
>Discusses algorithm to minimize pen movement on a pen plotter, given a
>series of lines to be drawn.
>
>   In article <633@jc3b21.UUCP> crash@jc3b21.UUCP (Frank J. Edwards) writes:
>   >The point I'm at now is optimizing the vector list to minimize pen movement
>   >Right now, this is more of a programming obsession than a "practical"
>   >project (not that it was very "practical" to begin with :-).

I "solved" this problem a couple of years back. I found that buffering a large
number of lines and then drawing whichever line had the nearest endpoint
to the current pen position to work very well. Two things to look out for:
	1) It is more important to avoid pen changes. If your plotter has N
	   pens, draw your figure N times throwing away all comands that are
	   not drawn in the current color.

	2) When using transparency pens on either transparencies or hp glossy
	   paper, you should draw lines in only one direction (i.e. from
	   left to right and top to bottom, but not right to left or bottom
	   to top). If you draw them both directions, half the lines will
	   be ugly, ugly, ugly.

>It occurs to me that the famous "travelling salesman" problem, which
>we know to be NP-Complete, might reduce to the pen plotter
>optimization problem.

Yup, it does. Setup all the end points of all the lines as cities. Each
of these cities is connected to every other city with a straight road of
the proper length. Now add a city at the mid-point of each line. These
mid-point cities are connected only to the cities at the end-point of
their line. If you solve the plot optimization problem, you also solve
the traveling salemen problem.
-------------------------------------------------------------------------
sdlfk lsd sd				My real signature is illegible too.