不规则三角网中约束线嵌入.pdf

I S S N i 0 0 0 0 0 5 4 清华 大学学报(自然科学 版)2 0 1 4年 第 5 4卷 第 1 2 期 可 J T s i n g h u a U n iv(S e i&T e c h n o 1)，2 0 1 4，Vo 1 5 4，N o 1 2 不规则三角网中约束线嵌入 郑辑 涛。，张 涛，何 红 红，朱 纪 洪(1 清华大学 计算机科学与技术系，北 京 1 0 0 0 8 4；2 空军装备研究院 航空气象防化研究所，北京 1 0 0 0 8 5)摘 要：该 文针对有 约束 情况 下的不规则 三角 网重建，分析 了约束线影响域的各种典型情况，在 此基础上提 出了一种 约 束线嵌入方法。该方法首先搜 索约束 线影响域，提取影 响域 的边界，根据凹 凸性判 断找到影 响域边 界上 的 凸角，并在 凸 角处 生成新 的三角形，通过对影响域 的重剖分完成 约束线 的 嵌入。同时给 出 了详细算 法流程并 进行 了实 验，结 果表 明：该算 法鲁棒 稳定，能够实现各种复 杂约束 情况 下的不规则 三 角 网 重建。关键词：不规则三角 网；约束线；嵌入；凹凸性 中图分 类号：T P 3 9 1 文献标志码：A 文 章 编 号：1 0 0 0 0 0 5 4(2 0 1 4)1 2-1 5 5 5-0 5 Emb e d d i n g o f a c o n s t r a i n e d l i n e i n t o a t r i a ng u l a t e d i r r e g u l a r n e t wo r k ZHE NG J it a o Z HANG Ta o ，HE Ho n gh o n g ，Z HU J i h o n g (1 De p a r t me n t o f Co m p u t e r S c i e n c e a n d Te c h no】o g y，T s i n g h u a Un i v e r s i t y，Be i j i n g 1 00 0 8 4，Ch i n a；2 Av i a t i o n M e t e o r o l o g i c a l a n d Ch e mi c a l De f e n s e I n s t i t u t e，Ai r F o r c e E q u i p me n t R e s e a r c h Ac a d e me，B e ij i n g 1 0 0 0 8 5，C h i n a)Ab s t r a c t：Th e r e c o n s t r u c t i n g o f t r i a n gu l a t e d i r r e g u l a r ne t wo r k s wi t h c o n s t r a i n e d l ine s i s a n a l y z e d f o r a l l k i n d s o f i nf l u e n c e d o ma i ns A c o n s t r a i n e d l i n e s e m b e d d i n g m e t h o d i s g i v e n t h a t f i r s t c h e c k s t h e i n f l u e n c e d o ma i n o f e v e r y c o n s t r a i n e d 1 i ne a n d t h e n e x t r a c t s t h e i n f l u e n c e d o ma i n b o u n d a r y Th e s y s t e m t he n e v a l u a t e s t h e c o n v e x a n gl e s o n t h e b o u n da r y a c c o r d i n g t o t h e c o n c a v e c o nv e x p r o pe r t y a n d g e ne r a t e s a n e w t r i a n g l e a t e v e r y c on v e x a n g l e t o e mbe d t he c o ns t r a ine d l i n e s b y a g a i n p a r t i t i o ning t h e i n f l u e n c e d o ma i n Te s t s s h o w t h a t t h e a l g o r i t h m i s s t a b l e a n d r o b us t a n d c a n s u c c e s s f u l l y r e c o n s t r u c t t r i a n g u l a t e d i r r e g u l a r n e t wo r k wi t h c o mp l e x c o ns t r a ine d l i n e s Ke y wo r d s：t r i a n g u l a r i r r e g u l a r n e t wo r k；c o n s t r a i n e d l i n e；e mbe d d i n g；c o n c a v e c o n v e x 重建不规则三角网是地理信息系统、虚拟现实、地学分析和逆向工程中的热点问题。实际情况下多 数地貌特征如等高线、山谷线和 山脊线等需要用约 束线来表达，约束条件下建立不规则三角网可 以在 9 20 1 55 5 1 55 9 较小的实测数据前提下提高建模 的精度。目前，关 于约束 条件 下 不 规 则 三 角 网 的重 建 通 常 有 2类 方 法：第一类是在建立三角 网的 同时考 虑约束条件的 影响口 ，这种方法时间效率较低，实际中已很少使 用；第二类是两步法l_ 3 ，第一步是在不考虑约束 条件 的情 况下 建 立 不规 则 三 角 网，第 二 步再 把 约 束 线强 行嵌 入 到三 角 网 中，这 种 方 法 不 仅 可 以充 分 利 用 点云 重构 三角 网 的研 究 成 果，而 且 由于 时 间效 率 高而受到研究者的普遍关注。两步法 的关键在于约 束线 的嵌入。文 4 提出了影响域的概念，同时提出 了适用 于 四边 形 影 响 域 的“四边 形 对 角 线 交 换”算 法；文 5 提出了一种“(+2)边形对角线交换”算 法，解决 了影响域为任意多边形情形下的约束线嵌 入 问题，但 由于该算 法 需 要 将 影 响域 分 为 2个 多 边 形后 分别 剖分，其 中还要 比较 点到 直线 的距离，因而 程序实现工作量较大，时间效率低。文 6 提 出了“轨迹生成”法，该算法从约束线的一端出发，对影响 域中的所有对角线依次进行交换，直到约束线嵌入 为止。实 际上 是对“四边 形对 角线 交换”算法 的重 复 调用，因而程序 实 现 简 单 明了。但 该 算法 也 有 其 局 限性，当影响域为凹多边形时可能会失效。在任意 影响域中强行嵌入约束线是否一定能够通过多次对 角线交换来实现也没有给 出严格证 明。文 7 基于 强 可交 换对 角线 的思 想 给 出 了肯 定 的证 明，认 为影 响域 中的每 个三 角形 至少 有一 条边在 影 响域 的边界 上，称 为该 三角形 的交换边，并 且 除首末 2个 三角形 外，每个三角形有且只有 1 条交换边。文 8 提出了“插入一 交 换”法，在 凸 多边 形 时进 行 交 换，在 凹 多边 收稿 日期：基金项 目：作者简 介：通信 作 者：2 O 1 4 0 5 0 7 国家 自然科学基金 资助项 目(6 1 1 0 4 0 8 2)郑辑涛(1 9 7 5 )，男(汉)，河北，博士研究生 朱纪洪，教授，E-ma i l：j h z h u ma i l t s i n g h u a e d u c n 清 华 大 学 学 报(自 然 科 学 版)形时插入交点，增加 了点数。文 1 2 的对角线循环 交换法很多情况下 会引起对角线 的重复交换，影响 了约束线 的嵌入效率。本 文 分析 了约束 线影 响域 的各 种 情 况，提 出 了 一种 约束 线嵌 入方 法。其 思路 是搜索 判 断约束 线 影 响域，顺 序排 列 约束线 两侧 的影 响域 边 界，然 后根 据 凹凸性判断，逐一割去凸角生成新的三角形，从而完 成对约束线影响域 的重剖分。1 基本概念 定义 1 与约束线相交 的三角形构成 的集合，其外边界为一多边形，此多边形称为该约束线 的影 响域。例如图 1中，S E为约束线，其中阴影部分是 约束线 s E的影响域。定义 2 约束线的一端作为起点，则 另一端称 为终 点。例如 图 1中 S为起 点，则 E为终 点。定义 3 构 成影 响域 多边 形 的外 边 界 即为影 响 域 边界，如 图 1中 S，A，C，F，E，G，D，B)构 成 了 S E 的影响域边界。如果把约束线看作一条起点到终点 的有向线段，则位于其左侧的边界称为左边界，通常 以起点到终点的顶点有序序列表示，如 图 1中 s，A，C，F，E)；同理，位于其右侧 的边界称为右边界，如图 1中 s，B，D，G，E。边界上任意 2个相邻的 顶点 构成 1 条 边界 边。定义 4 一 般情 况下 影 响域 中的 顶点 只 出现 在 影响域边界上，当一个顶点 出现在影响域内部时，该 顶 点称 之为 悬挂 点，如 图 2中的点 X。定义 5 三角形 中包含悬挂点且不与约束线相 交 的边称 为 悬挂 边，如 图 2中的边 AX。定义 6约束线左右两侧 边界上，对 于约束域 边界多边形，每个顶点处的内角小 于 1 8 0。则称为 凸 角，大 于 1 8 0。则称 为 凹角，等于 1 8 0。则 称为平 角。例 如 图 1中，边 界顶 点 C处 S AC为 一 凸角。定义 7 矢量菇 到 的逆时针夹角用(荫，S A)表示，称 为矢 量 问夹角。定义 8 构成影响域的三角形中，与约束线 S E 相交 的边 称 为相交 边，如 图 1中 的边 AB 和 BC等。图 1影响域 等基本概念示意 图 S S (a)凸影响域(b)凹影响域 图 2约束线影 响域 中悬 挂点 定 理 1 任 意多边 形 至少 有 1 个 顶 点 处 的 内 角 为 凸角。证明假设对任意 n边形，所有顶点处内角均 不为凸角，则有 个 内角均大于等于 1 8 0。，故 边 形 的 内角 和 大 于等 于 1 8 0。，这 与 n边 形 内 角 和 为(n一 2)1 8 0。矛 盾，因 此 假 设 不 成 立，原 命 题 得证。定理 2任意 边形，每次在凸角顶点处沿前 后两相邻顶点割去 1 个三角形，经过(一3)次分割，分成(一2)个三 角形。证明对任意 边形，定理 1保证其有 凸角存 在，而且 每 割 掉 1个 三 角 形，多 边 形 顶 点 和 边 数 减 1，由于定理 1 保证每次都能成功分割，因此只需进 行(，z 一3)次分 割 操 作，剩 余 3个 点，构 成 最 后 的 三 角 形。约 束线 影 响域通 常有 以下 几种：1)一般影 响域：约束线段 的影 响域边界 为一 凸多 边形，如 图 3 a 所 示。2)凹影响域：约束线段影 响域边界上有凹角，即边 界多边 形 中有 凹角 存在，如 图 3 b所 示。3)悬 挂 影 响域：约束 线 段 影 响域 内部 出现 悬 挂点和悬挂边，此时会 有与约束线相交 的三角形而 没有任何一边 出现在影响域边界上，如 图 3 c 所示。此类 影 响域 采 取 对 角 线 交 换 法 会 出 现 无 法 交 换 的 情 况。4)复 杂 影 响 域：约 束 线 的 影 响 域 边 界 出 现 凹 角同时又有悬挂点存在，如图 3 d所示。此类影响域 采 取对 角线 交换 法会 出现无法 交换 或 重复 交换 的情 况，且对 角线交 换或 重复 交换 会 引起复 杂 的拓扑 重 构。2 约束 线嵌入 2 1影 响域 搜索 以图 4为 例说 明搜 索影 响域 的步骤：第一步，找到初始相交三角形。郑辑 涛，等：不规则三角 网中约束线嵌入(a)一般影响域(b)凹影响域(c)悬挂影响域(d)复杂影响域 图 3影响域分 类 图 4影 响域 的 判 断 对 于任 一 条 约束 线 如 S E，对 起 点 S 的邻 接 三 角形逐一判断，找到与约束线 S E相交的一个三角 形如s AB，即为构成约束域的第一个三角形。用 角度可以判断是否相交，例如 图 4中(S 百，s )+(，)与 (菇，)相等，因此可以确定 S E 与 S AB 相 交，同 时 记 录 当 前 相 交 三 角 形 S AB、相交边 AB和初始 左右边界 S，A、S，B)。第 二步，根 据拓 扑关 系搜 索影 响域。从 当前相交边 AB开始，找到其邻接三角形 中 不同于当前相交三角形的三角形即AAB C，取当前 相 交边 AB在 该 三角形 中 的对 应 顶点 C，判 断 C是 否与约束线终点 E相同，如相 同则 E保存至左右 2 个边界并结 束搜索；如不 同则判断对 面顶点 c与 S E 的左右位置关系，如果在左侧，C记 录入左侧边 界，当前相交边更新为 B C，如果在右侧，C记录入 右侧 边界，当前 相 交边更 新 为 AC，同时 当前相 交 三 角形 更新 为ABC并 重复 第二 步。搜索结束得到影响域，实 际是约束线左右两侧 边界 顶点 的有 序 序列 即左 侧边 界 S，A，D，G，H，-厂，K，E)和右侧 边 界 S，B，C，F，I，E)。值得 注 意 的是，当有悬 挂点 存在 时，会 有 非相 交 边 GH 出现在影响域 内，根据相交边 的邻接三角形 搜索，会导致某个顶点出现 2次。例如图 4中，点 G 在 DF G 中 是 相 交 边 DF 的 对 应 顶 点，同 时 在 GHI中也 是相 交边 HI的对 应 顶点，为 了 区分 可 以用不同字符，表示，使得真实获取 的边界如 图 5 所 示。这 种处 理方 式避 免 了对 悬 挂点 的单 独处 理 _ 1，使得算法简单有效，对各种影响域具有普适性。图 5实 际边 界 处 理 2 2 约束 线嵌 入 确定影响域后，需要通过重新剖分完成约束线 的嵌 入。剖分 方法 是 在 影 响域 边 界上 判 断 凸角，在 凸角 处生 成新 的三角形。判 断 凹凸角 可 以根据矢 量 积符号，在任一除起点终点之外 的边界点处取构成 该角 的相 邻矢 量，方 向沿 起 点 到 终 点。前后 两 矢 量 做矢 量 积；对 于左 边 界，矢 量 积 小 于零 为 凸 角；对 于右边 界，矢 量 积大 于零 为 凸角。图 6中，A百B o，葫币 o，因此点 B处是凸角，点 H处是 非 凸角。图 6 凹 凸角 判 断 凸 角 处 的边 界 点 与前 后 相 邻 顶 点 建 立 新 三 角 形，同时把该凸角顶点从边界集合删除。重复此操 作直到左右边界上只剩下包括约束线两端点在 内的 3个点，形成三角形并结束。对 于边界 顶 点数 为 的 影 响域，定 理 1和 2保 证经 过(一4)次 割角操 作 可完成 约束 线 的嵌入。输入为非约束情况下不规则三角网和约束线集 合，输 出为 约束线 嵌 入 后 的不 规 则 三角 网，完整 算 法描 述 如下：步骤 1 任取一条约束线，判断搜索其影响域，获取构成影响域左右边界 的顶点有序序列。步骤 2 分别针对左右 2个影响域边界集合判 断是 否 只有 3个 点，是 则 生成 1个新 三角 形并 结束；否则 转 步骤 3。步骤 3 顺序在边界集 合中取相 邻的 3点，判 断 凹 凸角，如 果是 凸角，则 生 成 新 三 角形，并 在边 界 集合中删除凸角对应的边界顶点；转步骤 2。图 7为一个约束线影 响域 的重剖分过程，7个 郑辑涛，等：不规则 三角网中约束线嵌入 1 5 5 9 SUN W e n b i n，LI U Xi l i a n g，LUAN Xi a o h u i，e t a 1 M e t h o d s t u dy o ff c r e a t i n g i r r e g u l a r t r i a n g l e me s h wi t h r e g a r d t o c o n t o u r l i n e a n d c o n c a v e b o u n d a r y c h a r a c t e r i s t i c s E J G e o g r a p h y a n d G e o I n f o r ma t i o n S c i e n c e，2 0 1 0，2 6(4)：5 0 5 6 (i n Ch i n e s e)3 3 刘学 军，龚健雅约束数据域 的 De l a u n a y三角剖分与修改算 法 J 测绘学报，2 0 0 1，3 0(1)：8 2 8 8 LI U Xu e j u n，GONG J i a n y a De l a u n a y t r i a n g u l a t i o n o f c o n s t r a i n e d d a t a s e t口 A c t a G e o d a e t i c a e t C a r t o g r a p h i c a Si ni c a，2 00 1，3 0(1)：8 28 8 (i n Ch i n e s e)4 李立新，谭建荣约束 D e l a u n a y三角剖分 中强行嵌入约束边 的多 对 角 线 交 换 算 法 J 计 算 机 学 报，1 9 9 9，2 2(i 0)：1 1 1 41 1 1 8 LI Li x i n，TAN J i a nr o n g M u l t i p l e d i a g o n a l e x c h a n g i n g a l g o r i t h m f o r i n s e r t i n g c on s t r a ine d b o u n d a r y i n c o n s t r a i n e d De l a u n a y t r i a n g u l a t i o n F J C h i n e s e J o u r n a l o f C o mp u t e r s，1 9 9 9。2 2(1 0)：1 1 1 4 1 1 1 8 (i n Ch i n e s e)5 卢朝 阳，吴成柯，陆心如简单多边形 的优化 三角剖分 F J 电子学报，1 9 9 1，1 9(2)：8 28 7 I U Zh a o y a n g W U Ch e n g k e，LU Xi n r u Op t i ma l t r i a n g u l a t i o n o f s i mp l e p o l y g o n J A c t a E l e c t r o n i c a S i n i c a，1 9 9 1，1 9(2)：8 28 7 (i n Ch i n e s e)6 卢朝 阳，吴 成柯，陆心如优 化 TS P算 法的完善及推广 J 电 子 学 报，1 9 9 4，2 2(1)：8 6 8 9 LU Zh a o y a n g W U Ch e n g ke，LU Xinr u A g e n e r a l i z e d a l g o r i t h m o f o p t i ma l t r i a n g u l a t i o n o f s i mp l e p o l y g o n J Ac t a El e c t r o n i c a S i n i c a，1 9 9 4，2 2(1)：8 689(i n Ch i n e s e)7 周 晓云，刘慎权实 现约 束 De l a u n a y三 角剖 分 的健壮 算法 J 计算机学报，1 9 9 6，1 9(8)：6 1 5 6 2 4 ZHOU Xi a o y u n，LI U S he n q u a n A r o b u s t a l g o r i t h m f o r c o n s t r a i n e d De l a u n a y t r i a n g u l a t i o n J C h i n e s e J o u r n a l o f Co rn p u t e r s，1 9 9 6，1 9(8)：6 1 56 2 4(i n Ch i ne s e)8 陈学工，黄 晶晶De l a u n a y三角 网剖分 中的约束边嵌 入算法 J 计算 机工程，2 0 0 7，3 3(1 6)：5 65 8 C HE N X u e g o n g，HUANG J i n g j i n g Al g o r i t h m o f i n s e r t i n g c o n s t r a i n e d e d g e i n t o De l a u n a y t r i a n g u l a t i o n J C o mp u t e r Eng i n e e r i n g，2 0 0 7，33(1 6)：5 65 8 (in Chi n e s e)9 翁巧琳，姜昱 明基于等高线的三角 网建模 及真实感 地形重 建 F J 计算 机仿真，2 0 0 7，2 4(1 0)：1 8 81 9 1 WENG Qi a o l i n，J I ANG Yu mi n g Tr i a n gu l a r n e t wo r k mo d e l i n g a n d t e r r a i n r e c o n s t r u c t i o n b a s e d o n c o n t o u r s J Comp u t e r Si mu l at i o n，2 0 0 7，2 4(1 0)：1 8 81 9 1 (i n Ch i n e s e)1 0 刘少华，程朋根，史文 中约束 De l a u n a y三角 网生成算 法研 究 J 测绘通报，2 0 0 4，4(2 3)：47 LI U S h a o h u a，CH ENG P e n g g e n，SHI W e n z h o n g Al g o r i t h m s t u d y o f t h e c o ns t r a i ne d De l a u n a y t r i a n g u l a t i o n g e n e r a t i o n 刀B u l l e t i n o f S u r v e y i n g a n d Ma p p i n g，2 0 0 4，4(2 3)：4 7 (i n Ch i n e s e)1 1 孟永东，徐卫亚，田斌，等基 于带约 束三 角剖分 的三维地 质建 模 方 法 及 应用 _ J 系 统仿 真学 报，2 0 0 9，2 1(1 9)：5 9 855 9 8 9 M ENG Yo n g d o n g，XU W e i y a，TI AN Bin，e t a 1 M e t h o d o f mo d e l i n g 3-D g e o l o g i c a l mo d e l i n g a n d i t s a p p l i c a t i o n b a s e d o n c o n s t r a i n t D e l a u n a y t r i a n g u l a t i o n J J o u r n a l o f S y s t e m Si mul a t i o n，2 0 09，2 1(1 9)：5 9 8 55 9 8 9 (i n Ch i n e s e)1 2 刘合辉，罗勇军基于等高线的三角网快 速构建 与处理 J 测 绘 工 程，2 0 0 9，1 8(2)：5 5 5 8 LI U He hu i，LUO Yo n g J u n Sp e e d y c o n s t r u c t i n g a n d p r o c e s s i n g TI N b a s e d o n c o n t o u r s J E n g i n e e r i n g o f S u r v e y i n g a n d M a p pi n g，2 0 0 9，1 8(2)：5 55 8 (i n Ch i n e s e)1 3 宋 晓眉，张晓东，李 建林一种高准确度 的约束 D e l a u n a y三 角网生成算 法研究 J 地理与地理信息科 学，2 0 0 9，2 5(1)：9 9 1 O 3 S ONG Xi a o me i，ZHANG Xi a od o n g，LI J i a n l i nS t u d y o n a n e w C D T a l g o r it h m b a s e d o n h ig h a c c u r a c y J Geo g r a p h y a n d Ge o I n fo r ma t i o n Sc i e n c e，2 0 0 9，2 5(1)：9 9 1 0 3 (i n Ch i n e s e)1 4 陈学工，李 源，曹建，等D e l a u n a y三角 网剖分 的约束 边嵌 入改进算法 J 计算机 工程 与应 用，2 0 0 9，4 5(2 4)：2 3 5 2 3 7 CHEN Xu e g o ng，LI Yua n，CAO J ia n。e t a 1 I mp r o v e d a l g o r i t h m o f i n s e r t i n g c o ns t r a i n e d e dg e i n t o De l a u na y t r i a n g u l a t i o n J C o mpu t e r E n g i n e e r i n g a n d Ap p l i c a t i o n s，2 0 0 9，4 5(2 4)：23 52 3 7 (i n Chi n e s e)1 5 俞 亚磊，罗永龙，郭 良敏，等D e l a u n a y三角 网 中任 意约束 线段嵌入算法研究 J 测绘科学，2 0 1 3，3 8(4)：6 16 3 YU Ya l e i，LUO Yo n g l o ng，GUO Li a n g mi n，e t a 1 Al g o r i t h m o f i ns e r t i n g a ny c o ns t r a ine d l i n e i nt o De l a u n a y t r i a n g u l a t i o n J S c i e n c e o f S u r v e y i n g a n d Ma p p i n g，2 0 1 3，3 8(4)：6 16 3 (i n Ch i n e s e)