用有限的线段和圆弧逼近一条曲线
Approximate a curve with a limited number of line segments and arcs of circles
是否有任何算法允许在 x-y 平面（即由 x 和 y 定义的一组有序点）上用有限数量的线段和圆弧（恒定曲率）近似路径？生成的曲线需要为 C1（斜率的连续性）。
最大数量或线段和弧线可以作为参数。另一个有趣的约束是防止两个连续的圆弧没有中间线段连接它们。
我看不出有什么方法可以做到这一点，而且我不认为有任何方法可以做到这一点，但是欢迎任何对此 objective 的提示。
示例：
考虑这条路。它看起来像一条线，但实际上是一组非常接近的点的有序集合。没有噪声，点序列的顺序是众所周知的。
我想用最少数量的线段和圆弧（比方说 10 个线段和 10 个圆弧）和 C1 连续性来近似这条曲线。 segments/arcs 的数量本身不是 objective，但我需要任何允许 reduce/increase 这个数字的参数，以达到一定程度的参数化简单性，但代价是精度损失。
解法：
这是我的解决方案，基于 Spektre 的回答。红色曲线为原始数据。黑线是线段，蓝色曲线是圆弧。绿色十字是显示半径的圆弧中心，蓝色十字是线段可能连接的点。
- 检测线段，以斜率最大偏差和线段最小长度为参数。将新段步长的斜率与现有段的平均步长进行比较。我更喜欢基于优化的方法，但我认为它不存在于数量、位置和长度未知的不相交段。
- 用相切圆弧连接线段。为了关闭系统，选择半径使得段的末端移动最少。为我的目的添加了最小半径限制。我相信会有一些特殊情况需要处理，当拐点很远时（例如线几乎平行）并且与相邻线段相互作用。
所以你得到了一个点云......对于这样的通常点靠近在一起被认为是连接的所以：
你需要添加关于哪些点接近哪些点的信息
点仅靠近 2 个邻居信号 curve/line 的内部。只有一个邻居表示 curve/line 的端点，超过 2 个表示相交或太近或平行 lines/curves。没有邻居意味着噪音或只是一个点。
将路径段组合在一起
这叫做连通分量分析。所以你需要根据你的邻居信息 table.
检测线性路径块
这些相邻线段之间的坡度相同，因此您可以将它们连接成一条线。
用曲线拟合其余部分
这里有相关的问答：
- Finding holes in 2d point sets?
看下链接里面有不少拟合的例子 - Trace a shape into a polygon of max n sides
[Edit1] 对您的数据进行 #3 的简单线检测
我使用 5.0 deg 角度变化作为线的阈值，并将检测到的线的最小尺寸用作 50 个样本（假设点密度恒定，懒得计算长度）。结果如下所示：
点是检测到的线端点，绿线是检测到的线，白色 "lines" 是曲线，所以我现在没有发现这种方法有任何问题。
现在的问题是剩下的点（曲线）我认为也应该有几何方法，因为它只是圆弧所以像这样
- 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)
C1 的要求要求你必须 交替的直线和弧线。还要意识到，如果允许有足够数量的线段，则可以用直线简单地拟合每对点，并使用微小的圆弧来满足斜率连续性。
我推荐这个算法，
1 最适合一组（指定的 N 个）直线段。 （当然有完善的算法。）
2 考虑固定直线段，在每个关节处放置一个圆弧。单独处理每个关节我认为你有一个易于处理的问题来找到最佳弧度 center/radius 以满足连续性并提高拟合度。
3 现在您已经非常接近尝试将所有圆弧中心和半径（由相切定义的线段）视为全局优化问题。如果 N 很大，这当然会爆炸。
用其他曲线近似给定曲线时的典型约束是将近似曲线绑定到原始曲线内的 epsilon-hose（如果 Minkowski sum 具有固定半径 epsilon 的圆盘）。
对于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 圆弧和双弧的最小数量，CGTA，2008.
是否有任何算法允许在 x-y 平面（即由 x 和 y 定义的一组有序点）上用有限数量的线段和圆弧（恒定曲率）近似路径？生成的曲线需要为 C1（斜率的连续性）。
最大数量或线段和弧线可以作为参数。另一个有趣的约束是防止两个连续的圆弧没有中间线段连接它们。
我看不出有什么方法可以做到这一点，而且我不认为有任何方法可以做到这一点，但是欢迎任何对此 objective 的提示。
示例：
考虑这条路。它看起来像一条线，但实际上是一组非常接近的点的有序集合。没有噪声，点序列的顺序是众所周知的。
我想用最少数量的线段和圆弧（比方说 10 个线段和 10 个圆弧）和 C1 连续性来近似这条曲线。 segments/arcs 的数量本身不是 objective，但我需要任何允许 reduce/increase 这个数字的参数，以达到一定程度的参数化简单性，但代价是精度损失。
解法：
这是我的解决方案，基于 Spektre 的回答。红色曲线为原始数据。黑线是线段，蓝色曲线是圆弧。绿色十字是显示半径的圆弧中心，蓝色十字是线段可能连接的点。
- 检测线段，以斜率最大偏差和线段最小长度为参数。将新段步长的斜率与现有段的平均步长进行比较。我更喜欢基于优化的方法，但我认为它不存在于数量、位置和长度未知的不相交段。
- 用相切圆弧连接线段。为了关闭系统，选择半径使得段的末端移动最少。为我的目的添加了最小半径限制。我相信会有一些特殊情况需要处理，当拐点很远时（例如线几乎平行）并且与相邻线段相互作用。
所以你得到了一个点云......对于这样的通常点靠近在一起被认为是连接的所以：
你需要添加关于哪些点接近哪些点的信息
点仅靠近 2 个邻居信号 curve/line 的内部。只有一个邻居表示 curve/line 的端点，超过 2 个表示相交或太近或平行 lines/curves。没有邻居意味着噪音或只是一个点。
将路径段组合在一起
这叫做连通分量分析。所以你需要根据你的邻居信息 table.
形成折线
检测线性路径块
这些相邻线段之间的坡度相同，因此您可以将它们连接成一条线。
用曲线拟合其余部分
这里有相关的问答：
- Finding holes in 2d point sets?
- Trace a shape into a polygon of max n sides
[Edit1] 对您的数据进行 #3 的简单线检测
我使用 5.0 deg 角度变化作为线的阈值，并将检测到的线的最小尺寸用作 50 个样本（假设点密度恒定，懒得计算长度）。结果如下所示：
点是检测到的线端点，绿线是检测到的线，白色 "lines" 是曲线，所以我现在没有发现这种方法有任何问题。
现在的问题是剩下的点（曲线）我认为也应该有几何方法，因为它只是圆弧所以像这样
- 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)
C1 的要求要求你必须 交替的直线和弧线。还要意识到，如果允许有足够数量的线段，则可以用直线简单地拟合每对点，并使用微小的圆弧来满足斜率连续性。
我推荐这个算法，
1 最适合一组（指定的 N 个）直线段。 （当然有完善的算法。）
2 考虑固定直线段，在每个关节处放置一个圆弧。单独处理每个关节我认为你有一个易于处理的问题来找到最佳弧度 center/radius 以满足连续性并提高拟合度。
3 现在您已经非常接近尝试将所有圆弧中心和半径（由相切定义的线段）视为全局优化问题。如果 N 很大，这当然会爆炸。
用其他曲线近似给定曲线时的典型约束是将近似曲线绑定到原始曲线内的 epsilon-hose（如果 Minkowski sum 具有固定半径 epsilon 的圆盘）。
对于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 圆弧和双弧的最小数量，CGTA，2008.