多边形填充算法

Question

我正在为3D打印目的使用网格切片工具。一般来说，它应该将3d网格模型切成2d形状（多个多边形，可能带有孔），并使用特定图案填充确定厚度的路径。这些路径将用于生成3d打印机固件的gcode命令。

有各种开源工具，同样的目的，写在Python和Perl。但我的目标是理解切片机的工作流程并用C或C++编写我自己的工具。

到目前为止，我能够得到片的轮廓，现在该怎么处理路径填充。问题是我没有找到有效的算法来做到这一点。 甲填充实例的示意性过程：

任何人都可以建议如何生成这些填充路径？谢谢。

---

目前我使用下面的算法：

1. 查找形状的边界框
2. 拆分BB垂直线（行数= bb.width/path.thickness）
3. 找到形状和每条线的交点（应该是每条线两个点）
4. 从这些点构造一个线段与边界的偏移
5. 添加段，将原来的网段连接在一起，形成一个线带
6. 我们准备生成G代码或绘制路径

这是简单而快速的算法，但它确实不适用于凹多边形和带孔的多边形。它也只使用一个指定的模式。

Answer 1

经过研究一段时间，我在下面的算法结束： 有许多的优化机会，虽然。

Answer 2

你可能想看看this webpage约算法应用孵化到的区域。

Answer 3

下面的方法将产生一个填充图案，该图案由单一路径组成（即填充喷嘴永远不会关闭，移动并重新打开），只要这是可能的。

在你的第4步（“用这些点与边界的偏移量构造一个线段”）之后，将每一个垂直线段转换成2个或更多的点：顶部和底部端点，加上（想象你的图画在透明的幻灯片;在下面放一张水平线的纸，并标出图中垂直线段与纸上水平线相交的位置）。

立即形成包含每个点的顶点的边加权曲线图，与连接两个顶点每当他们的对应点小于或等于开一个网格单元的边缘。还要在线段的相邻最高点之间以及相邻最低点之间添加边线。使用边缘权重点之间的欧几里德距离。最后，魔术部分：在此图上找到最小重量Hamiltonian path。这是一个访问每个顶点一次的路径，并且具有最小长度。最小长度限制保证了路径永远不会自行交叉，因为如果任何两条线交叉，比如说a到b的线和c到d的线，那么通过删除它们总是可以创建一个更短的整体路径两行，并使用不同的端点组合（创建一个--- c和b --- d或者a --- d和b --- c）创建两个新行。这是你将要填写的路径。

查找哈密尔顿路径（更不用说最小权重哈密尔顿路径）是一个NP难问题密切相关，比较著名的旅行商问题。由于许多很好的确切TSP求解器已经存在（例如Concorde），这将是明智的，而不是使用其中的一个找一个旅行商参观，然后只需删除其中一个边缘以生产短的哈密尔顿路径。 （即使你删除了最重的边缘，这不一定会产生一个最小长度哈密尔顿路径，因为它可能是存在不开始，并在相邻顶点结束较短的路径，但我们真的不关心这里总长度，我们只想说所有访问顶点和不跨越本身的路径。）

不幸的是，图并不保证包含一个哈密顿路径，或旅行商参观。 ，在这种情况下，如果：（例如，具有1度的任何顶点的曲线图不能具有TSP游它们显然不能如果图断开存在，例如，但即使连接图形可以不具有任一个或两个）。您正在使用的TSP解算器可以找到不访问所有顶点的巡视，您可以重复此操作直到覆盖所有顶点。否则，我会回到你原来的算法。