我正在寻找有关在机械笔式绘图仪上绘图的算法的引用。
具体来说，我有一个直线向量列表，每个直线向量都代表要绘制的线。首先，我要删除重复的向量，因此每条线仅绘制一次。那很容易。
其次，有许多矢量相交，有时在端点处相交，但并不总是相交。它们可以按任何顺序绘制，但是我想找到一个减少笔必须抬起的次数的顺序，最好是减少到最小，尽管我知道这可能需要很长时间才能计算出(如果它是可计算的)。如果有帮助，可以将相交的向量分解为较小的向量。但是通常，如果笔沿直线移动，则最好使其保持尽可能长的移动时间。因此，可以将两个首尾相连的并行向量组合成一个向量，依此类推。
这听起来像某种图论问题，但是我对此并不了解。谁能指出我需要学习的引用文献或算法？还是示例代码？
谢谢，
尼尔
最佳答案
该问题是Chinese postman problem的一个示例，它是一个NP完全问题。最著名的NP完全问题是Travelling Salesman。所有NP完全问题的共同点是它们都可以相互转化。没有一种已知的算法可以在一个时间范围内求解任何一个算法，而该算法取决于多项式取决于输入中的节点数，它们是非多项式(NP)。
对于您的情况，我建议使用一些简单的启发式方法。不要过度使用它，只要选择一些很简单的方法，例如尽可能长的沿直线走，然后将笔抬到最接近的可用起点，然后从那里继续。
关于optimization - 最小化笔式绘图仪或类似设备中的笔升，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2509566/