一种求含孔洞多边形交、并、差集的新方法

A New Method for Determining the Intersection,Union and Difference of Two Polygons with Holes

提出了一种基于最小回路确定含孔洞多边形P和Q的交、并、差集的新方法。首先,初始化P和Q外环为逆时针方向,内环为顺时针方向,并通过连接内环极右顶点与其在外环上一可见点v,构造一条双向"桥边",将内外多环转换为单环。其次,求出P和Q被转换为单环的边序列的交点,并对交点处的关联边进行排序。然后,沿着各个交点处正向边,依照最小转角原则搜索最小回路,并根据其中所含P和Q边所呈现的顺、逆时针方向进行分类。最后,P和Q的交、并、差集即对应不同类别的最小回路。算法简洁且几何意义明显,具有较好的适应性。

A new algorithm is presented for Boolean operation of two polygons with holes based on minimum circle. Firstly, outer rings of Polygon P and Q are initialized to counter-clockwise direction, and inner rings are initialized to clockwise direction. ＂Bridge edges＂ connect the outer and inner rings, so the polygon with multiple rings is converted to single ring. Then the edges connecting to each intersection point of P and Q are arranged in sequential order. Next, all minimum circles are found by the minimum turning angle rule. These minimum circles are classified according to edges direction in P and Q. Intersection, union, and difference of the two polygons correspond to different kinds of minimum circles. The algorithm has explicit geometric significance, and well resolves the problems in special cases.