B-Spline样条和二次Bezier曲线的一种实现方法

                            
            B-Spline样条和二次Bezier曲线的一种实现方法

                                吕雪松

	在地理信息系统的应用中,经常会涉及到光滑曲线的应用;而光滑曲线的应用,既要解决适合计算机处理,且有效地满足空间表示与几何表现要求,又便于形状信息传递和地理数据交换的空间描述。1963年美国波音飞机公司的Ferguson首先提出将曲线曲面表示为参数的矢函数方法,并引入参数三次曲线。从此曲线曲面的参数化形式成为形状数学描述的标准形式。1964年美国麻省理工学院的Coons发表一种具有一般性的曲面描述方法,给定围成封闭曲线的四条边界就可定义一块曲面。但这种方法存在形状控制与连接问题。1971年法国雷诺汽车公司的Bezier提出一种由控制多边形设计曲线的新方法。这种方法不仅简单易用,而且漂亮地解决了整体形状控制问题,把曲线曲面的设计向前推进了一大步,为曲面造型的进一步发展奠定了坚实的基础。但Bezier方法仍存在连接问题和局部修改问题。到1972年,de-Boor总结、给出了关于B样条的一套标准算法,1974年Gordon和Riesenfeld又把B样条理论应用于形状描述,最终提出了B样条方法。这种方法继承了Bezier方法的一切优点,克服了Bezier方法存在的缺点,较成功地解决了局部控制问题,又轻而易举地在参数连续性基础上解决了连接问题,从而使自由型曲线曲面形状的描述问题得到较好解决。
	B样条曲线的坐标位置可表示为: 
 
	B样条具有以下性质: 
•		在u值域内,多项式次数为d-1 
•		对于n+1个控制点,曲线由n+1个混合函数描述 
•		每个混合函数Bk,d定义域为u值域的d子区间,以节点向量值uk为起点。 
•		参数u的值域由n+d+1个给定节点向量值分成n+d个子区间 
•		节点记为{u0,u1,u2,…,un+d},生成的样条曲线仅定义在从节点值ud-1到节点值un+1区间上 
•		每个样条曲线段(在两个相邻节点值间)受d个控制点影响。 
•	一个控制点可以影响最多d个曲线段的影响。 

	Bezier曲线最直接的表现为除端点外,不过控制点的光滑曲线,在整个周期范围内可求导,任意控制点的变化都会影响其形状。Bezier曲线的数学描述为
	Bezier曲线具有以下特征:
•	端点与特征多边形起点或终点重合,且与特征多边形边形相切;
•	Bezier曲线具有对称性,即控制点顺序的反向调整不改变整个曲线的形状;
•	曲线均位于特征多边形构成凸包之中;

	抛开复杂的数字理论模型不谈,应该说,B样条和Bezier贝塞尔曲线是地理信息系统中两种最常用的光滑曲线,或者说是两种最常用的曲线插值算法,二者之间不存在优劣之分,都可以分别应用在曲面光滑、曲线注记、TTF符号优化等环境中。如下所示两条过相同控制点的样条曲线和Bezier曲线的形状。
 
	在实现上,利用面向对象的方法来构造曲线类的层次结构,如下图所示:
	所有的类都从一个CGeoObject的虚基类派生,它是所有地物的共同基类,通过它,还可以派生诸如点、多边形、Arc、圆/椭圆、Pie等地物类型。在此基类中,构造了所有地物都具有的基本属性:坐标点链表。
	从CGeoObject派生出CGeoLine,此类是用来描述由两个和两个以上坐标点构成的强调长度、不强调面积的地物类型;从此类可以派生出CGeoSimpleLine(由两点构成的单线)、CGeoSegmentLine(二个以上点构成的线地物)、CGeoPolyline(封闭线)、CGeoParallelLine(平行线)等。
	CGeoSmoothLine是从CGeoLine派生出的光滑曲线的地物类,它的坐标点链表中存储的是原始的控制点信息,然后通过一个Build()纯虚函数,在其派生类中实现插值,根据指定的阶数,由控制点插值生成TGeoCurve类实例,即生成光滑曲线的插值坐标点。
	CGeoSpline和CGeoBezier是从CGeoSmoothLine派生的样条曲线和贝塞尔曲线的类定义。











	以下为VC中实现的以上类结构定义:

class CGeoObject
{
public:
	CGeoRect rect;
	vector<CGeoPoint*> ptList;
	
};

class CGeoPoint : public CGeoObject
{
public:
	double dx, dy, dz;
};
//线地物类定义

class CGeoLine : public CGeoObject
{};

class CGeoCurve;
//光滑曲线类定义
class CGeoSmoothLine : public CGeoLine
{
public:
	vector<CGeoCurve*> curvePts;			//曲线段链表
public:
	CGeoSmoothLine();
	virtual void Build() = 0;							//插值
};

//曲线段定义
class CGeoCurve 
{
public:
	CGeoCurve();
};

//样条曲线类定义
class CSpline : public CGeoSmoothLine
{
public:
	int nFactor;
public:
	CSpline();
	virtual ~CSpline() {};
	void Initialize() {};
	void Generate() {};
	void MatrixSolve() {};
	void MatrixSolveEx() {};
	virtual void Build() {};							//样条插值
};

//贝塞尔曲线类定义
class CGeoBezier : public CGeoSmoothLine
{
public:
	int nSmoothFactor;		//插值光滑度
public:
	CGeoBezier();			//构造函数	
	double GetBinomialCoefficient(int m, int i) {};		//获得多项式系数
	virtual void Build() {};								//贝塞尔曲线插值
};

以下为样条曲线的插值算法:

	void TGeoSpline::Generate() 
	{
		float AMag , AMagOld;
    	// vector A
		for(int i= 0 ; i<=NP-2 ; i++ ) 
		{
			Ax[i] = Px[i+1] - Px[i];
			Ay[i] = Py[i+1] - Py[i];
		}
		// k
		AMagOld = (float)sqrt(Ax[0]*Ax[0] + Ay[0]*Ay[0]);
		for(i=0 ; i<=NP-3 ; i++) 
		{
			AMag = (float)sqrt(Ax[i+1]*Ax[i+1] + Ay[i+1]*Ay[i+1]);
			k[i] = AMagOld / AMag;
			AMagOld = AMag;
		}
		k[NP-2] = 1.0f;

		// Matrix
		for(i=1; i<=NP-2;i++) 
		{
			Mat[0][i] = 1.0f;
			Mat[1][i] = 2.0f*k[i-1]*(1.0f + k[i-1]);
			Mat[2][i] = k[i-1]*k[i-1]*k[i];
		}
		Mat[1][0] = 2.0f;
		Mat[2][0] = k[0];
		Mat[0][NP-1] = 1.0f;
		Mat[1][NP-1] = 2.0f*k[NP-2];

		// 
		for(i=1; i<=NP-2;i++) 
		{
			Bx[i] = 3.0f*(Ax[i-1] + k[i-1]*k[i-1]*Ax[i]);
			By[i] = 3.0f*(Ay[i-1] + k[i-1]*k[i-1]*Ay[i]);
		}
		Bx[0] = 3.0f*Ax[0];
		By[0] = 3.0f*Ay[0];
		Bx[NP-1] = 3.0f*Ax[NP-2];
		By[NP-1] = 3.0f*Ay[NP-2];

		//
		MatrixSolve(Bx);
		MatrixSolve(By);

		for(i=0 ; i<=NP-2 ; i++ ) 
		{
			Cx[i] = k[i]*Bx[i+1];
			Cy[i] = k[i]*By[i+1];
		}
	}

                                

查看回复