用一个有限数量的线段和圆弧来近似曲线 [英] 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. 用切线弧加入段。为了关闭系统，选择半径以使分段末端移动的可能性最小。为我的目的添加了最小半径约束。我相信在拐点处会有一些特殊情况需要处理（例如，线条几乎平行）并与相邻节段互动。
   

基于优化的解决方案：

事实证明，找到一种调谐使用上述方法。正如agentp所建议的，我最终使用了一种基于优化的方法。自由度是分段可能相交的点的位置（下图中的洋红色）以及圆的半径。

1. 使用有限的给定数量的线段粗略近似曲线
   
2. 用弧线替换线段交点一个小的固定半径


3. 最小化曲线之间的距离，使用约束优化过程，以段和相关半径的交点位置为参数。
   
   
   
   

   考虑到我必须处理的弧的数量很少（这是我指定的一个参数），它收敛得非常快。下面的结果（对于不同的数据集，抱歉，我无法检索到另一个数据集）。
   
   

   
   
   

   它依赖于单个参数（弧的数量），并且比其他算法更通用，这需要角度容差和分段最小长度。此外，它基于优化过程，这是一个强大的数学基础。在实践中，它适用于任何非自相交的路径。

   解决方案

   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.

   Optimization-based solution:

   It turned out that it is very difficult to find a general method that "always work without tuning" using the method described above. I finally used an optimization-based approach, as suggested by agentp. The degrees of freedom are locations of points where segments potentially intersect (magenta in the graph below), as well as circles radii.

   1. Roughly approximate the curve with a limited given number of segments
   2. Replace segments intersections by arcs with a small fixed radius
   3. Minimize the distance between the curve, using a constrained optimization process with the position of intersections of segments and associated radii as parameters.

   It converges quite rapidly given the low number of arcs I have to treat (which is a parameter that I specify). Result below (for a different dataset, sorry I cannot retrieve the other one).

   It relies on a single parameter (number of arcs), and is much more general than the other algorithm, which required angle tolerance and segment minimum length. Further, it is based on an optimization process, which is a strong mathematical basis. In practice, it worked for me for any non self-intersecing path.

   解决方案

   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屋！