我正在开发用于 3D 打印目的的网格切片实用程序。一般来说，它应该将 3d 网格模型切成 2d 形状（许多多边形，可能带有孔），并使用特定图案用确定厚度的路径填充它们。这些路径将用于为 3d 打印机固件生成 gcode 命令。
有各种用途相同的开源工具，用 python 和 perl 编写。但我的目标是了解切片器的工作流程并用 C 或 C++ 编写我自己的工具。
到目前为止，我能够得到切片的轮廓，现在要用路径填充它们。问题是我没有找到有效的算法来做到这一点。填充示例的示意过程：
谁能建议如何生成这些填充路径？谢谢。
目前我正在使用以下算法：
这是一种简单快速的算法，但它不适用于凹多边形和带孔的多边形。它也只使用一种指定的模式。
只要有可能，下面的方法将产生一个由单个路径组成的填充模式（即填充喷嘴永远不会关闭、移动和重新打开）。
在您的第 4 步（“从这些点构造一个与边界偏移的线段”）之后，将每个垂直线段变成 2 个或更多点：顶部和底部端点，加上（想象您的图表绘制在透明幻灯片上；放一张下面有水平线的纸，并标记图表中垂直线段与纸上水平线相交的位置）。
现在形成一个边加权图，其中包含每个点的顶点，只要两个顶点的对应点相距小于或等于一个网格单元，则边连接两个顶点。还要在线段的相邻最高点之间以及相邻最低点之间添加边。使用点之间的欧几里得距离作为边权重。最后，神奇的部分：找到一条最小权重的哈密顿路径在这张图上。这是一条只访问每个顶点一次的路径，并且具有最小长度。最小长度约束保证路径永远不会与自身相交，因为如果任何两条线相交，比如从 a 到 b 的线和从 c 到 d 的线，那么总是可以通过删除这些来创建更短的整体路径两条线并使用不同的端点组合（a---c 和 b---d，或 a---d 和 b---c）创建两条新线。这是您将填写的路径。
寻找哈密顿路径（更不用说最小权重哈密顿路径）是一个 NP 难题，与更著名的旅行商问题密切相关。由于已经存在许多良好的精确 TSP 求解器（例如Concorde），因此明智的做法是使用其中之一来查找旅行推销员旅行，然后简单地删除其中一个边以生成一条短的哈密顿路径。（即使删除最重的边，也不一定会产生最小长度的哈密顿路径，因为可能存在不开始和结束于相邻顶点的较短路径；但我们并不真正关心这里的总长度，我们只想要一条访问所有顶点且不交叉自身的路径。）
不幸的是，不能保证图包含哈密顿路径或旅行商旅行。（例如，如果图是断开连接的，它们显然不存在，但即使是连通图也可能无法拥有其中一个或两者：例如，具有任何 1 度顶点的图不能有 TSP 巡回。）在这种情况下，如果您正在使用的 TSP 求解器可以找到不访问所有顶点的游览，您可以重复此操作，直到覆盖所有顶点。如果做不到这一点，我会求助于你原来的算法。
经过一段时间的研究，我得出了以下算法：
不过，有许多优化机会。
您可能想查看有关将阴影应用于区域的算法的网页。
恢复一个旧线程。
应用此处提供的答案中描述的技术，我创建了一个名为“Mandoline”的实现。请在此处查看：https ://github.com/Tannz0rz/Mandoline