用有限数量的线段和圆弧逼近曲线 [英] Approximate a curve with a limited number of line segments and arcs of circles

问题描述

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

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

我没有看到任何方法可以做到这一点，我认为不存在实现它的方法，但欢迎对此目标的任何暗示.

示例:

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

我想用最少连续的线段和圆弧(比如说 10 条线段和 10 条圆弧)和 C1 连续性来近似这条曲线.段/弧的数量本身并不是一个目标，但我需要任何允许减少/增加此数量的参数，以达到一定的参数化简单性，但会损失精度.

解决方案:

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

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

解决方案

C1 要求您必须交替直线和圆弧.还要意识到，如果您允许足够数量的线段，您可以用直线轻松拟合每对点，并使用小弧线来满足坡度连续性.

我建议这个算法，

1 最适合一组(指定 N)直线段.(当然有完善的算法.)

2 考虑固定的直线段，并在每个关节处放置一个弧.单独处理每个关节我认为你有一个容易处理的问题来找到最佳的圆弧中心/半径来满足连续性并改善配合.

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

Is there any algorithm that would allow to approximate a path on the x-y plane (i.e. an ordered suite of points defined by x and y) with a limited number of line segments and arcs of circles (constant curvature)? The resulting curve needs to be C1 (continuity of slope).

The maximum number or segments and arcs could be a parameter. An additional interesting constraint would be to prevent two consecutive circles of arcs without an intermediate line segment joining them.

I do not see any way to do this, and I do not think that there exists a method for it, but any hint towards this objective is welcome.

Example:

Sample file available here

Consider this path. It looks like a line, but is actually an ordered suite of very close points. There is no noise and the order of the sequence of points is well known.

I would like to approximate this curve with a minimum number of succession of line segments and circular arcs (let's say 10 line segments and 10 circular arcs) and a C1 continuity. The number of segments/arcs is not an objective itself but I need any parameter which would allow to reduce/increase this number to attain a certain simplicity of the parametrization, at the cost of accuracy loss.

Solution:

Here is my solution, based on Spektre's answer. Red curve is original data. Black lines are segments and blue curves are circle arcs. Green crosses are arc centers with radii shown and blue ones are points where segments potentially join.

1. Detect line segments, based on slope max deviation and segment minimal length as parameters. The slope of the new segment step is compared with the average step of the existing segment. I would prefer an optimization-based method, but I do not think that it exists for disjoint segments with unknown number, position and length.
2. Join segments with tangent arcs. To close the system, the radius is chosen such that the segments extremities are the least possible moved. A minimum radius constraint has been added for my purposes. I believe that there will be some special cases to treat in the inflexion points are far away when (e.g. lines are nearly parallel) and interact with neigboring segments.

解决方案

the C1 requirement demands the you must have alternating straights and arcs. Also realize if you permit a sufficient number of segments you can trivially fit every pair of points with a straight and use a tiny arc to satisfy slope continuity.

I'd suggest this algorithm,

1 best fit with a set of (specified N) straight segments. (surely there are well developed algorithms for that.)

2 consider the straight segments fixed and at each joint place an arc. Treating each joint individually i think you have a tractable problem to find the optimum arc center/radius to satisfy continuity and improve the fit.

3 now that you are pretty close attempt to consider all arc centers and radii (segments being defined by tangency) as a global optimization problem. This of course blows up if N is large.

这篇关于用有限数量的线段和圆弧逼近曲线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！