一种凸多边形的交、并求解算法.pdfVIP

第27卷 第4期 桂 林 工 学 院 学 报 V0I_27 No．4 2007年11月 Journal of Guilin University of Technology NOV． 2oo7 文章编号：1006—544X(2007)04—0589—04 一 种凸多边形的交、并求解算法 黄俊华 ，闰遂军 ，朱小龙 ，李景文 (1．武汉大学遥感信息工程学院，武汉 430079；2．广西区国土资源厅，南宁 530023； 3．桂林工学院土木工程系，广西桂林 541004) 摘 要：凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列．提出了以顶点与多边 形的空间拓扑关系为基础，将不同拓扑关系的顶点进行重新组合的方法来解决任意2个凸多边形 交、并的求解问题．算法易于编程实现，能够较好的求解二维凸多边形区域各种情况的交与并， 可为GIS应用中矢量多边形之间的关系计算提供算法基础． 关键词：计算几何；凸多边形；相交；相并 中图分类号：TP301．6；P208 文献标志码：A 研究2个平面凸多边形的交、并求解算法是 多边形．简单凸多边形是客观世界中空间实体常用 GIS应用中矢量多边形之间关系计算的基本问题之 的描述形式，其交、并求解算法是空间实体逻辑关 一 _l ． 现有的一些算法虽然能够解决这一问题， 系判断的常用方法． 但是它们多是以多边形的边与另外一个多边形的 1．2 算法思想 空间关系为依据，计算得到交、并多边形，不仅 2个凸多边形在平面上存在的位置关系有：分 顶点序列维护困难，而且需要大量的存储空间． 离、包含、相交和相切．对于2个凸多边形为分 笔者从多边形的顶点与另外一个多边形的空间关 离、包含和相切的情况，其交集和并集较容易表 系的角度考虑，将不同拓扑关系的顶点和2个多 示出来．本文主要讨论2个凸多边形相交情况下 边形的交点进行合并，得到了结果多边形顶点序 的交、并的求解算法． 列，从而实现了凸多边形的交、并求解运算，较 算法的基本思想是：将参与求解过程的2个 好的维护顶点序列的存储顺序． 凸多边形的顶点集按照顶点与多边形的拓扑关系 进行双向筛选，再将筛选出的2组顶点和2个多 1 算法的描述 边形的交点，按照多边形顶点序列逆时针顺序存 1．1 简单凸多边形的定义 储的原则合并共同存储为一个顶点序列，即可得 平面多边形是由Ⅳ个点 ， ， ，…， 首尾 到结果多边形的顶点序列 (图1)． 相连的闭合折线段表示， (i=1，2，…，n)为多边 2 算法实现的过程 形顶点， ， ，…， ～。 ， 为多边形的边． 对于任意非相邻边不相交的多边形称为平面简单 2．1 凸多边形交集求解算法的实现过程 多边形．凸多边形是简单多边形的一种特例，如果 多边形的顶点集采用变长数组进行表示，按 简单多边形的任意顶点 (i=1，2，…，n)对应的 照逆时针顺序存储顶点，在图2中，凸多边形的 多边形内角0 ∈(0，叮T)，则称此多边形为平面简单 顶点序列表示为P(P。，P ，P，，…，P )和Q(Q。，Q ， 凸多边形．除去凸多边形以外的简单多边形都是凹 Q ，…，Q )． 收稿日期：2007—04—11 基金项目：国家自然科学基金资助项目 ；广西自然科学基金项目(桂科自0448076) 作者简介：黄俊华 (1963一)，男，博士研究生，副教授，研究方向：GIS空间分析与决策方法． 59O 桂 林 工 学 院 学 报 2007正