基于像素的多边形等距区域子分算法中国图象图形学报.doc

中图法分类号：TP301.6 文献标识码：A 文章编号：1006-8961(200 ) - - 论文引用格式： 基于像素的多边形等距区域子分算法 严志刚， 寿华好 浙江工业大学理学院, 杭州 310023 摘 要：目的：多边形等距是计算机图形学、计算几何、计算机辅助几何设计领域的一个基础性问题，并且有着广泛的应用。为了有效的处理各种类型的多边形等距问题，提出一种基于像素的多边形等距区域子分算法。方法：利用四叉树数据结构对给定区域进行子分，再利用区间算术计算出符合等距要求的全体像素集。针对只是由线段组成的多边形采用点到线段的最短距离算子加快计算速度。结果：利用区域子分算法处理了不同类型的多边形等距问题，并与传统的基于像素的多边形等距膨胀算法进行了比较。实验结果表明所提算法能有效处理各种多边形的等距问题，相对于传统的基于像素的膨胀算法，在顶点处的处理效果上更好，并且耗时也更短。所提区域子分算法比传统边等距方法适用范围更广，能够有效的处理一些边等距算法不能处理的多边形等距问题。结论：提出了一种新的基于像素的多边形等距区域子分算法，其优点是不需要考虑自交和连接问题，并且可以处理其他许多常规方法处理不了的各种类型的多边形等距问题，包括带有弧段和孤岛的情况。 关键词 ：多边形等距; 区域子分算法; 区间算术; 四叉树 Pixel based domain subdivision algorithm for polygon offsetting YAN Zhigang, SHOU Huahao College of Science，Zhejiang University of Technology, Hangzhou 310023 Abstract: Objective: Polygon offsetting is a fundamental problem in the field of computer graphics, computational geometry and computer aided geometry design, and it has many applications. In order to deal with various types of polygon offsetting effectively, a pixel based domain subdivision algorithm is proposed in this paper. Method: Using quadtree data structure to subdivide the given domain and using interval arithmetic to calculate the sets of all those pixels that are on polygon offsets. For polygons that are composed of line segments only, using the shortest distance operator between point and line to speed up calculations. Result: Pixel based domain subdivision algorithm for polygon offsetting can handle different types of polygon offsetting problems, and it is compared with the traditional pixel based polygon offsetting expansion algorithm. The experimental results show that the proposed algorithm can deal with all kinds of polygon offsetting problems effectively. The performance of the proposed algorithm is better on the processing of vertices and it is less time-consuming than the traditional expansion algorithm. The proposed algorithm has more extensive applicable scope comparing with the traditional edge offsetting algorithm, it