贝赛尔曲线的拆分算法

贝赛尔曲线的拆分是指将贝赛尔曲线分解成逼近的多边形。可以用来判断贝赛尔曲线的选中，以及显示贝赛尔曲线的旋转效果等。

 贝赛尔曲线简单介绍：

 贝赛尔曲线的每一个顶点都有两个控制点，用于控制在该顶点两侧的曲线的弧度。所以本函数的顶点数组的记录方式是：控制点＋顶点＋控制点＋控制点＋顶点＋控制点＋……。所以两个顶点之间的曲线是由两个顶点以及两个顶点之间的控制点来决定的。

 ＝＝主函数PolyBezierToPolys＝＝

 【主要类型申明】

  typedef CArray<CPoint,CPoint> CPtArray;//点动态数组类型

 【参数说明】

    bezierPts[in]---贝赛尔曲线顶点和控制点数组

    bClose[in]------是否封闭的贝赛尔曲线

 polyPt[out]-----拆分后的多边形点数组

 precision[in]---拆分精度

 bool PolyBezierToPolys(CPtArray &bezierPts,

           bool bClose,CPtArray &polyPt,int precision)

 {

    polyPt.RemoveAll();

    CPtArray apt;

    int i,count = bezierPts.GetSize();

 //从1开始，是因为第一个是控制点，如果曲线不封闭，那么第一个控制点是没有用的。

 //每一段贝赛尔曲线由相邻的两个顶点和之间的两个控制点决定，所以频率为3（后一个顶点在下一组中还要使用）

    for(i=1;i<count-2;i+=3){  

    BezierToPoly(&bezierPts[i],apt,precision); //拆分每一段

 polyPt.Append(apt);//拆分完成，加入数组

    }

    //如果是封闭曲线，那么需要将最后一个顶点和第一个顶点以及最后一个控制点以及第一个控制点组成一组进行拆分

    if(bClose){

       CPoint ptBuffer[4];

       ptBuffer[0] = bezierPts[count-2];

       ptBuffer[1] = bezierPts[count-1];

       ptBuffer[2] = bezierPts[0];

ptBuffer[3] = bezierPts[1];

       BezierToPoly(&ptBuffer[0], apt,precision);

       polyPt.Append(apt);

    }

    count = polyPt.GetSize();

    i=0;

  //过滤相邻的值相等的点（由于精度和误差，可能会有一些坐标值相同的相邻拆分点）

    while(i<count-1){

       if(polyPt[i] ==polyPt[i+1]){

           polyPt.RemoveAt(i+1);

           count--;

           continue;

       }

       i++;

    }

    return true;

 }

 //拆分贝赛尔曲线

 bool InciseBezier(CPoint *pSrcPt, CPoint *pDstPt)

 {

    CPoint buffer[3][3];

    int i;

    for(i=0;i<3;i++){

       buffer[0][i] = pSrcPt[i] + pSrcPt[i+1];

       buffer[0][i].x /=2;

       buffer[0][i].y /=2;

    }

    for(i=0;i<2;i++){

       buffer[1][i] = buffer[0][i] + buffer[0][i+1];

       buffer[1][i].x /=2;

buffer[1][i].y /=2;

    }

    buffer[2][0] = buffer[1][0] + buffer[1][1];

    buffer[2][0].x /=2;

    buffer[2][0].y /=2;

    pDstPt[0]=pSrcPt[0];

    pDstPt[1]=buffer[0][0];

    pDstPt[2]=buffer[1][0];

    pDstPt[3]=buffer[2][0];

    pDstPt[4]=buffer[1][1];

    pDstPt[5]=buffer[0][2];

    pDstPt[6]=pSrcPt[3];

    return true;

 }

 //拆分一组贝赛尔曲线段

 bool BezierToPoly(CPoint *pSrcPts,CPtArray &polyPt,int precision)

 {

    polyPt.RemoveAll();

    polyPt.SetSize(4);

    polyPt[0] = pSrcPts[0];

    polyPt[1] = pSrcPts[1];

    polyPt[2] = pSrcPts[2];

    polyPt[3] = pSrcPts[3];

    CPoint ptBuffer[7];

    int i,j,count =4;

    bool bExit;

    while(true){

       bExit = true;

       for(i=0;i<count-1;i+=3){

 //          if(GetBezierGap(&polyPt[i])>precision){

           if(!EndBezierCut(&polyPt[i], precision)){

              bExit = false;

InciseBezier(&polyPt[i], ptBuffer);

              polyPt.RemoveAt(i+1,2);

              polyPt.InsertAt(i+1,ptBuffer[1],5);

              for(j=0;j<4;j++)

                  polyPt[i+2+j] = ptBuffer[2+j];

              i += 3;

              count += 3;

           }

       }

       if(bExit)

           break;

    }

    count = polyPt.GetSize();

    i=0;

    while(i<count-1){

       if(polyPt[i] ==polyPt[i+1]){

           polyPt.RemoveAt(i+1);

           count--;

           continue;

       }

       i++;

    }

    return true;

 }

 /计算贝赛尔曲线两个顶点的纵向和横向的最大距离

 int GetBezierGap(CPoint *p)

 {

    int gap = 0;

    for(int i=1;i<4;i++){

       if(abs(p[i].x-p[i-1].x)>gap)

gap=abs(p[i].x-p[i-1].x);

       if(abs(p[i].y-p[i-1].y)>gap)

           gap=abs(p[i].y-p[i-1].y);

    }

    return gap;

 }

 //判断是否可以终止更精细得拆分

 bool EndBezierCut(CPoint *ptBezier, int nExtent)

 {

 double C,dx,dy,delt,delt1,delt2;

 if (nExtent<2)

   nExtent = 2;

 dx = (double)(ptBezier[3].x - ptBezier[0].x);

 dy = (double)(ptBezier[3].y - ptBezier[0].y);

 C = dx * ptBezier[0].y - dy * ptBezier[0].x;

 delt = (double)nExtent*nExtent*(dy*dy+dx*dx);

 delt1 = dy * ptBezier[1].x - dx * ptBezier[1].y + C;

 delt2 = dy * ptBezier[2].x - dx * ptBezier[2].y + C;

 delt1 = delt1 * delt1;

 delt2 = delt2 * delt2;

 if (delt1 > delt || delt2 > delt)

  return FALSE;

 else

  return TRUE;

 }

原文转自：http://www.ltesting.net