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

趙向東，江瑤，馬中華

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

趙向東，江瑤，馬中華

（天津職業技術師范大學 理學院，天津 300222）

介紹6向鏈碼及Sierpiński三角分形相關基礎理論，將6向鏈碼技術應用于Sierpiński三角分形，提出了一種新的Sierpiński三角分形算法．與經典的Sierpiński三角分形算法相比，6向鏈碼方法在構造經典分形圖形——Sierpiński三角分形時，更易實現，效率更高．

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

1　引言及預備知識

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

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

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

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

圖1 4向鏈碼

圖2 8向鏈碼

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

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

圖3 6向鏈碼圖

圖4 6向鏈碼串實例

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

2　算法介紹

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

圖6 6向鏈碼和坐標之間旋轉關系

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

2.2　仿真實驗結果

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

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

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

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

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

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

表1 6向鏈碼法與經典算法性能對比 s

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

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

4　結語

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

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

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

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

[4] 王書穎，范欽杰．一類描述Sierpinski（謝爾賓斯基）墊的擬移位映射[J]．吉林師范大學學報：自然科學版，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] 高榮華，張有會，曹清潔，等．頂點鏈碼表示區域的面積計算[J]．計算機應用與軟件，2005，22（8）：106-108

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

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

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

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

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

[14] 劉勇奎．計算機圖形學的基礎算法[M]．2版．北京：科學出版社，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）．成都：四川省電子學會，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] 魏小峰，苗雙喜，濮國梁，等．應用于六邊形網格的鏈碼方法[J]．武漢大學學報：信息科學版，2019，44（11）：1700-1707

[18] 孫博文．分形算法與程序設計——Visual C++實現[M]．北京：科學出版社，2004

[19] 朱華，姬翠翠．分形理論及其應用[M]．北京：科學出版社，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

國家自然科學基金項目（11601391）；天津市自然科學基金項目（18JCQNJC69700）；天津市高等學校科技發展基金計劃項目（JWK1611）；天津職業技術師范大學研究生創新基金項目（YC19-36）

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