用有限数量的线段和圆弧来近似表示一条曲线

Question

是否有一种算法可以使用有限数量的线段和圆弧（恒定曲率）来近似表示平面上的路径（即由x和y定义的有序点序列）？生成的曲线需要具有C1连续性（斜率连续性）。

线段和圆弧的最大数量可以是一个参数。另一个有趣的限制是防止两个相邻的圆弧之间没有中间线段连接。

我没有看到任何方法可以做到这一点，也不认为存在一种方法，但对于此目标的任何提示都是受欢迎的。

示例：

此处提供示例文件

考虑这条路径。它看起来像一条直线，但实际上是一组非常接近的有序点。没有噪音，点序列的顺序是众所周知的。

我想用最少的线段和圆弧（比如10个线段和10个圆弧）以及C1连续性来逼近这条曲线。线段/圆弧的数量不是目标本身，但我需要任何可以减少/增加这个数量以达到参数化简单化的参数，以牺牲精度为代价。

解决方案：

这是我的解决方案，基于Spektre的答案。红色曲线是原始数据。黑色线段是线段，蓝色曲线是圆弧。绿色十字架是圆弧中心，显示半径，蓝色十字架是线段可能连接的点。

1. 基于斜率最大偏差和线段最小长度作为参数，检测线段。新线段步长的斜率与现有线段的平均步长进行比较。我更喜欢基于优化的方法，但我认为对于未知数量、位置和长度的不连续线段不存在这样的方法。
2. 使用切线弧连接线段以闭合系统，半径选择使得线段的端点移动最小。出于我的目的，添加了最小半径约束。我相信在拐点很远时（例如，线条几乎平行）并且与相邻线段交互时，会有一些特殊情况需要处理。

- seb007

---

光栅或矢量输入？如果没有样本输入/输出，很难推荐任何曲线拟合方法。我的常规方法是使用向量形式对采样点进行分组（连接组件分析），然后确定它们是直线还是曲线（基于单位距离的角度变化），然后将直线子段连接在一起并拟合曲线... - Spektre

向量输入：我修改了问题以使其更清晰。输入是由 x 和 y 定义的一组点。 - seb007

Answer 1

所以你得到了一个点云...通常认为靠近的点是连接在一起的，因此：

1. 您需要添加关于哪些点靠近哪些点的信息

   仅靠近2个邻居的点表示曲线/线的内部。只有一个邻居意味着曲线/线的端点，而超过2个则表示交叉或太近的几乎平行的线/曲线。没有邻居意味着噪音或只是一个点。

2. 将路径段分组在一起

   这称为连通成分分析。因此，您需要从邻居信息表中形成折线。

3. 检测线性路径块

   这些具有相同的斜率，因此您可以将它们连接成单条线。

4. 使用曲线拟合其余部分

以下是相关的问答：

• 如何在二维点集中找到空洞？
• 算法：椭圆匹配
• 近似搜索的工作原理请查看子链接，有很多拟合的示例
• 将形状追踪为最大n边形

[编辑1]从＃3开始对您的数据进行简单线检测

我使用5.0度角度变化作为线的阈值，同时也将最小检测线的大小设置为50个样本（假设点密度恒定，太懒了不去计算长度）。结果看起来像这样：

点被检测为线段端点，绿色的线是检测到的直线，白色的“线”是曲线，所以目前我没有看到任何问题。现在问题在于剩下的点（曲线），我认为也应该有几何方法来处理它，因为它只是圆弧，所以可以使用像这样的公式：Formula to draw arcs ending in straight lines, Y as a function of X, starting slope, ending slope, starting point and arc radius?。这可能也会有所帮助：Circular approximation of polygon (or its part)。

- Spektre

---

我在问题中添加了一些细节以更清晰地表达。我想在我的情况下只需要步骤3和4。首先检测线性路径块，然后使用曲线连接这些段。需要修改段的端点（延长/限制）以保持C1连续性。 - seb007

@seb007，你是否只能使用圆弧，还是可以使用更好的椭圆弧或三次曲线？ - Spektre

只有圆弧和线段。最好不要连续两个圆弧。 - seb007

@seb007，你应该分享一个矢量形式的样本测试数据进行测试...最好是ASCII格式，以便像SVG或自定义ASCII转储那样轻松访问。哪个项目有问题？ - Spektre

@seb007，小的斜率角偏差被认为是直线。但如何计算斜率角对于大的直线来说很清楚，只需使用atan2即可，但对于非常小的直线，您需要与相邻段进行插值或忽略它们。这取决于您的目标是什么。例如，我的硬件插值器使用“详细”参数，该参数是点之间的最小距离，因此如果任何一段较小，则会与其相邻的段连接...我认为这也适用于您的情况，因为您无论如何都在降低点数。 - Spektre

Answer 2

C1要求您必须交替使用直线和圆弧。此外，如果允许足够数量的线段，则可以轻松地使用一条直线拟合每一对点，并使用微小的圆弧满足斜率连续性。

我建议使用以下算法：

1. 使用一组（指定N）直线段进行最佳拟合。（肯定有成熟的算法可供使用。）

2. 将直线段固定，并在每个连接处放置一个圆弧。将每个连接单独处理，我认为您可以找到最佳圆弧中心/半径以满足连续性并改善拟合。

3. 现在，您已经非常接近，尝试将所有圆弧中心和半径（由切线定义的线段）视为全局优化问题。当然，如果N很大，这会爆炸。

- agentp

Answer 3

在以某曲线近似另一曲线时，一个典型的约束条件是将近似曲线限定在原曲线的 epsilon-套管内（用固定半径 epsilon 的圆盘进行 Minkowski 和运算来表示）。

对于 G1 或 C2 连续逼近（这是CNC/CAD人员喜欢的），使用双二次曲线（直线段可以看作是无限半径的弧）的前同事们开发了一种算法，可以给出如下解决方案 [点击放大]:

上面的图片来自项目网站：https://www.cosy.sbg.ac.at/~held/projects/apx/apx.html 该算法速度快，即运行时间为O(n log n)，基于广义Voronoi图。然而，它不能给出具有最小元素数量的精确近似值。如果您寻找理论最优解，我会参考Drysdale等人的一篇论文，《Approximation of an Open Polygonal Curve with a Minimum Number of Circular Arcs and Biarcs》，CGTA，2008年。

- S. Huber