Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!POSTGRES.BERKELEY.EDU!dillon
From: dillon@POSTGRES.BERKELEY.EDU (Matt Dillon)
Newsgroups: comp.sys.amiga.tech
Subject: Re: plotter optimizing algorithm
Message-ID: <8904242129.AA25480@postgres.Berkeley.EDU>
Date: 24 Apr 89 21:29:06 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Lines: 37


	Determining the most optimal plotter drawing sequence is almost the
traveling salesman problem!  Still, for a picture that is mainly vertical and
horizontal segments the easiest thing to do is something like this:

	* collect the horizontal and vertical segments into two different lists.

	* sort horizontal (H) list by y and sub-sort by x.  (i.e. a simple
	  numerical sort where 'y' is the msb and 'x' is the lsb).

	* sort the vertical (V) list by x and sub-sort by y.

	* starting at the top, draw the horizontal lines across reversing
	  direction each time.  I.e.  like a bi-directional printer.

	* starting at the nearest corner, draw the vertical lines in the same
	  manner... up then down then up ...

	* draw any diagonals (assumed to be only a few) that remain.

					-Matt

:I realize this is a somewhat open-ended request, but I'd like to poll the
:net.readers out there for "tips and techniques" in this area.
:
:My current strategy:
:
:1)	Sort the vectors in increasing (x,y) order of starting point
:	(the data is "struct { short sx, sy, ex, ey, flags }").
:	The "flags" member is for recording whether or not a particular
:	element has already been drawn.
:
:2)	Also generate and sort an array of pointers into the
:	start-point array, but sort these by end-point.
:	(This allows two methods of accessing the data; via start-point
:	or end-point order.)
:...