基于像素的多边形等距区域子分算法

目的 多边形等距是计算机图形学、计算几何、计算机辅助几何设计领域的一个基础性问题,并且有着广泛的应用。为了有效地处理各种类型的多边形等距问题,提出一种基于像素的多边形等距区域子分算法。方法 利用四叉树数据结构对给定区域进行子分,再利用区间算术计算出符合等距要求的全体像素集。针对只是由线段组成的多边形采用点到线段的最短距离算子加快计算速度。结果 利用区域子分算法处理了不同类型的多边形等距问题,并与传统的基于像素的多边形等距膨胀算法进行了比较。本文算法能有效处理各种多边形的等距问题,相对于传统的基于像素的膨胀算法,在顶点处的处理效果上更好,并且耗时也更短。所提区域子分算法比传统边等距方法适用范围更广,能够有效地处理一些边等距算法不能处理的多边形等距问题。结论 本文算法其优点是不需要考虑自交和连接问题,并且可以处理其他许多常规方法处理不了的各种类型的多边形等距问题,包括带有弧段和孤岛的情况。

Pixel based domain subdivision algorithm for polygon offsetting

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. A pixel-based domain subdivision algorithm is proposed in this paper to deal with various types of polygon offsetting effectively. Method The given domain is subdivided with quadtree data structure, and the sets of all those pixels that are on polygon offsets are calculated with interval arithmetic. For polygons that are composed of line segments only, the shortest distance operator is used 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 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 than that of traditional expansion algorithm. The proposed algorithm is also less time consuming than traditional expansion algorithm. Compared with traditional edge offsetting algorithm, the proposed algorithm has more extensive applicable scope, and it can effectively deal with various types of polygon offsetting problems that traditional edge offsetting algorithm fails. Conclusion A new pixel-based domain subdivision algorithm for polygon offsetting is proposed in this paper. The proposed algorithm does not need to consider intersection and connection problems, and it can handle various types of polygon offsetting problems that many other conventional algorithms fail, such as when polygon contains arcs and islands.