algorithm - 用有限的线段和圆弧逼近一条曲线

Question

是否有任何算法允许在 x-y 平面(即由 x 和 y 定义的一组有序点)上用有限数量的线段和圆弧(恒定曲率)近似路径？生成的曲线需要为 C1(斜率的连续性)。

最大数量或线段和弧线可以是一个参数。另一个有趣的约束是防止两个连续的圆弧没有中间线段连接它们。

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

示例:

Sample file available here

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

我想用最少数量的线段和圆弧(比方说 10 个线段和 10 个圆弧)和 C1 连续性来近似这条曲线。段/弧的数量本身并不是一个目标，但我需要任何参数来减少/增加这个数量，以实现参数化的某种简单性，但代价是精度损失。

解决方案:

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

1. 根据斜率最大偏差和线段最小长度作为参数检测线段。将新段步长的斜率与现有段的平均步长进行比较。我更喜欢基于优化的方法，但我认为它不存在于数量、位置和长度未知的不相交段。
2. 用相切圆弧连接线段。为了关闭系统，选择半径使得段的末端移动最少。为我的目的添加了最小半径限制。我相信在拐点远离(例如线几乎平行)并与相邻线段相互作用时，会有一些特殊情况需要处理。

Answer 1

所以你得到了一个点云......对于这样的通常靠近在一起的点被认为是连接的所以:

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

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

2. 将路径段组合在一起

   这称为连通分量分析。所以你需要从你的邻居信息表中形成折线。

3. 检测线性路径 block

   这些相邻线段之间的坡度相同，因此您可以将它们连接成一条线。

4. 用曲线拟合其余部分

这里有相关的 QAs:

• Finding holes in 2d point sets?
• Algorithms: Ellipse matching
• How approximation search works查看子链接有相当多的拟合示例
• Trace a shape into a polygon of max n sides

[Edit1] 来自#3 的简单线检测对您的数据

我使用 5.0 deg 角度变化作为线的阈值，并将检测到的线的最小尺寸用作 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)