多边形包容性检测

第 33卷 第 3期 东华大学学报(自然科学版) Vo1．33，No．3 2007年 6月 J()URNAL OF DONGHUA UNIVERSI'I、Y(NATURAI SCIENCE) Jun．2007 文章编号：1671—0444(2007)03—0328—04 多边形包容性检测 孙贤斌 ，李德华 ，尹 杰 ，姚 讯 (1．华中科技大学 图像识别与人工智能研究所。湖北 武汉 430070；2．湖北工业大学 土木工程与建筑学院，湖北 武汉 430068) 摘 要i多边形包容性检测即多边形与多边形包含关系的检测算法，这里提出的算法是先将两多边形A，B以同一方 向进行顶点编号，以A多边形的每边与B多边形求交点，将交点进行排序并与顶点编号方向一致，这些交点将多边形 A的边分为多段，将A位于B多边形内的各个线段 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 在线段 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf lines中；同理将 B位于A多边形内的各个线段也记 录在表lines中；在线段表 lines中取第一段，搜索与其后端点连接的下一段，继续搜索再下一段，直至首尾闭合，连接形 成两多边形的公共部分多边形，即两多边形的交集，其各顶点坐标已记录．将 lines中搜索出的段进行删除．在 lines中 继续搜索下一交集，直至 lines为空．实验表明，此算法简单有效． 关键词：计算机应用；多边形；包容性；线段搜索 中图分类号：TP 391 文献标志码：A ‘ Algorithm for Polygon in Polygon SUN Xian-bin ，LI De-hua ，yIN Jie ，YAO Xun (1．Institute of Image Recognizing and Artificial Intelligence，Huazhong University of Science and Technology，Wuhan Hubei 430070，China； 2．School of Ci I Engineering and Architecture，Hubei University of Technology。Wuhan Hubei 430068，China) Abstract：The relationship test of two polygons is algorithm for polygon in polygon． The prepared algorithm is complex；a new algorithm was given in this paper：every peak of two polygons was arranged a number in same direction，crossing points of polygon A and polygon B was calculated for every edge of A， these crossing points were ordered same direction as edge．The edges were divided into many segments by crossing points，every segments of polygon A located in polygon B was found out and put in a table “lines”；in the same way，segments of polygon B located in polygon A were founded out and put in table “lines”too．A segm ent in table“lines”was picked out as first segm ent，and a segm ent that can 1ink with its endpoint in“lines”was found out and put into table“points”．it is done continuously til1 the segm ents is close，it is a new polygon，the colnn'lon part of this two po lygons A and B．Another colnn'lon part could be found out like this method tiU“lines”are empt~ The algorithm was proved simply and effectively by programming． Key words：computer application；polygon；polygon in polygon；line search 在图像处理、计算机图形学、地理信息系统以及 其他一些工程应用和技术研究领域，有许多点一 线一多边形的拓扑关系处理，如：点一线关系、点一 多边形关系、线一线关系、线一多边形关系、多边形一 收稿日期：2007—01～2g 基金项目：国家自然科学基金 (69775022)；湖北省教育厅资助(G2OO514OO1) 作者简介：孙贤斌(1964一)，男，湖南华容人，副教授，博士，研究方向为计算机视觉和地理信息系统 E-marl：xianbinsun@126．tom 维普资讯 http://www.cqvip.com 第 3煳 孙贤斌 ，等：多边形包容性检测 329 多边形关系．在这些点一线一多边形关系中，复杂的 算法是点一多边形、线一多边形、多边形一多边形关 系，线一线关系最为关键，其他几种关系都可以转化 为线一线关系． 有许多问题需要计算两个多边形的交集，即判 断两多边形的包含关系，它需要检测出两多边形的 公共部分(图 1)，这是一个基本算法，在许多情况 下，需要检测的多边形的数目很多． 4 ／ B ／， A 图 1 两多边形相交 Fig,．1 Intersection of two polygons 近年来对此问题有不少的研究，文献[1]的算 法是先计算各交点，产生公共边线，经搜索形成多 边形，但须计算角度并进行旋转，以搜索夹角最小 的线，因而计算量较大． 文献[2，3]中提到多边形交集的算法，但它只 用于两凸多边形，对凹多边形不能处理． 文献[4]的算法讨论多边形的完全包含，即嵌 套关系，而对多边形相交形成交集的情况未讨论． 文献[5]的算法是通过区域划分，把一个大规 模的求交点运算分解为多个小规模的求交点运算， 计算每个区域内的交点，形成交点集，然后对交点 集进行整理．但其主要讨论区域划分，对如何形成 两多边形的公共多边形即交集基本未涉及． 文献[6]的算法是从两多边形的顶点作水平 线，这些水平线将两多边形切割为许多条带，判断 条带的各段是否位于公共部分．这种算法思路比较 复杂，并且可能会产生区间遗漏． 1 本文算法 本文算法是求出两多边形的所有交点，对交点 进行跟踪排序，形成公共区域多边形．两多边形相交 可能会形成多个公共区域即多个多边形，找出这些区 域的各个顶点并排序形成多个多边形(也可能没有公 共区域，或产生公用边或共同点等多种情况)． 如图1，两多边形P 和 P 按逆时针方向编号 为 1234561和 ABCDEFGA，求出多边形 P 位于 内的段的编号为n4，4，)，f6，6d；求出多边形 P 位于 P．内的段的编号为 E，Ec， ．则组成线段表 为 lines=[a4，46，f6，6 ， E， ， ]．在其中任取 一 段，如 ∞，记录后端点坐标，组成点表 points一 [6]，按后端点坐标值开始搜索，找到 6 段的前端 点与c6后端点坐标相同，为同一个点，将此段后端 点坐标值记录在点表中 points=[6，d]，然后删除 6 段，此时线段表为 lines一[n4，46，f6， E， ， ]；以 6 段的后端点 d的坐标值开始继续搜索， 找到 E段，记录E点，此时点表为 points一[6，d， E]，删除 E段，此时线段表为 lines一[n4，46，f6， ， ]；以E点搜索到 ，记录 C点坐标，points= [6，d，E，C]，删除Ec，lines=[a4，46，c6，ba]；以C点搜 索到f6，记录6，与起点相同，闭合}删除 c6，points= [6，d，E，C，6]，第一个公共多边形形成，lines=[a4， 46， ]；在 lines中任选一段继续同样方式的搜索，找 到其他多边形，直至线段表lines为空表结束． 2 交点判断及计算 设点P。(XO，Y。)和点P ( ，Y )为两端点组 成一条线段，则其直线方程为： — Y-- — Yo 一 二 二 一 X--X0 r — 0 z 1一 0 1一 0 1一 0 若 o4r≤1，则此式表示由点 P。( 。，Y。)和点 P ( ，Y )为两端点的线段． 将它以参数形式表示为： —z。-卜 一 。 o≤，≤l < 【J：＼r：＼l l y=y0+r( 1--y0) 、 、 当o4r≤l时，每个实数r与线段上的点一一 对应．图2中，点P0和P 组成线段L；点P：和P 组成线段 L ，O≤r≤l，o4r ≤1． P (L丁：，y：) 尸l(_丁，，Y、) eo(．r +r(P，一P。) +， (P：一P：) Y ) 图2 交点计算 Fig．2 Crossing po int calculation 如果 L和L 存在交点，则下式成立： 。+r(371--X0)一 ；+r ( j— ：) l Y。+r( --y。)一 ：+r ( 一 ) O≤r≤l，o4r 41 、 、 、 、 ＼ 维普资讯 http://www.cqvip.com 330 东华大学学报(自然科学版 第 33卷 若由上式得出的r和r 都位于闭区间[0，1]内， 那么，此两线段就有一个交点．交点为： ( +r( 1一 )，Y0+r( 1--y0)) 或 (z：+r (z 一z：)，Y：+r ( 一 )) (1) 据此计算下列行列式： 。一J X 一-- XoY； Yzi二 } l( 一 ) ( 一 ：)I 二 X --Xo 二 ． 分为下列3种情况处理： (1)若 D≠0，则L和L 可能有交点，且： r=D1／D r ： D2／D 即：如果 L和L 两线段存在交点，则必然有 DSo． 若 rE[0，1]，则r(1一r)≥0，即 D (D—D )／ D2≥0或 D (D--D )≥0． 由此可知，若L和L 两线段有交点，则： D (D--D )／D2≥0且 D2(D--D2)／D2≥0，D≠0 或 D (D--D )≥0 且 D2(D--D2)≥0，D4：O(2) (2)若 D一0，D *D2 So，则 L和 L 互相平 行，无交点． (3)若 D—D 一D。一0，则 L和 L 两线段共 线，不计算交点． 多边形 A各边SⅢ (z ，Y )，(z⋯ ，Y⋯ )]， 一 1，2，⋯，m}，其中： +1一z1，Y +1=-y1，以参 数方程描述为： 0≤ 1 多边形B各边s；{[(z；，Y；)，(z；+ ， ；+ )]， j=l，2，⋯， }，其中：z f ：z ， ，+ = ，以参 数方程描述为： 解求交点表达式： 0≤r ≤1 fXi+，．( 件 --．7；2 )一 ；+，． ( + --32；) < 【Yi+r( + --y )一 ；+r ( ；+1--y：) 0≤ 1，0≤r ≤1 其行列式为： 。一I‘( Yi．】+l--一Y iY ； Y 二 二 I f ) (：+ 一 ：)f 。 一I ( X j一-- ．T i； ：二 l D2 (．z'i+a--．z"i 二 按式(2)的原则处理，按式(1)计算出交点． 3 各分段 的处理 对两个多边形 A和 B，将它们以同一方向进行 顶点编号．求多边形 A与B的交点：以多边形 A的 某边S 与多边形B各边求交点，将交点按S 端点 的方向插入到S 中，这些交点将S 边分为多段，分 别判断各分段是否位于多边形 B内，按与多边形顶 点编号方向一致的方向记录各段的端点坐标，将位 于多边形 B内的段的两端点坐标写入线段表lines； 对A的各边做同样的工作．以同样的方式求出多边 形 B位于多边形 A 内的段并且也写入线段表 lines，两多边形的公共区域就由这些线段组成． 4 线段搜 索 取线段表lines中的任一段，为方便，取第一段 的后端点开始搜索，在 lines中寻找前端点与其坐 标相同的段，这两段就是连接在一起的相邻段，它 们将成为公共区的两条相邻边；以此段的后端点为 依据继续搜索与其相同的前端点，构成后续的边， 直至后端点与起点为同一点，即公共区闭合．将每 段的后端点坐标保存在点表 points中．为避免重 复，每搜索匹配成功一段，先保存后端坐标，然后删 除此段． 搜索出第一个公共区后，可能还有其他公共区， 在余下的线段表 lines中取第一段继续上述的操作， 找到另一个公共区域多边形，直至lines为空表． 搜索完成后，线段表lines为空，点表 points中 保存了各个公共区相邻顶点的坐标，为将各区分 开，另设一个数组变量 hum，记录各公共区的顶点 个数． 5 组成公共多边形 公共 区已存在 于点表 points和 hum 中，在 ) ) ≈ 一 一 H + + 一 一 z r ● ( 【 、 ， ＼， ， ．J ， ， z y 一 一 1 L + 十 ， J ， ．， z y ／ ／ ， ， r r + + ， J ， ．， z y 一 一 z r ● ( 【 维普资讯 http://www.cqvip.com 第 3崩 孙贤斌，等：多边形包容性检测 331 points中取前nllm(1)个点即为第一个公共多边形； 接着取num(2)个点即为第二个公共多边形；后续 7 总结 同样．这些公共多边形坐标都是首尾闭合的． 6 算例 图3中每行4张图，前2张是多边形A和B，第 3张是两多边形相交的情况，第4张是计算出的其 公共部分的边界． 訇 匐 訇 匐 訇国 图3 算例 Fig．3 Some examples a 口 ， I． 此算法主要由“点包容性检测”和“线包容性检 测”以及搜索算法组成，构成了一个新的算法，算法 简单实用、实现容易．笔者依此编写了相应的程序 进行验证，实验证明算法简单、有效、稳定、可靠．图 3为部分实验计算结果． [2] [3] [4] [5] [6] 参 考 文 献 卢华兴．基于 Polygon之间相互切割的算法描述与实现[J J． 地理空间信息，2005，(2)：12—14． 庞明勇，卢章平．计算两凸多边形的并集多边形及其面积的计 算机算法与实现[J]．工程图学学报，2004，25(1)：9O一94． 张宝琳．计算两凸多边形交集面积的计算机算法[J]．计算机 工程与应用，2001，(9)：128． 彭认灿 ，陈子澎，刘国辉．快速确定多边形与多边形包含关系 的一种新方法[J]．测绘通报，2006，(5)：50—52． 姚辉学 ，卢章平．一种任意复杂程度二维多边形的求交算法 [J]．工程图学学报，2006，(2)：127—131． 张 宏，温永宁，刘爱利．地理信息系统算法基础[M]．北京： 科学出版社，2006：23—28． (上接第 323页) 提高教学效果．网页发布见图5． 々 、 h● 啦 毋 萋 ， 曩．．·非 8 簸e 旺 结构、组成及拆装学习，也可作为实际拆装前的培训． 节省对设备实物的购买资金，并可根据教学需要和设 备改进及时进行调整和更新．提高了轮机专业的实践 性，拓宽了教学空间，丰富教学形式，为进一步开发虚 拟实验软件积累了宝贵的经验，具有参考价值． [2] 图5 拆装实验网页 吕5 Web of disassembly and assembly [3] 3 结束语 此实验系统可为轮机专业学生提供分油机设备 [4] [5] 参 考 文 献 吴 恒，李浩基．阿法拉伐现代技术 (分油机分册)[M]．大 连 ：海事大学出版社。1995：22—25． 李 帅，王卫平．虚拟实验技术在课堂教学中的应用研究 [J]．中国农村教育，2006，(6)：122—123． 王国权．虚拟试验技术[M]．北京：电子工业 出版社，2004： 99—103． 迟权德，陈 娟．虚拟机械实验室的构建[J]．计算机与信息 技术，2006，CN刊)：84—86． 邱龙辉，叶 琳．工程图学虚拟实验设计方法 [J]．青岛科技 大学学报，2006，27(5)}438—440． 维普资讯 http://www.cqvip.com