最大限度地减少笔式绘图仪或类似设备中的笔抬起
我正在寻找在机械笔绘图仪上绘图的算法的参考。
具体来说，我有一个直向量列表，每个向量代表要绘制的一条线。首先，我想删除重复的向量，因此每条线仅绘制一次。这很容易。
其次，有许多向量相交，有时在端点处相交，但并非总是如此。它们可以按任何顺序绘制，但我想找到一个顺序来减少必须举起笔的次数，最好是最少，尽管我知道如果可以计算的话，这可能需要很长时间来计算。如果有帮助的话，可以将相交的向量分解为更小的向量。但一般来说，如果笔沿直线移动，最好尽可能长时间地保持这种移动方式。因此，两个端到端连接的并行向量可以组合成一个向量，等等。
这听起来像是某种图论问题，但我对此了解不多。谁能给我指出我需要学习的参考资料或算法？或者也许是示例代码？
谢谢，
尼尔
I'm looking for references to algorithms for plotting on a mechanical pen plotter.
Specifically, I have a list of straight vectors, each representing a line to be plotted. First I want to remove duplicate vectors, so each line is only plotted once. That's easy enough.
Second, there are many vectors that intersect, sometimes at endpoints, but not always. They can be plotted in any order, but I want to find an order that reduces the number of times the pen must be lifted, preferably to a minimum though I understand that may take a long time to compute, if it's computable at all. Vectors that intersect can be broken into smaller vectors if that helps. But generally, if the pen is moving in a straight line, it's best to keep it moving that way as long as possible. So, two parallel vectors joined end to end could be combined into a single vector, etc.
This sounds like some variety of graph theory problem, but I don't know much about that. Can anyone point me to references or algorithms I need to study? Or maybe example code?
Thanks,
Neil
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该问题是中国邮差问题的一个例子，它是一个NP完全问题问题。最著名的 NP 完全问题是旅行推销员。所有 NP 完全问题的共同点是它们都可以相互转化。没有已知的算法可以在多项式依赖于输入中节点数量的时间内求解其中任何一个，它们是非多项式 (NP) 的。
对于你的情况，我会建议一些简单的启发法。不要做得太过分，只需选择任何非常简单的事情，例如尽可能长时间地走直线，然后将笔举到最近的可用起点并从那里继续。
The problem is an example of the Chinese postman problem which is an NP-complete problem. The most wellknown NP-complete problem is the Travelling Salesman. Common for all NP-complete problems are that they can all be translated into eachother. There are no known algorithms for solving any of them in a time that is polynomial dependent of the number of nodes in the input, they are non-polynomial (NP).
For your case I would suggest some simple heuristics. Don't overdo it, just pick anything quite simple like going in a straight line as long as possible and then lift the pen to the closest available starting point and go on from there.