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

摘要

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