貝塞爾曲線算法

貝賽爾曲線的拆分是指將貝賽爾曲線分解成逼近的多邊形。可以用來判斷貝賽爾曲線的選中，以及顯示貝賽爾曲線的旋轉效果等。

貝賽爾曲線簡單介紹：
貝賽爾曲線的每一個頂點都有兩個控制點，用於控制在該頂點兩側的曲線的弧度。所以本函式的頂點數組的記錄方式是：控制點+頂點+控制點+控制點+頂點+控制點+……。所以兩個頂點之間的曲線是由兩個頂點以及兩個頂點之間的控制點來決定的。
==主函式PolyBezierToPolys==
【主要類型申明】
typedef CArray<CPoint,CPoint> CPtArray;//點動態數組類型
【參數說明】
bezierPts&#91;in&#93;---貝賽爾曲線頂點和控制點數組
bClose&#91;in&#93;------是否封閉的貝賽爾曲線
polyPt&#91;out&#93;-----拆分後的多邊形點數組
precision&#91;in&#93;---拆分精度
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,apt,precision); //拆分每一段
polyPt.Append(apt);//拆分完成，加入數組
}
//如果是封閉曲線，那么需要將最後一個頂點和第一個頂點以及最後一個控制點以及第一個控制點組成一組進行拆分
if(bClose){
CPoint ptBuffer&#91;4&#93;;
ptBuffer&#91;0&#93; = bezierPts&#91;count-2&#93;;
ptBuffer&#91;1&#93; = bezierPts&#91;count-1&#93;;
ptBuffer&#91;2&#93; = bezierPts&#91;0&#93;;
ptBuffer&#91;3&#93; = bezierPts&#91;1&#93;;
BezierToPoly(&ptBuffer&#91;0&#93;, apt,precision);
polyPt.Append(apt);
}
count = polyPt.GetSize();
i=0;
//過濾相鄰的值相等的點（由於精度和誤差，可能會有一些坐標值相同的相鄰拆分點）
while(i<count-1){
if(polyPt ==polyPt&#91;i+1&#93;){
polyPt.RemoveAt(i+1);
count--;
continue;
}
i++;
}
return true;
}
//拆分貝賽爾曲線
bool InciseBezier(CPoint *pSrcPt, CPoint *pDstPt)
{
CPoint buffer&#91;3&#93;&#91;3&#93;;
int i;
for(i=0;i<3;i++){
buffer&#91;0&#93; = pSrcPt + pSrcPt&#91;i+1&#93;;
buffer&#91;0&#93;.x /=2;
buffer&#91;0&#93;.y /=2;
}
for(i=0;i<2;i++){
buffer&#91;1&#93; = buffer&#91;0&#93; + buffer&#91;0&#93;&#91;i+1&#93;;
buffer&#91;1&#93;.x /=2;
buffer&#91;1&#93;.y /=2;
}
buffer&#91;2&#93;&#91;0&#93; = buffer&#91;1&#93;&#91;0&#93; + buffer&#91;1&#93;&#91;1&#93;;
buffer&#91;2&#93;&#91;0&#93;.x /=2;
buffer&#91;2&#93;&#91;0&#93;.y /=2;
pDstPt&#91;0&#93;=pSrcPt&#91;0&#93;;
pDstPt&#91;1&#93;=buffer&#91;0&#93;&#91;0&#93;;
pDstPt&#91;2&#93;=buffer&#91;1&#93;&#91;0&#93;;
pDstPt&#91;3&#93;=buffer&#91;2&#93;&#91;0&#93;;
pDstPt&#91;4&#93;=buffer&#91;1&#93;&#91;1&#93;;
pDstPt&#91;5&#93;=buffer&#91;0&#93;&#91;2&#93;;
pDstPt&#91;6&#93;=pSrcPt&#91;3&#93;;
return true;
}
//拆分一組貝賽爾曲線段
bool BezierToPoly(CPoint *pSrcPts,CPtArray &polyPt,int precision)
{
polyPt.RemoveAll();
polyPt.SetSize(4);
polyPt&#91;0&#93; = pSrcPts&#91;0&#93;;
polyPt&#91;1&#93; = pSrcPts&#91;1&#93;;
polyPt&#91;2&#93; = pSrcPts&#91;2&#93;;
polyPt&#91;3&#93; = pSrcPts&#91;3&#93;;
CPoint ptBuffer&#91;7&#93;;
int i,j,count =4;
bool bExit;
while(true){
bExit = true;
for(i=0;i<count-1;i+=3){
// if(GetBezierGap(&polyPt)>precision){
if(!EndBezierCut(&polyPt, precision)){
bExit = false;
InciseBezier(&polyPt, ptBuffer);
polyPt.RemoveAt(i+1,2);
polyPt.InsertAt(i+1,ptBuffer&#91;1&#93;,5);
for(j=0;j<4;j++)
polyPt&#91;i+2+j&#93; = ptBuffer&#91;2+j&#93;;
i += 3;
count += 3;
}
}
if(bExit)
break;
}
count = polyPt.GetSize();
i=0;
while(i<count-1){
if(polyPt ==polyPt&#91;i+1&#93;){
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.x-p&#91;i-1&#93;.x)>gap)
gap=abs(p.x-p&#91;i-1&#93;.x);
if(abs(p.y-p&#91;i-1&#93;.y)>gap)
gap=abs(p.y-p&#91;i-1&#93;.y);
}
return gap;
}
//判斷是否可以終止更精細得拆分
bool EndBezierCut(CPoint *ptBezier, int nExtent)
{
double C,dx,dy,delt,delt1,delt2;
if (nExtent<2)
nExtent = 2;
dx = (double)(ptBezier&#91;3&#93;.x - ptBezier&#91;0&#93;.x);
dy = (double)(ptBezier&#91;3&#93;.y - ptBezier&#91;0&#93;.y);
C = dx * ptBezier&#91;0&#93;.y - dy * ptBezier&#91;0&#93;.x;
delt = (double)nExtent*nExtent*(dy*dy+dx*dx);
delt1 = dy * ptBezier&#91;1&#93;.x - dx * ptBezier&#91;1&#93;.y + C;
delt2 = dy * ptBezier&#91;2&#93;.x - dx * ptBezier&#91;2&#93;.y + C;
delt1 = delt1 * delt1;
delt2 = delt2 * delt2;
if (delt1 > delt || delt2 > delt)
return FALSE;
else
return TRUE;
}