论文部分内容阅读
摘要：讨论曲线拟合的基本原理，结合一些地形图测绘成果，分析各种曲线拟合算法，并实现加权分段圆弧法拟合曲线，分析拟合效果。
关键词：数字测图，曲线拟合，加权分段圆弧法
中图分类号：P231.5 文献标识码：A 文章编号：
Analysis of Curve Fitting Algorithms for Digital Mapping
Abstract:Combined with some topographic map surveying and mapping results to discuss the basic principle of curve fitting and analysis of a variety of curve fitting algorithm ,achieve weighted segmented arc method fitting curve and analysis fitting effect.
Key words: digital mapping, curve fitting, weighted segmented arc method
1.引言
数字测图是以计算机及其软件为核心在外接输入、输出设备的支持下，对地形空间数据进行采集、输入、成图、绘图、输出、管理。作为数字测图过程中主要处理对象的空间数据代表着现实世界地理实体或现象在信息世界中的映射。它具有空间性，属性和时间性。空间数据根据表示对象的不同，具体可分为七种类型，即类型数据、面域数据、网络数据、样本数据、曲面数据、文本数据、符号数据。所有这些不同类型的数据都可以由点、线、面三种不同的图形表示。而曲线的绘制是在实际工作中经常碰到，也是较难处理的问题，如果曲线绘制的方法不够严格，通过数字绘图所得的图形数据往往和实际情况有较大的偏差，甚至与实际情况相悖。
2.曲线拟合的基本原理
在数字绘图的过程中，往往需要将已知离散采样点连接成光滑曲线，如通过测高点勾画等高线；通过手工数字化采集等高线数据后，重新内插生成等高线；以及通过离散的实测或统计采样点，生成等值区域等。这一过程的实质就是采样点的曲线光滑处理，也称为采样点曲线拟合。
曲线拟合是用连续曲线近似地比拟平面上离散点组所表示的坐标之间的函数关系的一种数据处理方法。即是用解析表达式逼近离散数据的一种方法。曲线拟合所要完成的任务也就是在一定意义下“最佳”地逼近或拟合已知数据。由于通过测量和观测所得到的数据本身就有误差，所以在绘制曲线的过程中一定要通过型值点（x，y）似乎没有必要，因此如何使得空间内选择函数Y=Ψ（x）尽可能地逼近真实函数Y=f（x），就是曲线拟合所要解决的主要问题。如图一就是使用南方CASS成图软件所绘制的，进行曲线拟合处理前后的图形。
图1曲线拟合前后对比
3. 实际工作中的问题和简单处理方法
在实际工作中，所要绘制的线要素，都可以看成是曲线和直线的组合。如果在计算机绘图时，只考虑直线，不使用曲线的拟合功能，虽然能够保证通过测量所得到的点都能够准确的绘制在线要素上，但是绘制出来线要素并不能准确地描述出实际情况。如果在绘图工作中过于依赖曲线拟合功能，也不能准确地描述出实际情况。图2为某镇地形图的一部分，其中路中间的为隔离带。现将单个隔离带图形提取出来进行研究，图3为采用不同方法绘制出的隔离带图形。
图2
图3
综上所述，在绘图工作中，应当将直线绘制和曲线拟合综合考虑。图2就是综合两种情况考虑的结果，显然绘制的效果要比简单只考虑直线绘制和过于依赖曲线拟合所绘制的效果好。
4．拟合算法研究简介
常用的曲线拟合算法有张力样条函数，分段三次多项式，分段圆弧和切线方向内插法等。
4．1张力样条函数法
设已知特征点序列(xi,yi ),i=1,2,3,…，n，且满足条件x1 yi=f(xi) i=1,2,3,…，n，
同时还要求f"(x)-σ2f(x)必须是连续的，并且在每个区间[xi,xi+1](i=1,2,3,…，n-1)成线性变化，即：
式中Hi=Xi+1-Xi。
上式是一个二阶非齐次的常系数性微分方程，它的通解为:
式中的Y为它对应的齐次方程f"(X)-σ2f(X)=0的通解，即Y=c1e2x+c2e-2x，为它的一个特解，=aX+b。根据通过每一离散点的初始条件，就可解算出c1,c2和a,b的值。最后经过整理可得到单值情况下的张力样条函数：
式中Xi≤X≤Xi+1,Hi=Xi+1-Xi,i=1,2,3,…，n， 因此，只要能够确定各离散点处的二阶导数f"(Xi)，这个张力样条函数式便完全确定。
从张力样条函数中可以看到，其中σ称为张力系数。通过改变σ的大小，可以调节拟合曲线的光滑程度：σ趋近于0，则曲线为三次样条；当σ趋近于无穷大，则曲线退化为折线。张力样条函数虽然有较好的拟合效果，但是相应的计算量也较大，实现效率较差。
4．2分段三次多项式法
分段三次多项式又称五点光滑法，其原理是在每两个采样点之间建立一条三次多项式曲线方程，且整条曲线具有连续的一阶导数；各采样点的一阶导数以该点及其两侧相邻各两点（共5点）来确定，从而保证曲线是光滑的。
4．3分段圆弧法
已知平面上有若干采样点P1 (Xi,Yi)，P2 (X2,Y2)，…，Pn (Xn,Yn)，在任意两个采样点Pi(Xi,Yi)和Pi+1(X i+1,Y i+1)之间，用两条相切圆弧进行拟合，并且要求擬合曲线严格通过该两点，同时要求它在这两个已知处的一阶导数也等于给定值。
显然，根据上述原则，一般可以得到多组满足条件的圆弧。如再加以一定的条件限制，则可以得到唯一解。
4．4切线方向法
该方法即根据采样点处切线方向来拟合采样曲线，进而进行空间数据内插。根据内插时使用的采样点的数量，又分为三点法和五点法。
后三种算法，相对张力样条函数法在算法上要较为简练，并同样能较好的实现拟合的效果，特别是切线方向法的五点法，实践证明五点法最接近训练有素的绘图员徒手绘制的内插曲线。
5．拟合算法应用中的见解
除以上介绍的采样点曲线拟合算法之外，还有线性迭代、二次多项式平均加权法和斜轴抛物线平均加权法等。但是这些方法的缺陷在于有的实现较为复杂，运算效率较低；有的拟合效果较差，或是拟合的范围有限。通过与某市八镇地形图测绘成果图相结合，发现分段圆弧法拟合曲线通过一些加权条件的控制，可以达到不错的拟合效果。而在计算机实现方面，也较为简单。
图4
如图4所示，隔离带由两条直线和两条弧线组成，由于隔离带是对称的结构，所以以下只对一端曲线拟合的方法和效果进行讨论。隔离带上的采样点有Pi，Pi+1，Pi+2……，在Pi和Pi+1之间绘制拟合曲线时。
(1)设定权值为要求两个拟合圆的圆心连线（OiO i+1）与采样点Pi和Pi+1的连线相互垂直，则有
其中a为Pi Pi+1与x轴夹角，θi和θi+1分别为过Pi切线（即已知直线）和过Pi+1切线与Pi Pi+1夹角。
(2)根据权值条件：
(3)即可解得：
进而得Oi和O i+1的圆心坐标，绘出拟合曲线。
[参考文献]
[1]吴立新、史文中.地理信息系统原理与算法.科学出版社，2005:196－200
[2]张宏、温永宁、刘爱利.地理信息系统算法基础. 科学出版社，2007:157-171
[3] 陈永奇、张正禄、吴子安等.高等应用测量.武汉测绘科技大学出版社，1996
[4] 王侬，过静珺等.现代普通测量学（第2版）.清华大学出版社，2009
[5] 邹逸江.关于曲线拟合的线要素综合数据处理及见解.科技信息，2011（35）
关键词：数字测图，曲线拟合，加权分段圆弧法
中图分类号：P231.5 文献标识码：A 文章编号：
Analysis of Curve Fitting Algorithms for Digital Mapping
Abstract:Combined with some topographic map surveying and mapping results to discuss the basic principle of curve fitting and analysis of a variety of curve fitting algorithm ,achieve weighted segmented arc method fitting curve and analysis fitting effect.
Key words: digital mapping, curve fitting, weighted segmented arc method
1.引言
数字测图是以计算机及其软件为核心在外接输入、输出设备的支持下，对地形空间数据进行采集、输入、成图、绘图、输出、管理。作为数字测图过程中主要处理对象的空间数据代表着现实世界地理实体或现象在信息世界中的映射。它具有空间性，属性和时间性。空间数据根据表示对象的不同，具体可分为七种类型，即类型数据、面域数据、网络数据、样本数据、曲面数据、文本数据、符号数据。所有这些不同类型的数据都可以由点、线、面三种不同的图形表示。而曲线的绘制是在实际工作中经常碰到，也是较难处理的问题，如果曲线绘制的方法不够严格，通过数字绘图所得的图形数据往往和实际情况有较大的偏差，甚至与实际情况相悖。
2.曲线拟合的基本原理
在数字绘图的过程中，往往需要将已知离散采样点连接成光滑曲线，如通过测高点勾画等高线；通过手工数字化采集等高线数据后，重新内插生成等高线；以及通过离散的实测或统计采样点，生成等值区域等。这一过程的实质就是采样点的曲线光滑处理，也称为采样点曲线拟合。
曲线拟合是用连续曲线近似地比拟平面上离散点组所表示的坐标之间的函数关系的一种数据处理方法。即是用解析表达式逼近离散数据的一种方法。曲线拟合所要完成的任务也就是在一定意义下“最佳”地逼近或拟合已知数据。由于通过测量和观测所得到的数据本身就有误差，所以在绘制曲线的过程中一定要通过型值点（x，y）似乎没有必要，因此如何使得空间内选择函数Y=Ψ（x）尽可能地逼近真实函数Y=f（x），就是曲线拟合所要解决的主要问题。如图一就是使用南方CASS成图软件所绘制的，进行曲线拟合处理前后的图形。
图1曲线拟合前后对比
3. 实际工作中的问题和简单处理方法
在实际工作中，所要绘制的线要素，都可以看成是曲线和直线的组合。如果在计算机绘图时，只考虑直线，不使用曲线的拟合功能，虽然能够保证通过测量所得到的点都能够准确的绘制在线要素上，但是绘制出来线要素并不能准确地描述出实际情况。如果在绘图工作中过于依赖曲线拟合功能，也不能准确地描述出实际情况。图2为某镇地形图的一部分，其中路中间的为隔离带。现将单个隔离带图形提取出来进行研究，图3为采用不同方法绘制出的隔离带图形。
图2
图3
综上所述，在绘图工作中，应当将直线绘制和曲线拟合综合考虑。图2就是综合两种情况考虑的结果，显然绘制的效果要比简单只考虑直线绘制和过于依赖曲线拟合所绘制的效果好。
4．拟合算法研究简介
常用的曲线拟合算法有张力样条函数，分段三次多项式，分段圆弧和切线方向内插法等。
4．1张力样条函数法
设已知特征点序列(xi,yi ),i=1,2,3,…，n，且满足条件x1
同时还要求f"(x)-σ2f(x)必须是连续的，并且在每个区间[xi,xi+1](i=1,2,3,…，n-1)成线性变化，即：
式中Hi=Xi+1-Xi。
上式是一个二阶非齐次的常系数性微分方程，它的通解为:
式中的Y为它对应的齐次方程f"(X)-σ2f(X)=0的通解，即Y=c1e2x+c2e-2x，为它的一个特解，=aX+b。根据通过每一离散点的初始条件，就可解算出c1,c2和a,b的值。最后经过整理可得到单值情况下的张力样条函数：
式中Xi≤X≤Xi+1,Hi=Xi+1-Xi,i=1,2,3,…，n， 因此，只要能够确定各离散点处的二阶导数f"(Xi)，这个张力样条函数式便完全确定。
从张力样条函数中可以看到，其中σ称为张力系数。通过改变σ的大小，可以调节拟合曲线的光滑程度：σ趋近于0，则曲线为三次样条；当σ趋近于无穷大，则曲线退化为折线。张力样条函数虽然有较好的拟合效果，但是相应的计算量也较大，实现效率较差。
4．2分段三次多项式法
分段三次多项式又称五点光滑法，其原理是在每两个采样点之间建立一条三次多项式曲线方程，且整条曲线具有连续的一阶导数；各采样点的一阶导数以该点及其两侧相邻各两点（共5点）来确定，从而保证曲线是光滑的。
4．3分段圆弧法
已知平面上有若干采样点P1 (Xi,Yi)，P2 (X2,Y2)，…，Pn (Xn,Yn)，在任意两个采样点Pi(Xi,Yi)和Pi+1(X i+1,Y i+1)之间，用两条相切圆弧进行拟合，并且要求擬合曲线严格通过该两点，同时要求它在这两个已知处的一阶导数也等于给定值。
显然，根据上述原则，一般可以得到多组满足条件的圆弧。如再加以一定的条件限制，则可以得到唯一解。
4．4切线方向法
该方法即根据采样点处切线方向来拟合采样曲线，进而进行空间数据内插。根据内插时使用的采样点的数量，又分为三点法和五点法。
后三种算法，相对张力样条函数法在算法上要较为简练，并同样能较好的实现拟合的效果，特别是切线方向法的五点法，实践证明五点法最接近训练有素的绘图员徒手绘制的内插曲线。
5．拟合算法应用中的见解
除以上介绍的采样点曲线拟合算法之外，还有线性迭代、二次多项式平均加权法和斜轴抛物线平均加权法等。但是这些方法的缺陷在于有的实现较为复杂，运算效率较低；有的拟合效果较差，或是拟合的范围有限。通过与某市八镇地形图测绘成果图相结合，发现分段圆弧法拟合曲线通过一些加权条件的控制，可以达到不错的拟合效果。而在计算机实现方面，也较为简单。
图4
如图4所示，隔离带由两条直线和两条弧线组成，由于隔离带是对称的结构，所以以下只对一端曲线拟合的方法和效果进行讨论。隔离带上的采样点有Pi，Pi+1，Pi+2……，在Pi和Pi+1之间绘制拟合曲线时。
(1)设定权值为要求两个拟合圆的圆心连线（OiO i+1）与采样点Pi和Pi+1的连线相互垂直，则有
其中a为Pi Pi+1与x轴夹角，θi和θi+1分别为过Pi切线（即已知直线）和过Pi+1切线与Pi Pi+1夹角。
(2)根据权值条件：
(3)即可解得：
进而得Oi和O i+1的圆心坐标，绘出拟合曲线。
[参考文献]
[1]吴立新、史文中.地理信息系统原理与算法.科学出版社，2005:196－200
[2]张宏、温永宁、刘爱利.地理信息系统算法基础. 科学出版社，2007:157-171
[3] 陈永奇、张正禄、吴子安等.高等应用测量.武汉测绘科技大学出版社，1996
[4] 王侬，过静珺等.现代普通测量学（第2版）.清华大学出版社，2009
[5] 邹逸江.关于曲线拟合的线要素综合数据处理及见解.科技信息，2011（35）