正多邊形和心臟線生成算法

摘要：對于正多邊形和心臟線圖形的生成，本文給出了新的遞推公式，并以該公式為基礎構造了正多邊形和心臟線的生成算法;該算法在等分角度的設定下，計算正多邊形每對頂點需要2次乘法運算，計算心臟線每對點需要4次乘法運算，算法避免了大量的三角函數運算因而效率較高。用VB編寫程序對算法進行了驗證，算法具有一定的實用價值。

關鍵詞：正多邊形;心臟線;構造;算法;遞推公式

中圖分類號：TP391 ? ? 文獻標識碼：A

文章編號：1009-3044（2021）35-0127-02

1 正多邊形算法設計

1.1 正多邊形算法遞推公式的構造

r為正多邊形外接圓半徑，圓心與直角坐標系下的原點[o]重合。假設把圓周角[m]等份，每份對應的角度[θ=2π/m]。沿[x]軸的正方向逆時針方向順次在圓上取點，相鄰兩點圓弧對應的圓心角為[θ]。初始時，取[x0=0，y0=r;] [x1=rcos（θ），] [y1=rsin（θ）]。

[xn=rcos（nθ）]

[yn=rsin（nθ）]

根據前面兩對點的坐標值，可推導出新的一個點的坐標。下面推出遞推公式：

[xn+2=rcos（（n+2）θ）] ? ?[=rcos（（n+1）θ）cos（θ）-rsin（（n+1）θ）sin（θ）=2rcos（θ）cos（（n+1）θ）-r（cos（（n+1）θ）cos（θ）+sin（（n+1）θ）sin（θ）=2rcos（θ）cos（（n+1）θ）-rcos（nθ）=2cos（θ）xn+1-xn]

[yn+2=rsin（（n+2）θ）] ? ?[=rsin（（n+1）θ）cos（θ）+rcos（（n+1）θ）sin（θ）=2rcos（θ）sin（（n+1）θ）-r（sin（（n+1）θ）cos（θ）-cos（（n+1）θ）sin（θ））=2rcos（θ）sin（（n+1）θ）-rsin（nθ）=2cos（θ）yn+1-yn]

r為正多邊形外接圓半徑，m為多邊形的邊數，color為生成多邊形所用的顏色。t為每一條邊對應圓心角值。初始化后每次循環生成一對點畫一條線，直到執行m-1次循環。

1.2 正多邊形的生成算法

Pcreat（r，m，color）

int r，m，color;

{

int i，cx，cy;

float xn0，yn0，xn1，yn1，xn2，yn2，pi，t，d;

pi=3.1415927; ? ? ? ? ? ? ? ? ? ?/*pi是圓周率*/

t=2*pi/m;

d=2*cos（t）; ? ? ? ? ? ? ? ? ? ? ?/*t為上面遞推公式中的等分角度*/

xn0=0; ? ? ? ? ? ? ? ? ?   ? ? /*（xn0，yn0），第1對起始點初始化*/

yn0=r;

xn1=r*cos（t）; ? ? ? ? ? ? ? ? ? ?/*（xn1，yn1），第2對起始點初始化*/

yn1=r*sin（t）;

line （xn0，yn0）-（xn1，yn1），color; ? ? ?/*兩對起始點以color顏色畫線*/

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

{

xn2=d*xn1-xn0; ? ? ? ? ? ? ? ? /*計算新的一對坐標（xn2，yn2）*/

yn2=d*yn1-yn0;

Line （xn2，yn2）-（xn1，yn1），color; ? ? /*兩對點以color顏色畫線*/

xn0=xn1;

yn0=yn1;

xn1=xn2;

yn1=yn2;

}

}/*pcreat*/

1.3 正多邊形應用實例輸出

用VB6.0編寫程序得到圖1。

1.4 正多邊形算法分析

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

2 心臟線算法設計

2.1 心臟線遞推公式構造

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

[x=acosθ（1+cosθ））y=asinθ（1+cosθ），θ∈0，2π]

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

變換上式可得：

[x=acosθ+a2·cos2θ+a2y=asinθ+a2·sin2θ]

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

為表達遞推公式方便，令[f（n）=acos（n?t），g（n）=asin（n?t），]其中0≤n≤m。[f1（n）=a2·cos（n?2t），g1（n）=a2·sin（n?2t），]其中0≤n≤m。

采用與正多邊類似的構造方法，可構造出心臟線算法。

2.2 心臟線生成算法

Stancu （a，m，color）

int a， m， color;

{

int i;

float xn1， xn2， yn1， yn2， xm1， xm2， ym1， ym2 ;

float pi， t， t2， u， d， d2， x， y;

pi = 3.14159;

cx = 800.5;

cy = 1500.5;

a = 1000;

m = 1000;

t = 2 * pi / m;

t2 = 2 * t;

u = a / 2;

d = 2 * Cos（t）;

d2 = 2 * Cos（t2）;

xn0 = a * Cos（0）;

yn0 = a * Sin（0）;

xm0 = a / 2 * Cos（0）;

ym0 = a / 2 * Sin（0）;

x = xn0 + xm0 + u; ? ? ? ? ? ? /*（x，y），第1對起始點初始化*/

y = yn0 + ym0;

drawpixel （ int（x）， int（y），color）; ? /*顯示第1個點*/

xn1 = a * Cos（t）;

yn1 = a * Sin（t）;

xm1 = a / 2 * Cos（t2）;

ym1 = a / 2 * Sin（t2）;

x = xn1 + xm1 + u; ? ? ? ? ? ? /*第2對起始點初始化*/

y = yn1 + ym1;

drawpixel （ int（x）， int（y），color）; ? /*顯示第2個點*/

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

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

yn2 = d * yn1 - yn0;

xm2 = d2 * xm1 - xm0;

ym2 = d2 * ym1 - ym0;

x = xn2 + xm2 + u;

y = yn2 + ym2;

drawpixel （ int（x）， int（y），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）;yn0，yn1，yn2對應g1（n），g1（n+1）和g1（n+2）。

2.3 心臟線應用實例輸出

用VB6.0編寫程序得到圖2的輸出，其中，a=1000，m=1500。

2.4 心臟線算法分析

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

3 結束語

本文給出了正多邊形和心臟線的逐點生成算法，并且已經編寫了程序進行了驗證。算法具有構造簡單，執行速度較快的特點。通過構造遞推公式的方法避免了大量的三角函數運算，算法中乘法運算次數也較少，因此算法效率較高。遞推公式的構造方法也可以應用于類似的其他問題中，對于基于角度的圖像繪制算法的研究具有參考意義。

參考文獻：

[1] 李星秀，康寶生.玫瑰線和普通旋輪線的逐點生成算法[J].計算機工程與設計，2006，27（5）：746-748.

[2] 劉勇奎.直線與曲線的逐點生成算法[J].工程圖學學報，2005，26（6）：41-51.

[3] 張博.圓的高質量、快速生成算法[J].計算機應用與軟件，1994，11（2）：51-56.

[4] 譚浩強.Visual Basic程序設計[M].北京：清華大學出版社，2004.

[5] 嚴蔚敏，吳偉民.數據結構：C語言版[M].北京：清華大學出版社，1997.

[6] 張博.普通旋輪線和玫瑰線的逐點生成新算法[J].計算機時代，2014（9）：54-56.

【通聯編輯：梁書】