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

• 作者: 赵军 郝永兴
• 来源期刊: 图学学报
• 学科: 工学
• 关键词: 多边形 孔洞 最小回路 布尔运算
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 图形学与可视化
• 页码范围: 498-503
• 页数: 6页
• 分类号: TP391.4
• 字数: 3236字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵军	兰州交通大学机电工程学院	28	187	8.0	12.0
2	郝永兴	兰州交通大学机电工程学院	1	5	1.0	1.0