一种基于矢量游走的复域多边形合并算法.pdfVIP

第32卷第6期 微 计 算 机 应 用 V01．32No．6 2011年 6月 MICROCOMPIJTIERAPPUCATIONS Jun．20l1 一 种基于矢量游走的复域多边形合并算法 刘术华 周云燕 曹立强 万里兮 (中国科学院微电子研究所 北京 100029) 摘要：电磁仿真工具中，常常将许多具有相同属性的多边形合并成一个多边形，以便对图形进行整体操作和网格划分。本文 提出了适用于多边形合并的矢量游走规则及交点转移条件，通过交点与相交矢量边的联合处理，简化了重合交点处理，从而 实现一种基于矢量游走规则的带内孔复域多边形合并算法。 关键词：多边形 矢量游走 合并运算 相交 重合顶点 An InnerHoleDeployedPolygonCombination Algorithm BasedonVectorW anderM ethod LIU Shuhua，ZHOUYunyan，CAO Liqiang，WAN Lixi (InstituteofMicroelectronicsofChineseAcademyofSciences，Beijing，100029，China) Abstract：A numberofpolygonsthatshareshtesamepropertiesarecommonlycombinedintoasinglepo lygonSOastofacilitatethe graphicswithoveralloperationsandrgidpartition．ThispaperintroducesallinnerholedeployedpolygoncombinationM~dhtm based onvectorwnadermehtod，nadproposestherelatedrulesandconvergeshiftconditions．Thesimplificationofcoincidenceintersection processingisalsoproposedbycomb inationalhandlingtheintersectionandhteintersectedvector． Keywords：Polygon，VectorWna der，Comb inationAlgorithm，Intersected，CoincidenceIntersection 1 前言 常用的商用电磁仿真软件如HFSS、Slwave等，为了便于具有相同属性(材料、层、颜色、网格属性等)图 形的整体操作及仿真时网格化分，经常需要将同一版图中的多个多边行合并(Unite)成一个整体，这些被 u- nite的多边形都是简单多边形和由多个简单多边形组成的复域多边形。由此可见，为了实现增强电磁仿真 软件在实际工程应用中的实用性和可操作性，Unite功能是一个必不可少的功能，本文在实际电磁仿真软件 开发的基础上对多边形的合并运算算法进行了深人的研究，并在理论基础上提出了一种基于矢量游走的新 型合并算法。 多边形的合并运算在一般的计算机图形学书籍中都有所涉及，但都是基于简单凸多边形，对于复杂凹 多边形或复域多边形的合并基本没有介绍。本文运用矢量游走规则 J，并对其加以改进，提出了一种有效 的复域多边形合并算法。本算法通过把交点和两相交矢量边联合处理，有效剔除了 “伪交点”，且不用对交 点集排序，在电磁仿真软件中得到了很好的实际应用。 2 基本理论 为了简化描述，本文假设参与合并运算的两个多边形为P= ( ，… ．… ，。)，Q= (，，：… … ．， 砣 )，m1、IIl2为多边形顶点个数。 本文于2011—04—08收到。 2 微 计 算 机 应 用 2011年 简单多边形 ¨具有下列性质：①所有顶点各不相同，即：Vi≠ ≠ ；②任何顶点都只属于它所在 的边；③任意两条边都不相交。 简单多边形的方向-l：若多边形顶点v，v：，…，v