一種新的Sierpiński三角分形生成算法

趙向東，江瑤，馬中華

一種新的Sierpiński三角分形生成算法

趙向東，江瑤，馬中華

（天津職業(yè)技術(shù)師范大學(xué) 理學(xué)院，天津 300222）

介紹6向鏈碼及Sierpiński三角分形相關(guān)基礎(chǔ)理論，將6向鏈碼技術(shù)應(yīng)用于Sierpiński三角分形，提出了一種新的Sierpiński三角分形算法．與經(jīng)典的Sierpiński三角分形算法相比，6向鏈碼方法在構(gòu)造經(jīng)典分形圖形——Sierpiński三角分形時，更易實現(xiàn)，效率更高．

6向鏈碼；Sierpiński三角；分形

1　引言及預(yù)備知識

Sierpiński三角分形是分形幾何中一種最典型的分形幾何圖形，是一種典型的自相似集三角分形，其廣泛應(yīng)用于化學(xué)分子結(jié)構(gòu)、地毯構(gòu)成、計算科學(xué)和工程等研究領(lǐng)域[1-4]．

鏈碼（又稱為Freeman碼）方法是美國學(xué)者Freeman于1961年提出的，是一種用于表示任意幾何曲線構(gòu)型的方法，其實質(zhì)是一串指向符序列，用曲線起始點坐標和邊界點方向符來描述曲線或邊界的方法[5]，常被用于計算機圖形學(xué)和模式識別等領(lǐng)域[6-7]．高榮華[8]等利用頂點鏈碼的方法計算了區(qū)域的面積；王平[9]等基于Freeman鏈碼提出了直線識別算法；劉勇奎[10]等研究了壓縮鏈碼；余博[11]等基于Freeman碼方法提出了曲線匹配方法，其方法簡單易于實現(xiàn)，且不受曲線旋轉(zhuǎn)和縮放影響．

近年來，鏈碼方法的研究和應(yīng)用已相當成熟，文獻[12]基于鏈碼方法提出了串珠編織路徑算法，文獻[13]提出了Freeman鏈碼技術(shù)的幾何圖形識別算法．因此，F(xiàn)reeman鏈碼方法在處理圖像圖形學(xué)中有著廣泛的應(yīng)用價值．

常用的Freeman鏈碼按照中心像素點鄰接方向個數(shù)可分為4 向鏈碼（見圖1）和8向鏈碼（見圖2）．

圖1 4向鏈碼

圖2 8向鏈碼

6向鏈碼相比于4向鏈碼和8向鏈碼具有良好的連通性，且在圖像處理算法中易于實現(xiàn)，因此，諸多學(xué)者也對6向鏈碼進行了深入研究．劉勇奎[14]提出了6向鏈碼上的橢圓生成算法、圓弧生成算法以及輪廓跟蹤算法；文獻[15]將6向鏈碼應(yīng)用于六邊形的串珠編織路徑中，并提出了相應(yīng)的算法；文獻[16]提出了基于6向鏈碼的Koch曲線生成算法；文獻[17]進一步深入研究了六邊形網(wǎng)格鏈碼方法．本文基于6向鏈碼方法，提出一種新的Sierpiński三角分形算法，且和經(jīng)典的Sierpiński三角分形算法——遞歸算法、D0L系統(tǒng)算法、多規(guī)則LS文法進行了對比，分析其程序運行效率．結(jié)果表明，新的算法更易實現(xiàn)，效率更高．

本文只給出6向鏈碼及Sierpiński三角分形的定義，詳細基礎(chǔ)理論知識見文獻[18-19]．

圖3 6向鏈碼圖

圖4 6向鏈碼串實例

圖5 Sierpiński三角分形生成過程

2　算法介紹

2.1　6向鏈碼仿真Sierpiński三角分形算法描述

圖6 6向鏈碼和坐標之間旋轉(zhuǎn)關(guān)系

基于6向鏈碼法的Sierpiński三角分形算法步驟為：

2.2　仿真實驗結(jié)果

為了能夠更好地確保算法的正確性，進一步地，可以利用經(jīng)典的Sierpiński三角分形算法——遞歸算法，在相同的迭代次數(shù)下進行驗證，其仿真結(jié)果與圖7 一致（見圖 8），主要區(qū)別是在相同迭代次數(shù)下迭代時間不同．

圖7 6向鏈碼法仿真Sierpiński三角分形

圖8 遞歸算法仿真Sierpiński三角分形

圖9 6向鏈碼法()仿真Sierpiński三角分形

3 　Sierpiński三角分形算法性能對比

在不同的迭代次數(shù)下，計算算法的平均運行時間，通過與遞歸算法[18]19、D0L系統(tǒng)算法[19]59對比，可分析得出6向鏈碼法在繪制Sierpiński三角分形墊片時的性能（見表1）．

表1 6向鏈碼法與經(jīng)典算法性能對比 s

表2 6向鏈碼法與多規(guī)則LS文法性能對比 s

綜上可知，6向鏈碼法在繪制Sierpiński三角分形方面，具有容易實現(xiàn)，程序運行效率高的優(yōu)點．

4　結(jié)語

