普通旋輪線和玫瑰線的逐點生成新算法

摘 要： 構造了普通旋輪線和玫瑰線逐點生成的遞推公式并給出算法。算法中避免了三角函數運算，計算普通旋輪線上每對繪圖點只需要2次乘法運算；計算玫瑰線上每對繪圖點只需要4次乘法運算，算法效率有很大提升。利用所給出的構造方法和分析方法，也可以構造出圓和心臟線等圖形的生成算法，因此，本文對于基于角度的圖形繪制算法研究具有參考意義。

關鍵詞： 普通旋輪線； 玫瑰線； 逐點生成算法； 遞推公式； 構造方法

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2014）09-54-03

0 引言

對于極坐標表示的曲線和含有三角函數的參數方程表示的曲線，生成曲線時要用到三角函數運算，繪圖時如直接進行計算，計算量太大。常用方法是采用角度作為增量，通過構造遞推公式計算新的坐標點，這樣可減少運算量。

文獻[2]給出玫瑰線和普通旋輪線的逐點生成算法，計算每個點分別需要2次乘法，計算每對輸出點分別需要4次乘法運算。本文通過構造新的遞推公式，使得算法的執行速度更快，生成普通旋輪線每對繪圖點，只需2次乘法；生成玫瑰線每對繪圖點，只需4次乘法，乘法的運算次數減少了。文獻[3]給出了心臟線的逐點生成算法，若采用本文給出的構造方法，可使乘法運算次數減少一半。

1 構造遞推公式用到的兩個恒等式

⑴ 已知：α，β為角度，求證：cos（α+2β）=2cos（β）cos（α+β）-cos（α）

證明：2cos（β）cos（α+β）-cos（α）

=2cos（β）（cos（α）cos（β）-sin（α）sin（β））-cos（α）

=2cos2（β）cos（α）-cos（α）-2sin（α）sin（β）cos（β）

=cos（α）cos（2β）-sin（α）sin（2β）

=cos（α+2β）

原式成立。

⑵ 已知：α，β為角度，求證：sin（α+2β）=2cos（β）sin（α+β）-sin（α）

證明：2cos（β）sin（α+β）-sin（α）

=2cos（β）（sin（α）cos（β）+cos（α）sin（β））-sin（α）

=2cos2（β）sin（α）-sin（α）+2cos（β）sin（β）cos（α）

=sin（α）+cos（2β）+cos（α）sin（2β）

=sin（α+2β）

原式成立。

2 普通旋輪線

2.1 遞推公式構造

在直角坐標系中，普通旋輪線的參數方程為：

其中，x，y的單位為像素。

把以上區間分成m份，每份的角度為：。當θ=kt時（k=0，1，…，m），分別計算出x和y的值。

為表達遞推公式方便，令f（n）=rcos（n·t），g（n）=rsin（n·t），其中0≤n≤m。

令α=n·t，β=t，以上兩個恒等式變為：

兩邊同時乘以r，可得遞推公式：

f（n+2）=2cos（t）·f（n+1）-f（n）

g（n+2）=2cos（t）·g（n+1）-g（n）

初始化計算以下各式的值，

f（0）=rcos（0），g（0）=rsin（0）。

f（1）=rcos（t），g（1）=rsin（t）。

由遞推公式計算新的f（n）和g（n），再按公式進行加法運算就可得到對應的x和y值。

2.2 算法

Cycloid （r， m， color）

int r， m， color；

{ int i；

float pi， v， t， u， d， xn0， xn1， xn2， yn0， yn1， yn2， x， y；

pi=3.14159；

r=400；

m=400；

t=2*pi/m；

d=2*Cos（t）；

xn0=r*Cos（0）； /*初始化計算第一個點*/

yn0=r*Sin（0）；

x=-yn0；

y=r-xn0；

drawpixel（int（x+0.5）， int（y+0.5）， color）； /*顯示第一個點*/

xn1=r*Cos（t）； /*初始化計算第二個點*/

yn1=r*Sin（t）；

v=r*t； /*用v來構造rθ*/

u=r*t； /*u存放rθ的增量*/

x=v-yn1；

y=r-xn1；

drawpixel （int（x+0.5）， int（y+0.5）， color）； /*顯示第二個點*/

for（i=2； i<=m； i++）；

{ v=v+u；

xn2=d*xn1-xn0； /*計算新的點*/

yn2=d*yn1-yn0；

x=v-yn2；

y=r-xn2；

drawpixel （ int（x+0.5）， int（y+0.5），color）；

xn0=xn1；

yn0=yn1；

xn1=xn2；

yn1=yn2；

}

} /*Cycloid*/

xn0，xn1，xn2對應f（n），f（n+1）和f（n+2）；yn0，yn1，yn2對應g（n），g（n+1）和g（n+2）。v用來構造r·n·t。x，y為要顯示點的橫縱坐標值。

2.3 運行結果

