基于顶点可见性的凹多边形快速凸分解算法

第 36卷 第 1 2期 l 999年 l2月 计 算 机 研 究 与 发 展 JOURNAL OF COMPUTER RESEARCH ＆ DEVELOPMENT Vo】．36．No．12 Dec． 1999 I ～1 6o 基于顶点可见性的凹多边形快速凸分解算法 、／ 金文华 饶上荣 唐卫清 刘慎权 (中国科学院计算技术研究所 CAD开放研究实验室 北京 100080) I 、 一 n2LL P{ l }2 摘 要 凹多边形的凸分解问题是计算几何的摹本问题之一．在许多领域均有应用 现有算法太多为全局剖分算 法，而局部剖分算法研究的很少．全局方法由于耗时太多．而不能满足所有工程应用的需要．目前局部剖分算法中 最经典的是 Rogers算法，但由于其存在许多缺陷而在实际应用中受到限制．文中在多边形顶点可见性基础上．提 出了新的局部剖分方法．利用凹点的局部几何特性．通过引入权函数从凹点的可见点串中选取适当的点引剖分线． 或者利用凹点夹角平分线与某两可见顶点所在边的交点引剖分线进行多边形分解．文中算法已应用于工厂软 件PDSOFT Piping中．实践证明效果很好． 关麓词 简单多边形·嘎盛旦墨 ·多边形分解· !： ：塑 中圈法分类号 TP302．4}TP391．72 凹夕趣矽 凸舛 耸曩 A FAST P0LYGoN CoNVEX DECoMPoSITIoN ALGoRITHM BASED oN PoINT VISIBILITY JIN Wen—Hua，RAO Shang—Rong，TANG Wei—Qing，and LIU Shen Quan (CAD Laboratory，Institute of Computing Technology．Chinese Academy of Sciences·Beijing 100080 Abstract Polygon convex decomposition is one of the fundamental problems in computational geometry．It is used in many fields．Most of the algorithms now available are global searching ones．Local searching algorithms are rarely studied．The global searching algorithms waste so much time that they cannot meet the need of all the engineering problems．Presently the most classical local searching method is Rogers algorithm． But as it has many limitations， it is restricted in some actual use．In this paper，a new local searching algorithm is proposed based on the polygon point visibility．The local geometrical property is fully used in the algorithm．The cutting—line is obtained from the concave point to the visible point which is carefully searched from the visible point list of this concave point by using weight function．Alternatively，the cutting—line is found from concave point to the intersection point which is located on the visible point line and the bisector of the concave angle associated with the concave point．The presented algorithm has been applied in the plant design system of PDSOFT Piping，and the results 0btained are remarkab】e． Key words simple polygon，point visibility，polygon decomposition，computational geometry 原稿收到日期：199819 23l修改稿收到日期：1999·08·31．本课题得到国家自然科学基金项目(项目编号 69673001)资助．盒文华，男，1970 年 1O月生，博士后．主要研究顿域为CAD／CG、计算几何、产品信息建模、、数据库等．饶上荣，男．1971年 12月生，博士研究生．主要 研究领域为CAD／CG、网络、优化算{击、敷据库等 唐卫清，男．1965年 7月生．研究员．主要研究顿域为CAD／CG、科学可视化、交互界面、产品 信息建模．项目管理、数据库等．刘慎权，男，1930年 l2月生．研究员．博士生导师，主要研究领域为CAD／CAM、产品信息建模、面向对象技术、 CG、计算几何、科学可视 化等 ： # } 自 _1f1 _ 维普资讯 http://www.cqvip.com 计 算 机 研 究 与 发 展 1 引 言 绐定任意一个简单多边形，如何将其分解为多个具有相同特性的子多边形的组合是计算几何的一个基 本问题，这些子多边形类型包括三角形 、矩形 、梯形 、任意凸多边形 、螺旋多边形 、星形多边 形 、单调多边形 等．对于多边形的组合又存在两种形式，⋯种是并的组合，这是当前流行的多边形剖分 组合方式 ；另一种是并和差相混合的组合，如汪嘉业等人在文献[4]中利用凸包算法将简单凹多边形分 解为多个凸多边形的差组合．本文只讨论将简单多边形分解为多个任意凸多边形并组合的问题、 凹多边形的凸分解在许多领域都有其用武之地，如计算机图形学 、模式识别 、图像分析 l、有限元三 角网格剖分_I 等．给定任意一个简单多边形，如何将其分解为最少个数的凸多边形是计算几何中的一个经 典问题，被 称为 OCD(optimal convex deeomposition)问题．最初人们认 为这是一个 NP hard问题 ．但 B． Chazelle和D、P．Dobkin于 l 979年发表的文章指出这并非是 NP—hard问题，并给出了相应的算法 ．虽然 OCD问题已经有可行的算法进行求解。但由于其耗时巨大，而不能用来解决大多数实际工程问题．另外，在 实际工程问题中．有时不仅要求剖分后凸多边形的数量尽可能少，而且要求凸多边形的形态质量较好．文献 一 5]将凸多边形形态质量理解为“剖分所得各凸多边形在邻接处内角大小应尽量接近，或者说是各凸多边形 内角中最小者最大”．真正实用的凹多边形剖分算法大多数是在解决分解后得到的凸多边形形态质量和数量 两者之间寻求折中． Schachter利用Delaunay思想对简单凹多边形进行凸分解 ．Chazelle等通过构造 Xk型(Xk—pattern) 凹点串实现了尽可能少数目的凸分解一”]、Keil利用基凸多边形(base convex polygon)合并的思想进行凸分 解ll ．国内也有不少学者对此进行了研究 ．肖忠晖等人在文献[33中根据凹点与其前后相邻点的位置关 系，将凹点进行编码分类，然后根据凹点对的编码情况选择铷分策略、王钲旋等人在文献[j]中通过在可视点 对之间建立一种权函数来进行剖分，权函数既考虑了如何尽可能减少凸多边形数目，又考虑了分解后凸多边 形的形态质量，该算法是对文献[3]中算法的改进． 在多边形凸分解算法中，是否使用辅助点(Steiner points)将直接影响分解后产生的凸多边形数目．此处 的辅助点是指凹多边形分解后得到的所有凸多边形顶点中那些不属于原凹多边形顶点的点．在一般情况下． 采用辅助点有助于减少凸多边形数量，而且如果辅助点选取适当，还能提高凸多边形的形态质量． 凹多边形凸分解的本质是消除凹点，因此，剖分线均是扶凹点引出的．一个凹点，经剖分后，将分别对应 两个新多边形中的相应顶点，这两个新顶点在各自的多边形内可能是凸点，也可能是凹点，但两个新顶点不 可能都是凹点．凸点经剖分后将仍是凸点．在文献 3]中，提出了最佳剖分、准最佳剖分和单点剖分的概念，并 确定了最少剖分数 目S应该为： [Ⅳ／2]一l≤s≤Ⅳ一 l 其中，Ⅳ为凹点数．IN~z]取N／2的上整数． 2 全局剖分与局部剖分 简单多边形剖分算法总体上分为两类，一类是每次剖分只针对一个凹点，只考虑如何 I剖分线米消除当 前凹点，这类算法称为局部剖分算法；另一类是从所有可视凹点对和所有可视凹凸点对中选取当前最好的一 条剖分线(可视点对中可以包括辅助点)，这类算法称为全局剖分算法．全局剖分一般来说比局部剖分得到的 凸多边形形态更好，且剖分数不会超过局部剖分，但付出的代价也不小，需要耗费的时问和空间远远超出局 部剖分方法，因此也不能满足所有工程应用的需要，现以石化工厂设计配管软件 PDSOFT Piping中的平剖 图纸(一种工程图纸)自动消隐问题为例进行说明． 在工厂设计配管软件 PDSOFT Piping的平剖子系统中，对管道元件(如管子、阀门、三通等)和设备、建 筑物等进行消隐时，首先用凸包算法[1S．1 s]或割线法It 7-1~]求出处于上位的元件、设备或建筑物等的特征轮廓， 然后把处于下位的元件、设备或建筑物等位于特征轮廓内的图形裁剪掉．特征轮廓用任意简单多边形表示． 维普资讯 http://www.cqvip.com 12期 金文华等 基于顶点可见性的凹多边形快速凸分解算法 割线法求出的多边形基本上都是凹多边形．由于在消隐过程中利用凸包算法得到的凸多边形数量远大于用 割线法求出的凹多边形数量，因此有必要将少数的凹多边形分解为凸多边形，再统一采用底层的凸多边形裁 剪算法 进行消隐处理． 在平剖系统中，如果简单地对特征轮廓多边形进行全局剖分处理，则会降低系统整体性能，因为凹多边 形的全局剖分处理需要很大的时间和空间开销．在平剖消隐中，只要把凹多边形分解为多个凸多边形，并且 尽量使得分解产生的凸多边形有较好的形态，就可进行后续的裁剪处理，而并非一定要把凹多边形分解为最 少个数的凸多边形． 现有许多算法都属于全局剖分算法，相对而言，局部剖分算法研究的文献较少，目前Rogers算法是典型 的局部剖分算法．虽然 Rogers算法能够分解凹多边形．但其固有的缺陷使得其应用受到限制．为此本文在简 单多边形可见点快速搜索算法口 的基础上，提出了新的凹多边形局部剖分算法． 3 Rogers算法 在 凹多边形的凸分解算法中，经典方法是 Rogers．F．David在文献U103中论述的算法(本文称其为 Rogers算法)．Rogers算法属于使用辅助点的局部剖分算法．下面以图1(a)中的多边形为例简要介绍该算 法的基本思路． ， (b) (c) 图 1 Rogers算法图例 设简单多边形为逆时针方向．且以单向链表表示．多边形中顶点凸凹性的定义及判断方法可参见文 献[22]．如图l(a)所示，算法可从多边形的任一点出发(如从点 d出发)，沿单向链表搜索到第一个凹点c，从 凹点c沿有向边 (称为凹边)作射线，与多边形其余边求交，取离点 最近的交点．如图1(b)所示的点 ，沿 线段 将多边形一分为二，得到两个多边形：d6 m和cdefgi 、对这两个多边形再分别作同样的处理、这是 一 个递归过程．当所有新产生的多边形均为凸多边形时，递归终止．如图l(c)所示，递归结束后，原来的凹多 边形被分解为 4个凸多边形，即：口6 4，hik h，c c和 e． Rogers算法的时间复杂度为O(ran)，其中．m为凹点个数， 为多边形顶点个数．Rogers算法简单、清 晰、易于实现，但其存在如下的缺陷： (1)计算量大．在算法处理过程中，每次沿凹边切割多边形时，凹边射线均须与多边形的其它所有边进 行求交运算，从而导致算法效率不高； (2)剖分产生的凸多边形数量较多．用 Rogers算法剖分得到的凸多边形个数基本上固定不变．设多边 形P有n个顶点，其中有 m个凹点．算法每次沿凹边切割多边形后，凹点在两个新多边形中分别对应平坦点 和凸点．因此，算法每作一次切割处理必然会减少一个凹点．因此， Rogers算法最多只产生(m+1)个凸多边形．只有当凹边所在射线与多 边形其它边求交后得到的最近交点正好是原多边形的凹点时，一次切割 才会减少两个凹点．但这种情况出现的概率很小，所以，Rogers算法在绝 大多数情况下得到的凸多边形个数为(m+1)，而这往往是现有其它算法 的最坏结果(仅从数量而言)； (3)有可能产生非常细小或非常微小的凸多边形．如图2所示，凹多 边形的凹边所在射线与下一条相邻边的夹角 如果很小，切割得到的凸 图2 Rogers算法的缺聃 维普资讯 http://www.cqvip.com 计 算 机 研 究 与 发 展 多边形就会变得很细小．这种形态不好的凸多边形在后续的多边形线裁剪算法中极有可能因浮点运算的误 差导致结果错误． 4 基于顶点可见性的局部剖分算法 本文探讨的算法和Rogers算法一样，都属于使用辅助点的局部剖分方法 设简单多边形 P一( 。m ， 。， ⋯ ． )，其中 ，i一0，1，2，⋯， 1为多边形顶点．设从 。出发搜索到的第一个凹点为 ，将 Ⅵ作为视 点，利用文献[21]提出的可见点快速搜索算法求出视点 的可见点串ST=( ⋯， )． 设Ⅳ 为由 出发，与有向线段 = ， 方向一致的射线；Ⅳ为由 出发，与有向线段 + m方向一致的射 线．M 和Ⅳ所在直线将平面分为4个区域；A，B，C，D，如图3所示，其中： ；射线 和Ⅳ形成的扇形区域(包括射线Ⅳ 和N)； ． B；射线 与Ⅳ 的反向射线形成的扇形区域(包括 Ⅳ 的反向射 『 ≤ ＼ c：射线Ⅳ与M的反向射线形成的扇形区域 包括 的反向射 l ． ． 。。 ． 残 J； f { ． 一 ／ 口 D：M的反向射线与N的反向射线形成的扇形区域· ＼／ 。＼／ 显然，ST中的点只可能在区域 A，B， 中，并且在这 3个区域中 ： D r： 的点形成的点串在s了1中是连续分布的．用 SA，SB，SC表示这 3个点 串．如图 3所示 ，SA一( 2 5 s4，s5)；SB一( c， 1)；SC=(s6， ·如·S9)． 图。 凹点的 个区域 从可见点串的几何特性可得出如下结论； 结论 1．如果 SA为空，并且SB和SC均不为空．则 SB中的最后一个点 与 SC中的第一个点 “+ 必 在多边形的同一条边上． 可用反证法证明此结论．如图4所示．如果 和“+ 不在同一条边上，则“和s“ 之间存在多边形顶点， 且由于5 和“一 在s了1中是相邻的，因此“与s + 之问的这些顶点是不可见的．不失一般性，设在s 与s 之 间存在一个不可见的顶点 ．如果 在 的区域 A内，如图4(a)所示，则 必可见，这与“顶点 是不可见 的”相矛盾；如果口在有向线段 五： 的左边，如图4(b)所示，则 也肯定可见，这也与“顶点 是不可见的” 相矛盾；如果 在 的右边，不妨设 在射线 M的右边，如图4(c)所示，则射线 与线段 m一 ]的交 点 “可见，这与““和“+ 在s了1中是相邻的”相矛盾．如果 在线段[ “+ ]上，则 必可见，这也与“顶点 是不可见的”相矛盾．因此 与“+ 之问不可能存在多边形顶点，即“与 + 必在多边形的同一条边上，故结 论成立． 证毕- Ⅳ ≥ l、≥≤ 二s 入 B ‘ ～入 B (a】 (b) (c) 图4 和 必在同 条边上 结论 2．如果SA为空，则 SB和SC必不为空． 对于结论 2，也可用反证法证明，在此不再赘述． 下面介绍本文基于顶点可见性的凹多边形局部剖分算法： (1)搜索凹点．如果多边形没有凹点，则算法结束，否则，设搜索到的凹点为当前凹点； (2)搜索当前凹点的可见点串ST，并由此求取点串SA，SB和SC； 维普资讯 http://www.cqvip.com l2期 金文华等：基于顶点可见性的凹多边形快速凸分解算法 (3)如果 A不为空，则 ： ① 当SA中有多个凹点，并且如果n也同时位于其中某几个凹点 的区域 A中，则将这些凹点放人集合 P中； ② 否则，将SA中的所有可见点放人集合 P中； ③ 如果集合 P中的顶点只有一个，则将其作为选中的点，否则 利用下列方法求出 P中顶点的权值，取权值最小者为选中的点： 设 5 为 P中的任一点，其与 构成的矢量为一Sj．射线M 的单位 矢量为而，射线Ⅳ的单位矢量为 ． mid一 痂+ ： mid构成区域 A的平分线矢量．权值 g 可取下列矢量的z坐标 值 ： N C ) Af． 口 (舾 ) 图 5 集台 SP中可见点的权值计算 g 一 [ +mid] 当g =0时，可见点 正好在区域A的平分线上，此时引剖分线得到的凸多边形形态最好． (4)如果SA为空，由结论 2可知，SB和SC必不为空．设5 为SB中的最后一个点，5t+1为SC中的第一 个点．由结论 l可知，5 和5t--1必在多边形的同一条边上．求线段[ s + ]与区域A平分线的交点为所选择的 点 ； (5)设从步骤 3或 4中选择得到的点为“，从 至“引剖分线，将多边形切割成两个多边形； (6)对新产生的两个多边形按上述步骤递归地进行凹多边形凸分解处理，直到所有的多边形均为凸多 边形为止． 在上述判断过程中，由于引入了判断条件①，使得本文算法在对于 点所对应的可见点串这一局部范 围内．可以一次消去两个凹点，从而尽可能减少凸多边形个数． 5 结 论 由于本文算法在每次剖分处理之后，至少会减少一个凹点，因此算法的整个处理过程最多只需进行 次剖分操作．从文献[21]可知，求取凹点的可见点串算法的时间复杂度为0( )．因此本文的时间复杂度也为 O(mn)． 虽然本文算法与Rogers算法的时间复杂度相同，但本文算法在每次剖分操作时消去两个凹点的概率远 大于Rogers算法(此概率问题的本质是点落在区域内的概率远大于落在直线上的概率．具体证明在此不赘 述)．另外，本文算法在作剖分操作时无须作过多的求交运算．因此本文算法的实际运行速度快于 Rogers算 法． 由于所有剖分操作均是在凹点的区域A中进行，并且利用权函数可使剖分得到的凸多边形具有很好的 形态，这是本文算法优于Rogers算法的主要特色．本文权函数与文献Es]中的权函数的最大不同之处在于本 文方法不需要求角度． 本文算法已应用于工厂设计软件 PDSOFT Piping中．PDSOFT Piping是一个较为成功的工厂设计配 管软件，在工厂建模、单线图、平剖图、材料表、模型渲染和消隐等方面均有独特之处．本文算法在平剖图自动 消隐的底层算法凹多边形凸分解中得到应用并产生了很好的效果． 参 考 文 献 Asano Te~uo．Asano Takao．Mirfimum psrthion of polygonal region~into trapezoids．In：Proe 24th Annual FOCS Symp．New York IEEE Computer Press·1983．233～ 241 Schachter B Decomposition of po lyKons into coQvex 9ets．IEEE Trans 0n Computers，1978 r C一27(11)：i078~ 1082 维普资讯 http://www.cqvip.com 1460 计 算 机 研 究 与发 展 1999年 3 肖忠晖，卢振荣，张谦．简单多边形凸单元剖舟的编码算法．计算机学报．1996．19／5)：477～481 (Xiao Zhonghui，Lu Zhenrong．Zhang Q Jan Coding atgorithm for decomposing a simp Le polygon into coR％,ex parts／in Chinese) Chinese Journal 0f Computers．1 996，1 9(6)：4 77～481) 4 汪矗业．在卫．简单多边形分解戚凸多边形差组台的算法．汁算机辅助设计与图形学学报，l992，4(2)：22～29 (Wang Jiaye．Wang Wei Algorithm for finding convex decomposition of simple polygons Journal of Computer．added [k~sign ＆ Compu【 r Graphics(in Chinese)t l992．4f2)：22～ 29) 5 王钲旋．李文辉，魔云阶 一个加权割分简单多边形为凸多边形的算法 计算机学报，1998，21(3)：229～233 (Wang Zhengx~a Li Weahuit Pang Y,miie．A weighting algorithm for decomposing a simpte po Lygon into convex po Lygons(in Chinese) Chinese Journal Computers，1998，21(3)：229～ 233) 5 Rou rke()J，Supowi【J K．Some NP hard polygon decompo skioa problems IEEE Trans oR Information Theory，l983t IT 29f2) 181～ l90 7 Feng Houyuan，Pav[idis T．Decomposition 0f polygons into simpler components：Feature generation for syntactic pattern recognition IEEE TraⅡs on Conlputers．1975，C 24(6)：636～ 550 8 Avis D．Toussaint T G．An efficient algorithm for decomposing a polygon iRto star shaped po[ygo~．Pattern Recognition，l981·13(6)： 39 5～ 398 9 Berg M de，Krevetd M van．O,,ern]~rs M ．Sehwarzkopf O．C~mputadona[Geometry Algorithms and Applications．Berlin HeideIbery r Germany Sp~ng Ver[ag．1 99 7 49～ 55 1 0 Rogers F D Procedura[Elemenvs for Computer Graphics New York：McGraw Hd[，I985 l【 Bykat A Automatic generation oftriangular grid：I— subdivision of general polygoninto convex subregionstII triangulation of convex polygons．InrI Journal for Numer M eth Eng．1976．c1∞ 一l329～ l342 12 Chazel Le B．Dobkin P D Decomposing a polygon into its co parts In：Proc 11th Annual SIGACT Syrup 0n Theory of Computing New York：Association for Computer Machinery Inc，1 979．38～48 1 3 Chazelle B，Dobkin P D Optimal CoDvex decomp~it[ons In=Toussaint T Godf~ed ed．Computational Geometry，Amsterdam，Hottand： Nor[h HolIand，1 98 5．63～ 133 14 Keil M Decomposing poIygo~ into simpler comgonents~Ph D dissertation]．University of Toronto，1 983 1j (金文华 ．何涛，刘晓平等．基于有序茼单多边形的平面点集凸包快速求取算挂．计算机学报．1 998．gl(6)；533～∞9) (Jin Wenhua，He Tan，Liu Xiaoping al A fast convex hul【a Lgorithm of planar point set based 0n sorted simple polygon Chinese Journa【of Computers(in Chinese)．1998，21(6){533～ 539) 1 6 垒文华，何祷，唐卫清等 简单快速的平面散乱点集凸包算法．北京航空航无大学学报 ，1999，25(1)：72～75 ／JinWenhua．HeTao．TangWeiq[ng Ⅱ ．A simplefast coR％,ex hn【【algorithm of planar point set(in Chinese) Chinese Journal ofBe ijing Univ ofAero 8LAs[ro，19 9目，25(1)：72～75】 17 Jin Wenhua，Liu Xiaoping，Yu Tiefeng eg a1．Automatic featlife conlour recognition of component in piping design CAD system In：Pr0c of CAD＆ Graphics’97．Be[jing：Internationa[Academic Pubhshers，1 997 752～75．5 lB 金文华，何涛，唐卫清等 管道CAD元件特征轮廓的识别 计算机辅助设计与田形学学报．1998，1O(增刊)：169～173 (Jin Wenhua，He Tan Tang Weiqing et a1．Feature co,tour recognition of component in piping CAD system(in Chinese) Journal of Computer Aided Design＆ Computer Graphics，1 998，10(supp[)：169～173) 19 盘文华，何涛，刘晓平等．改进的管道CAD元件特征轮廓识捌方法 计算机辅助设计与图形学学报 1999，11(2)：1 47～1弼 (Jtn Wenhua．He Tao．Liu Xlaop[ng ．Improved feature contoHr r~ognition of component in piping CAD sys㈣ ．Journal of Computer Aided Design&ComputerGraphics，1999．11(2)：147～1 50 盘文华，何涛，唐卫清等．凸多边形窗口的快速线裁剪算法 见：中目计算机田形学的新发展__Ch[nagraph’98论文集 北京：清华大学 出版杜，1 998．25～鲫 (JinWenhua．He Tan，TangWei Qing et A fas【algorithm for convex po Lygonline clipping(inChinese)．In：Chinagraph’98 Be ijing Tsinghua University Press，1g9g 25～30) 21 (金文华，何祷，唐卫清等．简单多边形可见点问题的快速求解算法．计算机学报．1 999，22(3)：275～282 (Jin Wenhua，He Tan，Tang Welqing et f_A fast point vis bib v algorithm for simple polygon(in Chinese) Chinese Journat Computers 1999．22(3)：275～282) 22 金文华．唐卫清，唐荣锦 简单多边形顶点凸凹性的快速确定算j击 工程图学学报，1998，(1)：66～70 (Jin W enhua，Tang Weiqing，Tang Rongx[ A fast algorithm for determining the convexity concavity of vertices of simple polygon． Chinese Journal of Engineering Graphics(in Chinese)，1 998，(1 ：65～70】 维普资讯 http://www.cqvip.com