一种任意简单多边形求差算法

摘要：

提出一种基于线段操作的简单多边形求差算法。该算法的主要过程为：应用基于单调链的扫描线求交算法，求取交点，该过程减少了求交过程中的比较次数，从而提高了求交效率。基于线段操作的结果多边形连接算法，该过程利用基础的计算几何理论，寻找构成结果多边形的边，得到两个多边形的差。实验表明该算法思路简单，数据结构简单，易于编程实现，对于简单多边形求差问题具有普适性。

关键词：简单多边形、求差算法、基于线段、单调链

分类号：P25;TP301.6(专业测绘)

资助基金：国家科技支撑计划项目2013BAB05B01；甘肃省自然基金项目148RJZA041；甘肃省科技支撑计划项目1304GKCA009；甘肃省财政厅基本科研业务费214146

在线出版日期：2015-10-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：66-68,71