基于遗传算法的以线段和圆弧为基元的曲线拟合

采用线段和圆弧作逼近基元是数字曲线拟合中的一个难点。文中给出一种基于改进遗传算法的拟合方法。通过对点列进行二进制编码，以拟合段数较少和拟合误差较小为优化目标，变异概率和交叉概率自适应生成，并根据相关知识控制分界点间隙，所得最优解中值为1的基因对应数字曲线的分界点，对线段与圆弧相交和相切以及具有噪声等多种情况进行检测，可同时提取尖点和切点，还可得到逼近基元及其之间关系。较好地解决了用线段和圆弧拟合曲线问题。

Segmenting Planar Curves into Straight Line and Circular Arcs Segments Using Genetic Algorithm

Demarcation points from a curve with least number of segments (lines and arcs) are extracted, and each of them can be fitted into a line or arc with least error. Chromosomes are encoded into binary strings. Mutation probabilities and crossover probabilities are calculated adaptively. The gaps between demarcation points are restricted. Points of a curve corresponding to genes of a chromosome which are 1s, are demarcation ones. The algorithm can deal with many cases including a line is intersecting or tangent to an arc, an arc is tangent to an arc, and some points are noisy ones, and can detect cusp and tangent points. The method can represent well a curve with lines and arcs, the algorithm is effective and robust.