用VB6.0編寫程序得到輸出如圖1，共顯示三個周期，其中，r=400，m=400。

2.4 算法分析

算法速度取決于取點數的多少和計算每個點的計算量。初始化后，計算每對繪圖點需要2次乘法運算。計算m個繪圖點需要2m次乘法運算。

3 玫瑰線

3.1 遞推公式構造

玫瑰線的極坐標方程為ρ=αsinkθ，θ∈[0，2π]，其中，θ為弧度，k為常數。

在直角坐標系中，玫瑰線的參數方程為：

其中，x，y為單位像素。

變換上式可得：

假設把以上區間分成m份，每份的角度為：。當θ=kt時（k=0，1，…，m），分別計算出x和y的值。

為表達遞推公式，令f（n）=cos（n·（k+1）·t），g（n）=sin（n·（k+1）·t），其中0≤n≤m。f1（n）=cos（n·（k-1）·t），g1（n）=sin（n·（k-1）·t），其中0≤n≤m。

構造表達式與普通螺旋線采用的方法相同。

3.2 算法

Stancu （a， m， color）

int a， m， color；

{ int i；

float xn0，xn1， xn2，yn0， yn1， yn2， xm0，xm1， xm2， ym0，ym1， ym2；

float pi， k， t， t2， d， d2， x， y；

pi=3.14159；

k=2； /*極坐標方程中的k*/

a=2000；

m=1000；

t=（k+1）*（2*pi/m）；

t2=（k-1）*（2*pi/m）；

d=2*Cos（t）；

d2=2*Cos（t2）；

xn0=a/2*Cos（0）； /*初始化計算第一個點，此時n=0*/

yn0=a/2*Sin（0）；

xm0=a/2*Cos（0）；

ym0=a/2*Sin（0）；

x=yn0+ym0；

y=-xn0+xm0；

drawpixel （int（x+0.5）， int（y+0.5），color）； /*顯示第一個點*/

xn1=a/2*Cos（t）； /*初始化計算第二個點，此時n=1*/

yn1=a/2*Sin（t）；

xm1=a/2*Cos（t2）；

ym1=a/2*Sin（t2）；

x=yn1+ym1；

y=-xn1+xm1；

drawpixel （int（x+0.5）， int（y+0.5）， color）； /*顯示第二個點*/

for（i=2； i<=m； i++）

xn2=d*xn1-xn0； /*計算新的點*/

yn2=d*yn1-yn0；

xm2=d2*xm1-xm0；

ym2=d2*ym1-ym0；

x=yn2+ym2；

y=-xn2+xm2；

drawpixel （int（x+0.5）， int（y+0.5），color）；

xn0=xn1；

yn0=yn1；

xn1=xn2；

yn1=yn2；

xm0=xm1；

ym0=ym1；

xm1=xm2；

ym1=ym2；

}

} /*Stancu*/

xn0，xn1，xn2對應f（n），f（n+1）和f（n+2）；yn0，yn1，yn2對應g（n），g（n+1）和g（n+2）。xm0，xm1，xm2對應f1（n），f1（n+1）和f1（n+2）；ym0，ym1，ym2對應g1（n），g1（n+1）和g1（n+2）。

4 運行結果

用VB6.0編寫程序得到輸出如圖2，其中從左到右k分別取值2、3和4。選取不同的k可得到各種美觀的圖形。

5 算法分析

算法速度取決于取點數的多少和計算每個點的計算量。初始化后，計算每對繪圖點需要4次乘法運算。計算m個繪圖點需要4m次乘法運算。

6 結束語

本文給出的普通旋輪線和玫瑰線的逐點生成算法，已經編寫程序并進行了驗證。算法中乘法次數較少，且通過構造遞推公式的方法避免了大量的三角函數運算，因此運算速度快。遞推公式構造簡單、規律性強，很容易編寫程序實現。按照此方法也可構造出圓和心臟線等圖形的生成算法。

本文的研究對于基于角度的圖形繪制算法研究具有參考意義。

參考文獻：

[1] 孫家廣等.計算機圖形學[M].清華大學出版社，1998.

[2] 李星秀，康寶生.玫瑰線和普通旋輪線的逐點生成算法[J].計算機工

程與設計，2006.3：746-748

[3] 林芳.心臟線的逐點生成算法[J].寧夏大學學報，2006.3：25-26

[4] 劉勇奎.直線與曲線的逐點生成算法[J].工程圖學學報，2005.6：

41-50

[5] 張博.圓的高質量、快速生成算法[J].計算機應用與軟件，1994.2：

51-55

[6] 張志剛，周明全.一種輪廓曲線的多邊形近似算法[J].計算機應用，

2006.3：577-578

[7] 張博等.中點生成橢圓的整數型算法[J].工程圖學學報，2011.1：1-4

[8] 王棟.Visual Basic程序設計[M].清華大學出版社，2002.

[9] 嚴偉敏，吳偉民.數據結構[M].清華大學出版社，1997.