摘要
在充分挖掘AutoCAD图形中简单多边形自身隐含的垂直与共线关系的基础上,提出一种新的基于直角顶点判定和凹凸顶点判定的简单多边形剖分算法。该算法首先判断出多边形顶点的直角特性和凹凸性,然后根据多边形自身的特点按照一定的先后次序进行剖分,力求把多边形分割成直角梯形、矩形和直角三角形的形式。其中判断辅助线连接次序的优先级是实现剖分算法的关键。程序实现中采用递归算法,对分割后的多边形重新进行判断,直到多边形分割完毕。
A new decomposition algorithm of simple polygon based on determination of right-angled vertices and convex-concave vertices is presented by fully mining vertical and lined relationship of polygon itself in AutoCAD.Its basic idea is to calculate right-angled vertices and convex-concave vertices first,then try to decompose polygon into rectangles right-angled triangles and trapezias according to specific priorities.The determination of connection order of assistant line is the key of algorithm.Recursion algorithm is used in programming,and repeat the above steps for each new polygon until termination condition is met.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第5期43-45,49,共4页
Computer Engineering and Applications
基金
杭州市5112工程基金资助项目
