多边形优化算法

《多边形优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第!"卷第#期浙!江!大!学!学!报!工学版"=(->!"?(>#$%%&年#月’()*+,-(./0123,+45+361*7389!:+43+11*3+4;<31+<1";1@>$%%&多边形顶点匹配优化算法丁弋川!刘利刚"浙江大学数学系%浙江杭州B"%%$&#摘!要#分析了B种有代表性的平面多边形顶点匹配算法的特点%即基于极小化形变功的匹配算法&基于轮郭绕行趋势变化的匹配算法和基于边界局部剖分的匹配算法%综合利用不同算法的优点%在修正动态规划框架下设计了一种新的匹配算法>新算法结合了多边形局部和全

2、局的几何本质特性%其匹配结果不受图形平移&缩放和旋转等形变的影响>分别利用!种算法对Q$幅平面多边形图形样本进行了试验%按照算法匹配结果和人为判断结果的一致性进行评分>统计分析结果显示%在不同规模的图形组实验中%新算法较前B种算法均表现出明显的优越性>关键词#形状匹配$顶点对应$动态规划中图分类号#MKB#"!!!!!文献标识码#R!!!!!文章编号#"%%S#&BT"$%%&#%#"QB$%QJ3*%"#)Q,.*,V"#*42%&$#)$/.%*2"0/.3/)+$/&#)-2#3,-IY?VW3G

3、<0),+%JY5J3G4,+4"D&E-+.,&*.$(F-.5&,-./19%45&6/-*’7*/8&+9/."%:-*’;5$1>%E1.(*H,83(+H3+3H3D,83(+[,71EH,8<03+4,@@*(,<0%<(+8()*8,+41+83,-6

4、,*3,83(+[,71E,@@*(,<0%,+E[()+E,*9714H1+8,83(+[,71E,@@*(,<0%,+(61-@(-94(+,-70,@1H,8<03+4,-4(*380HC,7E161-(@1E[,71E(+,+3H@*(61EE9+,H3<@*(4*,HH3+4.*,H1C(*a>M01@*(@(71E,-4(*380H<(+73E1*7[(80801-(<,-,+E8014-([,-41(H18*3<,-@*(@1*8317(.80170,@17%,+E801H,8<03+4*

5、17)-8373+6,*3,+88(80141G(H18*3<8*,+7.(*H,83(+3+<-)E3+48*,+7-,83(+%7<,-3+4%,+E*(8,83(+>N3.89G8C(7,H@-170,@17C1*181781E)73+4801.()*,-4(*380H7%,+E)71*77<(*1E,--801H,8<03+4*17)-87>;8,83783

6、11,-4(*380H7>8,+9/.1-’70,@1H,8<03+4$61*81X<(**17@(+E1+<1$E9+,H3<@*(4*,HH3+4!!图形匹配是指找出$幅给定图形中各部分间的匹配问题的一般模型和解决这类问题的一般步骤%然对应关系%并符合人的一般判断标准>图形匹配不仅后介绍和分析了B种有代表性的算法%并通过综合&有其自身的重要意义%而且是图形查找&形变等操作改进提出了本文算法>通过程序试验和评分统计的方的核心步骤%寻找有效的图形匹配算法对提高图形法比较了不同算法在各种规模图形匹配中的性

7、能>数据库作业性能至关重要%其中应用最广泛的是$条平面封闭曲线之间的匹配>一般平面图形的信"!问!题息具有连续统势%不能为计算机所接受%所以要用多边形对原平面封闭曲线作近似%即把曲线分段%记录:>:!多边形顶点匹配问题的数学描述分段点的坐标%再用直线段近似曲线段%记录其凹凸图"是多边形顶点匹配的一个例子B给定$个(")多边形C和GB记C的,个顶点E"/c"%$%*%,#性以便用样条曲线复原>本文描述了多边形顶点/收稿日期#$%%A%B"%>浙江大学学报!工学版"网址#CCC>2()*+,-7>D2)>1

8、E)><+!1+4基金项目#国家自然科学基金资助项目"A%Q%B%A&#$浙江省自然科学基金资助项目"W"%Q"Q##>作者简介#丁弋川""#S!F#%男%浙江湖州人%硕士生%从事计算机图形学&组合与优化等的研究>:GH,3-’9&E3+4!H,80>)C,81*-((><,通讯联系人’刘利刚%男%副教授>:GH,3-’-34,+4-3)!D2)>1E)><+第#期丁弋川!等"多边形顶点匹配优化算法"QBBH3+4"IK$表进行"如图$所示