c# - 将折线转换为具有宽度的多边形

Question

当我试图解析 Gerber RS274X 文件并将其转换为 GDSII 文件时，我遇到了一个问题。

如果你沿着某个路径（一条折线）画一个实心圆，你得到的是一个实心形状，它可以随后转换为一个封闭的多边形。我的问题是是否有一个库或可靠的算法来自动化这个过程，其中输入将是一串表示折线的点，输出将是生成的多边形。

下面是我上传的图片来解释我的问题。

Answer 1

您可以通过在每个输入点周围放置所需数量的均匀间隔的点来计算您寻找的形状，然后在线段上找到每对圆的凸包。这些多边形的联合将组成您想要的多边形。

有许多算法可以找到一组点的凸包，还有提供实现的库。

Answer 2

您正在谈论的算法称为“Minkowski sum”（在您的情况下，折线和多边形，近似一个圆）。在您的情况下，第二个和（圆）是凸的，这意味着可以使用所谓的多边形卷积相当有效地计算 Minkowski 和。

您没有指定您使用的语言。在 C++ 中，Minkowski sum 可作为Boost.Polygon的一部分或作为CGAL的一部分使用。

要使用它们，您可能需要通过两次遍历将折线转换为（退化的）多边形：向前，然后向后。

@melak47 提出的凸包联合将产生正确的结果，但效率要低得多。