pete@Octopus.COM (Pete Holzmann) (03/08/90)
Does anybody know of references or working code to solve the following
problem?...
Problem: Given a set of mostly multiply-connected 2D line segments (think
of a piece of a street map, but with lots of dangling segments around the
edges, and extra or missing connections in various places in the middle),
I would like to produce the longest possible (preferably mostly-straight)
segment chains in order to plot the complete set of segments.
Basically, the goal is:
1) Avoid lifting the pen
2) Avoid sharp corners
It is more important to do a pretty good job quickly, than to do a perfect
job in a ridiculous amount of time.
Any ideas out there?
Thanks!
Pete
--
Peter Holzmann, Octopus Enterprises |(if you're a techie Christian & are
19611 La Mar Ct., Cupertino, CA 95014 |interested in helping w/ the Great
UUCP: {hpda,pyramid}!octopus!pete |Commission, email dsa-contact@octopus)
DSA office ans mach=408/996-7746;Work (SLP) voice=408/985-7400,FAX=408/985-0859falk@sun.Eng.Sun.COM (Ed Falk) (03/08/90)
In article <1990Mar8.060653.14280@Octopus.COM>, pete@Octopus.COM (Pete Holzmann) writes: > Does anybody know of references or working code to solve the following > problem?... > > Problem: Given a set of mostly multiply-connected 2D line segments (think > of a piece of a street map, but with lots of dangling segments around the > edges, and extra or missing connections in various places in the middle), > I would like to produce the longest possible (preferably mostly-straight) > segment chains in order to plot the complete set of segments. > > Basically, the goal is: > 1) Avoid lifting the pen > 2) Avoid sharp corners > > It is more important to do a pretty good job quickly, than to do a perfect > job in a ridiculous amount of time. The "classic" solution is the travelling saleman problem, which I believe is 2**n, but might be n**2, I can't remember. I once wrote a font editor that had a function to optimize any given character. The algorithm wasn't perfect, and would occasionally make things worse; but on average, when applied to the Hershey fonts, you got a 50% reduction in wasted pen motion and 30% reduction in storage size for the fonts. For the triple-stroke fonts and Gothic fonts, it did even better. Basicly, all pen-down motion is cast in concrete, you can't get rid of it. What you want to do is to reduce pen-up motion. Your degrees of freedom are the fact that: 1) you can switch endpoints on any pen-down motion 2) you can re-arrange pen-down motions 3) you can take any closed polylines and re-break them at any vertex. Basicly, what my algorithm did was this: I created a database of polylines where each element in the database described a single polyline, including the two endpoints, the actual strokes involved, and whether or not the polyline was closed (two endpoints at same coordinates). Then, I assume the initial pen position is at (0,0) and simply searched the database for the endpoint nearest the current position. I then draw that polyline, remove it from the database and look for the next endpoint. Obviously this is an n**2 algorithm. In the case of closed polylines, all their vertices are eligible when searching for the next polyline, not just the endpoints. Occasionally you find polylines with coincident endpoints; they naturally pop out using this algorithm. If you detect them, you can avoid picking the pen up and putting it down again in the same spot. You can probably do various optimizations such as bounding boxes or assigning polylines to regions, etc. I didn't catch the case where one polyline intersected another (closed) polyline, in which case you can stop drawing your first polyline, draw the second, and then continue with the first. Sorry, I don't have any code; this was years ago. -- -ed falk, sun microsystems, sun!falk, falk@corp.sun.com "If you wrapped yourself in the flag like George Bush does, you'd be worried about flag-burning too"
Nagle@cup.portal.com (John - Nagle) (03/12/90)
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