本文介紹了6向鏈碼，并將6向鏈碼與經(jīng)典分形幾何圖形——Sierpiński三角分形構(gòu)造原理相結(jié)合，給出了一種新的基于6向鏈碼技術(shù)構(gòu)造Sierpiński三角分形的算法．為了更好地測試6向鏈碼方法的性能，選取經(jīng)典的Sierpiński三角分形算法——遞歸算法、D0L系統(tǒng)法以及多規(guī)則LS文法，在不同迭代次數(shù)下，對運行時間進行了對比分析，得出了6向鏈碼在Sierpiński三角分形構(gòu)造中的優(yōu)勢——易于實現(xiàn)，程序效率高．

[1] 張珍，謝文俊，楊奕，等．基于鹵鍵的謝爾賓斯基三角分形自組裝的模擬研究[J]．物理化學(xué)學(xué)報，2017，33（3）：539-547

[2] 王燕．基于謝爾賓斯基三角分形壓電振子的性能研究[D]．南京：南京郵電大學(xué)，2016

[3] 王麗．三分謝爾賓斯基墊片上的標準拉普拉斯算子[J]．江蘇理工學(xué)院學(xué)報，2014，20（6）：13-17

[4] 王書穎，范欽杰．一類描述Sierpinski（謝爾賓斯基）墊的擬移位映射[J]．吉林師范大學(xué)學(xué)報：自然科學(xué)版，2007（4）：49-51

[5] Freeman H．On the encoding of arbitrary geometric configurations[J]．IRE Transactions on Electronic Computers，1961（2）： 260-268

[6] Freeman H，Davis L S．A corner-finding algorithm for chain-coded curves[J]．IEEE Transactions on computers，1977（3）： 297-303

[7] Freeman H．Computer processing of line-drawing images[J]．ACM Computing Surveys（CSUR），1974，6（1）：57-97

[8] 高榮華，張有會，曹清潔，等．頂點鏈碼表示區(qū)域的面積計算[J]．計算機應(yīng)用與軟件，2005，22（8）：106-108

[9] 王平，董玉德，羅喆帥．基于Freeman鏈碼的直線識別方法[J]．計算機工程，2005，31（10）：171-173

[10] 劉勇奎，魏巍，郭禾．壓縮鏈碼的研究[J]．計算機學(xué)報，2007，30（2）：281-287

[11] 余博，郭雷，趙天云，等．Freeman鏈碼描述的曲線匹配方法[J]．計算機工程與應(yīng)用，2012，48（4）：5-8

[12] 閆建業(yè)，姚立綱，林冬良，等．串珠涼墊編織路徑數(shù)學(xué)建模與仿真[C]//第10屆中國機構(gòu)與機器科學(xué)應(yīng)用國際會議（2013CCAMMS）論文集. 北京: 中國機械工程學(xué)會機械傳動專業(yè)學(xué)會機構(gòu)學(xué)專業(yè)委員會，2013：249-253

[13] 裴姍，章騰．基于 Freeman 鏈碼的幾何圖形識別算法[J]．計算技術(shù)與自動化，2018（3）：21-25

[14] 劉勇奎．計算機圖形學(xué)的基礎(chǔ)算法[M]．2版．北京：科學(xué)出版社，2007：164-183

[15] Zhao X，Sun W，Liu X，et al．On Six Directions Chain Code and Its Application of Bead Weaving[C]//2018 IEEE 4th International Conference on Computer and Communications（ICCC）．成都：四川省電子學(xué)會，2018：2262-2267

[16] Liu X，Ma Z，Zhao X．A Comparison of Algorithms of Drawing the Koch Snowflake Curve[C]//Proceedings of the 3rd International Conference on Computer Science and Application Engineering．New York：Association for Computing Machinery，2019：1-5

[17] 魏小峰，苗雙喜，濮國梁，等．應(yīng)用于六邊形網(wǎng)格的鏈碼方法[J]．武漢大學(xué)學(xué)報：信息科學(xué)版，2019，44（11）：1700-1707

[18] 孫博文．分形算法與程序設(shè)計——Visual C++實現(xiàn)[M]．北京：科學(xué)出版社，2004

[19] 朱華，姬翠翠．分形理論及其應(yīng)用[M]．北京：科學(xué)出版社，2011

A new algorithm for generating Sierpiński triangle fractal

ZHAO Xiangdong，JIANG Yao，MA Zhonghua

（School of Science，Tianjin University of Technology and Education，Tianjin 300222，China）

The basic theory of six direction chain code and Sierpiński triangle fractal correlation are introduced，a new Sierpiński triangle fractal algorithm is proposed by applying the six direction chain code technique to Sierpiński triangle fractal．And compared with the classical Sierpiński triangle fractal algorithm，the six direction chain code method is easier to be implemented and more efficient in constructing the classical fractal graph——Sierpiński triangle fractal.

six direction chain code；Sierpiński triangle；fractal

O189.11

A

10.3969/j.issn.1007-9831.2020.06.002

1007-9831（2020）06-0005-05

2020-04-10

國家自然科學(xué)基金項目（11601391）；天津市自然科學(xué)基金項目（18JCQNJC69700）；天津市高等學(xué)校科技發(fā)展基金計劃項目（JWK1611）；天津職業(yè)技術(shù)師范大學(xué)研究生創(chuàng)新基金項目（YC19-36）

趙向東（1993-），男，甘肅慶陽人，在讀碩士研究生，從事計算代數(shù)幾何研究．E-mail：zxdtute17010@tute.edu.cn