两个简单多边形求交的算法  被引量:8

An Algorithm to Compute the Intersection of Two Simple Polygons

在线阅读下载全文

作  者:宋立明[1] 闫浩文[1] 王邦松[1] 方爱玲[1] 

机构地区:[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出  处:《测绘与空间地理信息》2011年第6期258-260,共3页Geomatics & Spatial Information Technology

摘  要:采用了双向链表这种数据结构,对两简单多边形的顶点及交点进行存储,在对交点进行插入时,可直接插入链表中,避免了利用单向链表或数组进行存储时对点的重复查找。通过遍历两个顶点、交点混合表,可得到两多边形的交及多边形的顶点,从而得到两多边形的交集。相对其他类似的算法,该算法具有较快的计算速度和较高的效率。This algorithm utilizes the two-way list data structure to store the vertices and nodes of two simple polygons.When being inserted,the node can be directly inserted into the list,which can avoid a repeat search comparing with the one-way list and the array structures.The vertex of the intersection polygons can be acquired after the two mixed-point lists are searched,so that the intersection polygons can be obtained.The algorithm owns the rapid calculation speed and high efficiency comparing with the similar ones.

关 键 词:双向链表 多边形 顶点 交点 交集 

分 类 号:TP311[自动化与计算机技术—计算机软件与理论]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象