首页 文章

近似具有有限数量的线段和圆弧的曲线

提问于
浏览 次
0

是否存在允许近似x-y平面上的路径（即由x和y定义的有序点集合）的算法，其具有有限数量的线段和圆弧（恒定曲率）？得到的曲线需要是C1（斜率的连续性） .

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

我认为没有办法做到这一点，我认为没有办法解决这个问题，但是对这个目标的任何暗示都是值得欢迎的 .

Example:

Sample file available here

Discrete path defined by a suite of points

考虑这条路 . 它看起来像一条线，但实际上是一个非常接近点的有序套件 . 没有噪声，并且点序列的顺序是众所周知的 .

我想用最小数量的连续线段和圆弧（比如10个线段和10个圆弧）和C1连续性来近似这条曲线 . 段/弧的数量本身不是目标，但是我需要任何允许减少/增加该数量的参数以获得参数化的某些简单性，代价是精度损失 .

Solution:

根据Spektre的回答，这是我的解决方案 . 红色曲线是原始数据 . 黑色线条是段，蓝色曲线是圆弧 . 绿色十字形是弧形中心，半径显示，蓝色十字形是可能连接的区域 .

Fitting

  • 基于斜率最大偏差和段最小长度作为参数检测线段 . 将新分段步骤的斜率与现有分段的平均步长进行比较 . 我更喜欢基于优化的方法，但我认为它不存在具有未知数量，位置和长度的不相交的段 .

  • 使用切线弧连接线段 . 为了关闭系统，选择半径使得段末端移动得最少 . 为我的目的添加了最小半径约束 . 我相信会有一些特殊情况需要在弯曲点处理时（例如线几乎平行）并与neigboring段相互作用 .

algorithm geometry computational-geometry

3 回答

  • 1

    C1要求要求你必须有交替的直线和弧线 . 还要意识到，如果允许足够数量的线段，则可以通过直线轻松地将每对点拟合，并使用小弧来满足斜率连续性 .

    我建议这个算法，

    1最适合一组（指定的N）直段 . （当然，有很好的算法 . ）

    2考虑固定的直线段和每个关节处的弧形 . 单独处理每个关节我认为你有一个易处理的问题，找到最佳的弧中心/半径，以满足连续性和改善拟合 .

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

    回复于
  • 1

    当通过某个其他曲线逼近给定曲线时的典型约束是将近似曲线约束到原始曲线内的ε-软管（如果Minkowski sum具有固定半径epsilon的磁盘） .

    对于具有biarcs的G1或C2连续近似（来自CNC / CAD的人）（以及直线段可以看作具有无限半径的弧），我的同事开发了一种算法，给出了这样的解决方案[点击放大]：

    Sample solution

    以上图片来自项目网站：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 .

    回复于
  • 0

    所以你有一个点 Cloud ......对于这样的通常点在一起被认为是连接的，所以：

    • you need to add info about what points are close to which ones

    点仅接近2个邻居，表示曲线/线的内部 . 只有一个邻居意味着曲线/线的终点，然后多于2表示相交或太近的几乎或平行的线/曲线 . 没有邻居意味着噪音或只是一个点 .

    • group path segments together

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

    • detect linear path chunks

    这些在相邻段之间具有相同的斜率，因此您可以将它们连接到单行 .

    • fit the rest with curves

    Here related QAs:

    [Edit1] simple line detection from #3 on your data

    我使用 5.0 deg 角度变化作为线条的阈值，并且将检测到的线条的最小尺寸用作50个样本（假设恒定点密度，则懒得计算长度） . 结果如下：

    lines

    点是检测到的线 endpoints ，绿线是检测到的线条和白色“线”是曲线，所以我现在看不出这种方法有任何问题 .

    现在的问题是左边的点（曲线）我认为应该还有几何方法，因为它只是圆弧，所以像这样的东西

    这也可能有所帮助：

    回复于

相关问题