（通信与信息系统专业论文）二维组合曲线的等距方法研究.pdf

河海大学硕士研究生论文摘要 摘要 二维组合曲线的等距方法是c a d c a m 领域中的一个重要课题，并在型腔 环切加工刀具轨迹自动生成技术中得到广泛研究。现有应用最广泛的封闭二维组 合曲线等距方法是边等距法，该类方法的主要不足是尚不能很好地处理带有孤岛 的封闭二维组合曲线，且效率有待提高。研究具有良好效率和适用范围的二维组 合曲线等距方法，可以使刀具加工路径生成技术更加精确和有效，为型腔加工技 术领域提供强大的技术支持，因而对于这一领域有着重要的实际意义。在深入研 究c h o i & p a r k 边等距法的基础上，本文着眼于研究一种能够处理带有孤岛的封闭 二维组合陷线的等距方法。 本文提出了“一种新的带有孤岛的封闭二维组合曲线等距方法，该方法将辨环 和孤岛看作独立的对象。首先，分别对外环和孤岛单独进行局部干涉区间的检测 和删除，得到初步有效曲线；其次，采用本文提出的网格法检测出外环及孤岛中 的干涉凹点并确定全局干涉边对：第三，调用经本文修改的c h o i & p a r k 边干涉检 测程序，统一检测出所有的全局干涉区间，并分别删除外环及孤岛各自的全局干 涉区问；最后，对曲线剩余部分进行一次等距操作，得到最终的有效等距线。 本文带有孤岛的封闭二维组合曲线等距方法具有以下主要特点：第一，将外 环和孤岛看作独立对象，实现了对带有孤岛的封闭二维组合曲线的等距，拓展了 等距方法的适用范围：第二，提出一个网格法，用于全局干涉区间的检测，避免 了对全局干涉部分的等距操作以及对初步等距线中圆弧边的离散化，减少了计算 量，提高了等距方法的效率。 最后，在v i s u a lc h 缶0 下实现了本文提出的方法，并进行了大量的实验测 试，实验表明该方法具有较好的效率和健壮性，具有良好的工程应用价值。 关键词：二维组合曲线，等距，多边形链，边等距法，网格法 二维组合曲线的等距方法研究 a b s t r a c t t l l e o f f s e t t i n gt e c h n o l o g yo f2 d c o m p o a n dc u r v ei s ab a s i cp r o b t e mi n c a d c a m a n dh a sb e e nw i d e l ys t u d i e di nt 0 0 1p a t h g e n e r a t i o nf o rp o c k e t m a c h i n i n g c u r r e n t l y , t h em o s tw i d e l yu s e do f f s e t t i n gm e t h o df o rc l o s e d2 d c o m p o u n d c u r v ei sp a i r - w i s eo f f s e t t i n gm e t h o d ，t h ed i s a d v a n t a g eo ft h i st y p eo fm e t h o d si st h a t t h e yc a nn o td e a lw i t hc l o s e d2 d c o m p o u n dc u r v e sw i t hi s l a n d sv e r yw e l l a n dt h e e f f i c i e n c yi se x p e c t e dt ob ei m p r o v e d s oi ti su r g e n ta n dm e a n i n g f u lt of i n dw a y st o i m p r o v et h ee f f i c i e n c ya n da p p l i c a b i l i t yf o rt h ec u r r e n to f f s e t t i n gm e t h o d s a f t e ra d e 印r e s e a r c hi n t oc h o i & p a r kp a i r - w i s eo f f s e t t i n gm e t h o d ，t h i st h e s i sa i m sa tf i n d i n g a ne f f e c t i v eo f f s e t t i n ga p p r o a c hw h i c hc a nd e a lw i t hc l o s e d2 d c o m p o u n dc n r v e s w i t hi s l a n d s an e wo f f s e t t i n ga p p r o a c hf o rc l o s e d2 d c o m p o u n dc n r v e sw i t hi s l a n d si s p r o p o s e d i nw h i c ht h eo u t l o o pa n di s l a n d sa r e 仃e a t e d a si n d e p e n d e n to b i e c t s f i r s t l y , 1 0 c a li n t e r f e r i n gr a n g e so ft h eo u t l o o pa n di s l a n d sa r ed e t e c t e da n dd e l e t e d r e s p e c t i v e l yt oo b t a i nt h er a wv a l i dc u r v e ；s e c o n d l y , h a t e r f e r i n gc o n c a v ev e r t i e e sa r e d e t e c t e da n dg l o b a l i n t e r f e r i n gp a i r sa r e d e t e r m i n e db ya p p l y i n gag r i d d i n g a p p r o a c h ；t h i r d l y , a l lg l o b a li n t e r f e r i n gr a n g e sa r ed e t e c t e db yi n v o k i n gam o d i f i e d c h o i & p a r kp a i r 试s ei n t e r f e r i n gd e t e c t i o np r o c e d u r e ，a n d9 1 0 b a li n t e r f e r i n gr a n g e s b e l o n g i n gt oo u t l o o pa n di s l a n d sa r ed e l e t e dr e s p e c t i v e l y ；l a s t l y , t h ef i n a lv a l i do f f s e t c u r v ei so b t a i n e db yo f f s e t t i n gt h er e m a i n e dp a r t so f t h er a wv a l i dc u r v e t h ep r o p o s e do f f s e t t i n ga p p r o a c hf o rc l o s e d2 d c o m p o u n dc u r v e sw i t hi s l a n d s h a st h ef o l l o w i n gc h a r a c t e r i s t i c s ：f i r s t t h e o u t l o o pa n di s l a n d s a r et r e a t e da s i n d e p e n d e n to b j e c t s ，r e a l i z i n gt h eo b j e c t i v eo fd e a l i n gw i t hc l o s e d2 d c o m p o u n d c u r v e sw i t h i s l a n d s t h e r e f o r e t h e a p p l i c a b i l i t y o fo f f s e t t i n gm e t h o di s i m p r o v e d ；s e c o n d ，ag r i d d i n ga p p r o a c hi sp r o p o s e da n di sa p p l i e di nt h ed e t e c t i o no f g l o b a li n t e r f e r i n gr a n g e s , t h eo f f s e t t i n go fg l o b a li n t e r f e r i n gr a n g e sa n dt h ed i s p e r s i o n o f a r c si nt h er a wo f f s e tc l l t v ea r ea v o i d e d ，r e d u c i n gt h ea m o u n to f c a l c u l a t i o n , t h u st h e e f f i c i e n c yo f o f f s e t t i n gm e t h o di si m p r o v e d a tl a s t , t h ep r o p o s e do f f s e t t i n ga p p r o a c hf o rc l o s e d2 d c o m p o u n dc u r v e sw i t h i s l a n d sh a sb e e nr e a l i z e dw i t hv i s u a lc + + 6 0a n dh a sb e e nt e s t e dw i t hv a r i o u s e x a m p l e s , t h er e s u l t ss h o wt h a tt h ep r o p o s e do f f s e t t i n ga p p r o a c hi se f f e c t i v ea n d r o b u s t k e y w o r d s ：2 d c o m p o u n dc u r v e ，o f f s e t t i n g ，p o l y g o n a lc h a i n , p a i r - w i s eo f f s e t t i n g m e t h o d ，g r i d d i n ga p p r o a c h i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ： j 磷，月刀日 f 学位论文使用授权说明： 河海大学、中国科学技术信息研究所( 含万方数据库) 、国家图 书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位 论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存 论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内 的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布 ( 包括刊登) 授权河海大学研究生院办理。 论文作者c 签名，：莹坠堡础；月，7 日 i v 河海太学硕士研究生论文第一章绪论 1 1 课题背景 1 1 1 等距方法的技术背景 第一章绪论 等距操作( 运算) 是实体造型中一个重要的造型技术，同时能有效支持抽壳 ( s h e l l i n g ) 、倒角和圆过渡等操作。等距( o f f s e o 技术在各种各样领域有着广泛的应 用，如机械加工中刀具路径规划、3 维数控加工、公差分析、路径障碍物碰撞检 测、v l s i ( 超大规模集成电路) 中布线间隙和重叠检查、蚀刻和铸造工艺中生成近 似体等。正因为其基础性和应用的广泛性，等距技术得到了研究人员和工业界的 广泛关注和熏视。其中二维组合曲线的等距是c a d c a m 领域中的一个重要课 题，并在型腔环切加工刀具轨迹生成技术中得到广泛研引1 心【3 】【4 】。 有关等距方法的研究已有3 0 0 多年的历史，人们对其进行了大量的研究i ”喁j 。 这些研究主要可以分为两类：几何等距( o f f s e tg e o m e t r y ) 和拓扑等距( o f f s e t t o p o l o g y ) t g 。几何等距研究的是等距曲线曲面的精确和逼近生成方法，它针对单 一曲线曲面；而拓扑等距是在几何造型系统中生成等距体的拓扑操作方法，它 以等距曲线曲面技术为基础，研究组合曲线曲面的等距方法。目前已有的研究 成果主要集中在几何等距研究上，对拓扑等距研究尚很初步。 等距曲线曲面的一个重要应用领域是刀具加工路径的自动生成，鉴于现有 的等距技术尚不足以有效支持刀具定位面的确定，许多学者研究了结合3 轴n c 加工特点的曲面等距方法。这些方法主要可分为基于点和基于线两类。基于点的 方法通常利用z m a p 方法生成离散点集获得刀具定位面【加】，为提高计算速度， i n u i “蝽螺j3 d 绘制硬件中多面体隐藏面消除算法快速生成刀具定位面，但其精 度取决于硬件网格分辨率，不能按需要控制。j l l n 1 2 提出一个基于线的3 轴n c 加工刀具轨迹生成方法，把各个等距面问的求交问题转化为驱动平面上交线问的 求交。由于现有的拓扑等距方法很难处理全局自交问题，还很难支持5 轴加工的 刀具定位面确定。 平面上组合曲线的等距操作是人们早就关注的问题，也是本文的研究重点。 由于曲线可以通过一系列直线段加以逼近，故大部分研究集中于多边形的等距方 法。 1 1 2 二维组合曲线等距方法的研究现状及研究意义 等距包括二维、三维空n _ i ：n 等距，二维空间上有平面( 封闭) 曲线的等距， 三维空间上有三维自由曲线、曲面及几何实体的等距。 二维组台曲线的等距方法研究 等距( o 融t ) 曲线曲面也被称为平行线，面，定义为到原曲线曲面距离为一 常数的点的集合。等距体是对一个实体的等距离扩展或缩小，对实体s 等距扩展 距离r 后，其扩展部分中的点到s 边界的距离小于等于r ；反之，对实体s 等距 缩小距离r 后，s 中到其边界的距离小于等于r 的部分被减去。等距体可以通过 原实体组成面的等距面来实现。因此，实体模型的等距技术要研究出多个曲面( 线) 组成的等距睦面( 线) 的生成方法。 平面上组合曲线的等距操作是本文的研究重点。现有的多边形等距方法可以 分为三类：边等距法( p a i r - w i s eo f f s e t ) 1 2 、v o r o n o i 图法【3 】和基于像素法( p i x e l b a s e d ) 。因计算稳定性或效率问题，后两类方法较少为人们所关注。 边等距法的一般过程分成如下三步：首先对多边形的每条边沿等距方向作等 距，然后用圆弧段连接断开的等距边生成初步等距线；其次检查初步等距线的自 交点；最后删除无效环( i n v a l i dl o o p ) 。该方法直观简单，但自交点的判别和无效 环的删除计算量大且数值计算稳定性差。v o r o n o i 图法的效率和强壮性比边等距 法好但同样存在计算稳定性问题。基于像素法主要优点是强壮性好，可是为达到 一定的精度需要占用大量的内存且计算量很大。 c a d c a m 领域中的一大部分多边形通过自由曲线( 通常是平面与曲面的交 线) 离散产生，它可能包含成千上万条直线段。当多边形中部分连续线段构成近 似圆( 圆半径等于等距值) 时，这些线段的等距线的交点集中在近似圆的圆心，此 时不仅要有效处理大量求交问题，还会产生大量等距线交点近似相同从而导致边 等距法数值计算的不稳定，这样的不稳定性称为近似圆奇异性( n e a r - c i r c u l a r s i n g u l 撕t y ) 【3 j 。s u g i h a r a 3 】指出v o r o n o i 图法同样存在近似圆奇异性问题。 边等距法的关键问题在于如何确定各等距段中的非干涉部分，许多学者提出 了一些有效的算法，如s u b 3 等根据等距环走向来判定各环是否存在干涉，h a n s e n 和a r b a b t i 】提出了干涉标志量i i ( i n t e r f e r e n c ei n d e x ) 来简化等距线中干涉段的判 断。然而这些方法仍然存在着求交量大和不稳定问题。不久前，c h o i 和p a r k 扣 提出了一个新的边等距法。他们把无效环分为局部无效环( 1 0 c a li n v a l i dl o o p ，边界 点为一个自交点的无效环) 和全局无效环( g l o b a li n v a l i dl o o p ，边界点为一对自交 点的无效环) 两种，首先通过一个边干涉检查程序( p a i r - w i s ei n t e r f e r e n c e d e t e c t i o n ( ) ) 在初步等距线构造以前就把所有局部无效环删除掉；然后用p a r k - s h i n 扫描线法 f 6 1 在初步等距线中找出自交点从而确定是否存在全局无效环；再进一步调用 p a i r - w i s e i n t e r f e r e n c e d e t e c t i o n ( ) 删除全局无效环。c h o i 和p a r k 【5 1 提出的边等距法， 从多边形顶点出发在初步等距线构造以前就把所有局部无效环删除掉；再用一个 扩展了的扫描线法( p a r k s h i n 扫描线法 6 】) 确定是否存在全局无效环。该方法的 特点是避免了多边形中局部干涉部分的等距操作，从而减少了计算量。但对全局 干涉部分仍需通过等距操作后再剔除。 p a i r - w i s e i n t e r f e r e n c e d e t e c t i o n ( ) 基于凸点必是干涉点( 定义见后) 这一基本事 河海大学硕士研究生论文第一章绪论 实，其基本思想是：首先任选一凸点为种子点，比较分别以种予点为起点和终点 的两条边的干涉关系( 定义见后) ，若此两边不是部分干涉，则根据其干涉关系沿 向前和向后两个方向用下一条边代替相应边进一步比较边对的干涉关系，直到两 比较边为部分干涉为止。 c h o i & p a r k 边等距法中扫描线法仍需离散圆弧边。没有避免全局干涉部分的 等距操作。我们针对这些主要问题进行深入研究，目的是寻找避免圆弧边离散及 全局干涉部分等距操作的方法，并进一步研究能够处理带孤岛的封闭二维组合曲 线的等距方法。 另外，曲面上的曲线等距方法也被广泛关注。不同于平面上曲线的等距，曲 面上曲线等距操作的距离是基于测地线计算的，一个有效的方法是先计算曲线上 采样点的等距点再进行插值求得逼近等距线f 1 3 】。h o l l a a 掣1 刖提出了一个在三角 面片表示的曲面上曲线o f f s e t 方法，曲面上的曲线由折线段组成，根据每个折线 段端点等距方向逐步生成中间等距线，使得每条中间o f f s e t 线不跨越三角面片( 最 多到达边界点) ，最后得到满足给定距离的等距线。该方法能自动删除了局部自 交环，但全局自交环删除方法效率不高。最近，t a m 等【”】提出了一个曲面上曲 线等距新方法，首先从原曲线出发生成初步等距线，根据原曲线和等距曲线的对 应关系以及局部无效环的几何特性，通过相邻等距曲线逐步搜寻自交点并剔除局 部无效环生成局部等距曲线：然后确定局部等距曲线的自交点并根据全局无效环 特性确定并剔除全部无效环生成真正的等距曲线。该方法适用于参数表示的曲线 曲面，能处理封闭曲线和开曲线。但初步等距线生成以及无效环的确定计算量太 大。 二维组合曲线的等距方法的个重要应用领域是刀具加工路径的自动生成。 研究良好的等距方法的研究意义在于，它可以为这一领域提供强大的技术支持， 使刀具加工技术能力更强，精度和效率更高。 1 2 本文的主要工作 从前面的分析中可以看到，二维组合曲线的等距方法是计算机辅助设计、计 算机图形学及相关研究领域的基本闲题。在国家自然科学基金项耳“非规则镱4 造 特征的自动识别方法研究”( 项目编号：6 0 3 7 4 0 5 3 ) 资助下，本文对二维组合曲 线的等距方法进行了研究。 在封闭二维组合曲线等距方法中，提高方法的效率和健壮性的关键在于减少 或避免大量的求交运算和等距操作、对复杂封闭曲线的处理、以及避免圆弧边的 离散化等问题。 c a d c a m 领域中的一大部分多边形通过自由曲线( 通常是平面与曲面的交 线) 离散产生，用以近似自由曲线，它可能包含成千上万条直线段。本文提出的 维组台曲线的等距方法研究 方法所处理的是二维组合曲线经离散后的多边形。 c h o i 和p a r k l 5 提出的边等距法，采用一个边干涉检测程序 ( p a i r - w i s e i n t e r f e r e n c e d e t e c t i o n ( ) ) ，在初步等距线构造以前就把所有局部无效环 删除掉：再采用p a r k - s h i n 扫描线法【6 l 确定是否存在全局无效环。该方法的特点 是避免了多边形中局部干涉部分的等距操作，但对全局干涉部分仍需通过等距操 作后再剔除。另外，c h o i & p a r k 边等距法不能处理带有孤岛的封闭二维组合曲线， 并且p a r k s h i n 扫描线法需要离散圆弧边，增加了相当的求交计算量，方法效率 有待提高。 通过分析全局无效环存在的几何特性，我们提出了一个区域网格技术，用于 全局干涉区间的确定当中，它避免了多边形中所有干涉区域的等距操作：并基于 区域网格技术进一步提出了带有孤岛的封闭二维组合曲线等距方法，它可以处理 带有任意数目孤岛的封闭二维组合曲线。其采用网格法来检测全局干涉区间，避 免了对初步等距线中圆弧边的离散化，并避免了对全局干涉区域的等距操作，减 少了一定计算量。本文最后对两种方法进行了实验对比，结果证明本文提出的方 法较c h o i & p a r k 边等距法具有更高的效率和健壮性。 本文首先介绍了c h o i & p a r k 边等距法，并对其进行了实现，针对典型的示例 图形，对方法进行了说明和分析：然后，介绍了改进的带有孤岛的封闭二维组合 曲线等距方法及其实现，同样地针对典型示例图形，对方法进行了说明和分析。 最后，以实际工程应用中的轿车车门型腔加工模型图为实验输入图形，对 c h o i & p a r k 边等距法和本文带有孤岛的封闭二维组合曲线的等距方法进行了实 验，给出实验数据及结果，对实验结果进行了对比分析，并给出了结论。 具体章节安排如下： 第一章，概述本文的研究背景、研究意义和研究内容。 第二章，介绍本文所采用的基本概念、性质、定义及定理：对重要的二维 求交算法进行具体说明。 第三章，介绍多边形求交相关算法及本文多边形链求交改进算法；详细介 绍c h o i & p a r k 边等距法及其实现，并结合示例图形对方法流程进 行阐述和分析。 第四章，介绍用于凹点干涉性检测的外切正方形法及网格法；详细介绍本 文带有孤岛的封闭二维组合曲线等距方法及其具体实现，并结合 示例图形对方法流程进行说明分析。 第五章，以实际工程应用中的轿车车门型腔环切加工模型图为实验输入图 形，对c h o i & p a r k 边等距法和本文带有孤岛的封闭二维组合曲线 的等距方法进行了实验，对实验结果进行分析，并得出结论。 第六章，对全文进行总结，对未来工作进行展望。 河海大学硕士研究生论文 第二章基本概念、定义、定理及相关几何算法 第二章基本概念、定义、定理及相关几何算法 本章介绍一些本文中用到的基本概念、术语、定义、定理，并介绍计算几何 中的一些算法，这些算法构成本文等距方法的基础。 2 1 基本概念及相关性质 概念1 封闭曲线及其边的方向封闭曲线的方向根据其顶点的排列顺序分为顺 时针( 负向) 和逆时针( 正向) 两个方向。若沿着封闭曲线方向行进，封闭曲 线所围成的区域总在边的左侧，则此封闭曲线为正向。封闭二维组合曲 线的组成边有直线边和圆弧边，其方向定义为与封闭曲线方向一致。记 封闭曲线的方向为f 。( 1 表示正向，1 表示负向) 。不失一般性，我们假设 封闭曲线中不存在相邻的共线直线边。 概念2 封闭曲线顶点的凹凸性本章讨论的封闭曲线不含自交点。封闭曲线顶 点v i 处的角度约定为内角。以图2 1 为例，过顶点v i 作其前后两相邻边+ 的端点切向如和z b 。顶点v i 处的角度定义为前端点切向的负向量一噩l 绕v i 沿封闲曲线内侧旋转到后端点切向所转过的角度值0 。顶点v i 的凸凹性依据e 值定义如下： 若。度e 1 8 0 度，则该顶点为凸； 若1 8 0 度 0 s i g n ( a b ) = s i g n ( d e t “鼢) = j od e tl 4 嚣) = 0 【1d e t “b ) 0 概念4 封闭二维组合曲线仅由直线边及圆弧边构成的封闭二维曲线，是本文的 研究对象。需要说明的是，本文中所有的封闭二维组合曲线是经圆弧边 = 生望鱼塑些塑竺墅互垫竺壅 离散后的多边形，即本文实际处理的是仅含直线边的多边形。 性质1 简单多边形顶点凸凹性与方向的关系“盯n 7 设多边形p 的方向为f 。( + 1 表 示正向，- l 表示负向) ，霸，和死为顶点v i o 前后两相邻边在v i ，o 处的端 点切向。若v i ，o 为凸点，则有s i g n ( t , 1 ) = f p ，表示露，与f p 符号相同； 若v i 0 为凹点，则有s i g n ( 嚣，蚴= - f p ，表示霸，正2 与f p 符号相反。因此只 要找出简单多边形的任一凸点即可判别其方向：设v io 为凸点，若 s i g n ( 霸，霸沪1 ，则此多边形的方向为正向；若s i g n ( l t l ：) = 一1 ，则此多边 形的方向为负向。 性质2 封闭曲线方向及顶点凸凹性的判定封闭曲线中，一顶点的两端点切向、 端点的凸凹性和封闭曲线方向三者间存在内在关联性。若一顶点前后两 相邻边在该顶点上的两个端点切向不平行，则它们叉乘后得到的向量垂 直于封闭曲线的所在面。如图2 1 ，v i 0 为封闭曲线的一个顶点，其前后 两相邻边的端点切向为乃j 和。则7 ) j 和的顺逆性判别式d e t ( t u z b ) 、 v i o 的凸凹性和封闭曲线方向f p 存在表2 1 所示的关系。 表2 1 顺逆性判别式、封闭曲线方向积顶点凸凹性关系 根据表2 1 ，若已知一封闭曲线的顶点v ，o 为凸点，通过d e t ( t h 如) 的符号即 可确定封闭曲线的方向：反之，己知一封闭曲线的方向，通过d e t ( t u 蚴的符号 即可确定顶点v i 0 的凸凹性。 对于不存在相邻共线直线边的多边形，利用表2 1 即可判定封闭曲线各个顶 点的凸凹性。由此，本文封闭曲线顶点凸凹性判定方法的基本思想是： 1 寻找一个最值顶点( 该顶点坐标的x 值和y 值在所有顶点坐标中均为最值， 即x 和y 均为最大值或均为最小值，或者x 最大、y 最小，或者x 最小、 y 最大) ，此点必为凸点，根据其叉乘确定封闭曲线方向： 2 根据已经确定的封闭曲线方向，再依次计算各顶点相邻两边的叉积，对照 表2 1 即可确定各顶点的凹凸性。 2 2 定义和定理 本文包含许多定义和定理，其中一部分引用了c h o i & p a r k 边等距法【5 l 咩一的相 应部分，一部分为自行定义。注意本文所指的封闭二维组合曲线实际上为多边形 ( 仅包含直线边) 。顶点表示多边形中的一个点，边表示连接两个相邻顶点的直 线段。 定义1 ( 凹点和凸点) 此为本文自行定义。设p 为多边形的一个顶点，记以p 为 河海大学硕士研究生论文 第二= 二章基本概念、定义、定理及相关几何算法 起始点的边为e n 。，以p 为终点的边为e 。n d d 以p 为旋转点让边e ，t a r t 逆 时针旋转到与边b 。d 重合，记其旋转角度为旺。若a 大于兀，则称点p 为 多边形的溜点；若a 小于等于冗，刚称点p 为凸点。 图2 2 中实心点表示的点为凸点，空心点表示的点为凹点。 当多边形等距时，凹点等距为一圆弧段，它把凹点的两相邻边的等距边连接 起来。为此我们把多边形的边分成直线边( 1 i n e a rs e g m e n t ) 和反射边( r e f l e xs e g m e n t ) 两种。 定义2 ( 直线边和反射边【5 1 ) 多边形中由两个顶点连接而成的直线段称为直线边， 多边形中的凹点称为反射边。为叙述方便计，凹点p 对应的反射边也记 为p 。 下面把多边形的直线边和反射边统称为多边形的边。 本文中多边形的边以参数化形式表示。每条边的参数取值范围为l ，任取多 边形中一边为首边，其参数区间为【0 ，l 】，沿多边形的走向，下一条边的参数区间 为【1 ，2 】，第i 条边的参数区间为【i 1 ，i 】。记p ( t ) 为第i 条边在t 【i - l ，i 】处的点，则 p ( i 1 ) 、p ( i ) 分别对应于第i 条边的起点和终点。若第i 条边为反射边，则对任意 一个t e i 1 ，i p ( t ) 都对应于此凹点。以图2 2 为例，边p o p l 为首边，p o 点的参数 值为0 ，p l 点的参数值为1 ，对反射边p 2 有p ( 2 ) = p ( 3 ) ，即其起点p ( 2 ) 及终点p ( 3 ) 均对应凹点p 2 。图2 2 中需要注意的是；p d 是首边p o p l 的起点又是末边p 9 p l o 的 终点，故p ( o ) = p ( 1 0 ) 。多边形中任意点p ( t ) 的单位法向n ( t ) 定义为等距方向， 如n l 为边p l p 2 上任一点的单位法向。反射边韵单位法向从上一条边的单位法向 变化至下一条边的单位法向，如图2 2 中的反射边p 2 的单位法向n ( t ) ( t 【2 ，3 】) 从 n l ( 产2 ) 暇时针连续变化到n 2 0 = 3 ) 。 图2 2 多边形的参数化 定义3 ( 相切圆【5 】) 与一条边相切的圆称为边的相切圆。与两条边都相切的圆为公 切圆。设相切圆的半径为r = p ，与边的相切点为p ( t ) ，则相切圆的圆心 c ( t ) = p ( t ) + r n ( t ) 。其中n ( t ) 为边在p ( t ) 点的单位法向。可见直线边上所有 点的相切圆圆心的集合即为此直线边沿法向n ( t ) 等距量为r 的等距边， 反射边p ( t ) 上所有点的相切圆圆心的集合为以p o ) 为圆心，半径为r 的 二维组合曲线的等距方法研究 圆弧。 嘲2 3 初步等e e 线中的有效环和无效环 定义4 ( 无效环) 此为本文自行定义。边等距法首先对多边形的每条边沿等距方 向作等距，然后用圆弧段连接断开的等距边生成初步等距线；初步等距 线中边与边的交点称为多边形的等距自交点。可见自交点是以等距量为 半径的公切圆的圆- t l , 。自交点把初步等距线分割为两类环，类环包含 在等距多边形中，这样的环为有效环。其余环称为无效环，无效环在多 边形等距时必须删除，因为它们不包含在等距多边形中。在图2 - 3 中， 黑粗线表示原始多边形，红、蓝线为初步等距线，s i ( i = l ，9 ) 为自交点， l l ，l 7 为无效环( 红线表示) ，l 8 和b 为有效环( 蓝线表示) 。 等距把原始多边形上的点和初步等距线中的点建立了对应关系，自交 点对应于原始多边形上的两个点，而无效环对应于原始多边形上的一段 或多段连续线段。如图2 3 中，自交点s 1 对应原始多边形上的两个点t 1 和t 2 ，无效环l i 对应于连续线段h p i t 2 ，无效环l 3 对应于两条连续线段 h p 3 t 4 和t 5 t 5 。对应于原始多边形上一条连续线段( 此连续线段的两个端点 对应于一个自交点) 的无效环称为局部无效环，而对应于一对连续线段( 四 端点对应于两个自交点) 的无效环称为全局无效环。图2 3 中的局部无效 环有l l 、l 2 、l 4 、l 5 、l 7 ，全局无效环有l 3 和l 6 ，而l 8 和l 母为有效环。 事实上，图2 3 中的原始多边形的等距多边形就是由有效环l 8 和l 9 组成。 定义5 ( 干涉点和干涉区间) 此为本文自行定义。对多边形的边e 上的任意一点 p ( t ) ，若其相切圆与多边形上的其它边( 除边e 外) 相交，则称点p ( t ) 或参数 t 为干涉点。若多边形上的一个点p 位于p ( t ) 的相切圆内( 或在相切圆上) ， 称p f t ) 或参数t 被点p 干涉显然多边形中的任一凸点必为干涉点。 若参数区间i 中豹任意一点p ( t ) ( t i ) 皆为干涉点，则称i 为一干涉区 间。若参数域叭、l ，可以包含多个干涉区间) 中的任意一点p ( t ) ( t v ) 都为干 涉点，则称v 为一千涉区域。 记多边形的参数定义域d ，若参数r d 满足如下条件则称r 为干涉 端点：存在一个足够小的正数，使得参数区间( r ，- f ) 为干涉区间， 而( r ，r + ) 为非干涉区间；或者( - e 。，r ) 为非干涉区间，而( f ，r + 1 为干涉区间。不难看出，干涉端点是多边形中与自交点对应的点，所 河海犬学硕士研究生论文 第二章基本概念、定义、定理及相关几何算法 s 以总是成对出现的。如图2 3 中t 卜t 2 、t 3 、t 4 、t 5 和t 6 都为干涉端点。 若参数区间 8 b 】中的任意点p ( t ) ( t ( a ，b ) ) 皆为干涉点，而a 和b 为 干涉端点，则称( 咄】为一最大干涉区间。 根据无效环和干涉区间的定义可知局部无效环和全局无效环有如下 特点： ( i ) 局部无效环 ( 2 ) 全局无效环 公切皤 对应于一个最大干涉区间【a ，b 】；两个干涉端点a 和 b 对应于个自交点；对任意一点t e ( a ，b ) ，必存在 点t b ) l ；lt7 t ，使得t 被t7 干涉。 对应于两个干涉区间，其干涉端点对应于两个自交 点。 公切嚼 公切圆 直线边与直线边部分干涉 反射边与直线边部分干涉 反射边与反射边部分干涉 sj 的终点相切圊 s l 的终点相切圆 s l 的终点相切圆 直线边与直线边完全干涉 反射边与直线边完全干涉 反射边与反射边完全干涉 s，l s s l 相切脚 s 的相切圜s t 的相切圆 ，_ 直线边与直线边反向干涉反射边与直线边反向干涉 反射边与反射边反向千涉 图2 4 边与边的干涉关系 仍以图2 3 为例，局部无效环l l 对应于干涉区间 t 2 t d ，全局无效环 二维组台曲线的等踊方法研究 l 3 对应于干涉区间【t 3 问和【t 6 ，t 5 】，其中干涉端点t 3 和t 5 对应于自交点s 3 ， t 4 和t e 对应于自交点s 4 。 定义6 ( 干涉边和干涉关系( 5 1 ) 设s l 和s 2 为多边形中的两条有向边，若s l 的终点 相切圆与s 2 相交，则称s 1 被s 2 完全干涉；虽然s 1 的终点相切圆不与s 2 相交，但8 l 中有多个点的相切圆与s 2 相交，则称s 1 被s 2 部分干涉：若 s l 中不存在与s 2 相交的相切圆，但实际上s l 被多边形的其它部分干涉， 则称s l 技s 2 反向干涉。 s l 和s 2 为两条有向边，若s l 被s 2 部分干涉同时s 2 也被s l 部分干涉， 则称s i 和s 2 为部分干涉关系；若s l 和s 2 中其中一条不被另一条干涉。 但该边实际上被多边形的其它边干涉，称s l 和s 2 为反向干涉关系；若s i 和s 2 中其中一条被另一条完全干涉，而另一条边被部分或完全干涉，则 称s l 和s 2 为完全干涉关系。图2 4 例举了各种各样的边干涉关系。 定义7 ( 相互干涉边对) 此为本文自行定义。设s 1 和s 2 为多边形中两条边，其参 数域分别为i t i ；，t l 。】和【t 2 。，t 2 。】，若存在t 1 。【t l s , t l 。】，使得以p 为半径相切于 点p ( t l 。) 的相切圆包含s 2 中的点：同时。存在t 2 。 t 2 5 i t 2 e 】，使得以p 为半 径相切于点p 【t 2 。) 的相切圆包含s i 中的点，则称s 1 和s 2 为相互干涉边对。 需要注意的是相互干涉边对中的边不是有向边，其相切圆位于等距方向一 侧。 显而易见，与一凸点相连的丽条直线边必为相互干涉边对，称这样的 相互干涉边对为凸干涉边对。另外，其中至少一条边是反射边的相互干涉 边对称为凹干涉边对。如图2 3 中的相互干涉边对p i p 2 与p i p 6 为凸干涉 边对。反射边p 3 与直线边p 1 p 6 组成的相互干涉边对为凹干涉边对。对于 对有向边s 1 和s 2 ，若它们的干涉关系为部分或完全干涉，则称s l 和s 2 为有向干涉边对。 定义8 ( 单调榭蜘) 由直线段首尾相连组成的一段连 续啦线。称为一个链。给定一个方向，如果垂 直于这个方向的每一条直线和一个链有且仅 有一个交点，那么称此链为沿此方向的单调 1 弋p n ， 扫描拽方向 图2 5 单调链 链，其中给定的方向为扫描线方向，垂直于这个方向的直线为扫描线。图 2 5 中a , b ，c ，d 四条线段组成的一组连续曲线为一单调链，t 为其扫描线方 向。 定义9 ( 极值点) 此为本文自行定义。不失一般性，我们选取x 轴方向为扫描线 方向，一个链沿x 轴方向的局部极值点称为该链的极值点，其局部极小 值点称为左极值点，局部极大值点称为右极值点。 定义1 0 ( 顶点的凸凹性) 此为本文自行定义。若一个链的内点( 非端点) v i 位于其 相邻两顶点连线v i 1 v i + i 的左侧，则称为凸点，否则称其为凹点。 1 0 河海大学硕士研究生论文 第二章基本概念、定义、定理及相关几何算法 定义1 1 ( 凸( 凹) 链) 此为本文自行定义。一个链中由一系列相邻凸( 凹) 点、直 线段连接起来的子链称为凸( 凹) 链。 定义1 2 ( 顶点的非极值范围( 6 1 ) 一个顶点是否为极值点由扫描线方向决定顶点 的非极值范围定义为一角度范围，位于该范围内的扫描线方向使该顶点 成为非极值点。 定义1 3 ( 凸( 凹) 链的最少极值范卧6 1 ) 一个凸( 凹) 链的极值点个数由扫描线方 向决定，凸( 凹) 链的最少极值范围定义为一角度范围，位于该范围内的 扫描线方向使该凸( 凹) 链的极值点个数最少。 定义1 4 ( 严格单调链) 此为本文自行定义。沿x 轴( 扫描线方向) 和y 轴方向都单 调的链称为严格单调链。由于单调链总是沿x 轴单调递增，若一单调链 沿y 轴方向单调递增( 减) ，则称此链为严格递增( 减) 链。 定义1 5 ( 封闭曲线外环及孤岛) 此为本文自行定义。封闭曲线外环及封闭曲线的 最外层边界线，即最外层的封闭图形。孤岛及位于封闭曲线外环内部的 封闭图形。如图2 6 所示。个封闭曲线有且仅有一个外环，却可以有 多个孤岛。 定义1 6 ( 封闭曲线外环与孤岛的方向及等距方向) 此为本文自行定义。封闭曲线 外环与孤岛的方向始终相反，如图2 6 所示。若外环为顺时针，则孤岛 为逆时针，反之亦然。封闭曲线外环与孤岛的等距方向亦始终相反。若 外环为向内等距，则孤岛为向外等距，反之亦然。 图2 6 带孤岛的封闭曲线固形 定理1 局部无效环在原始多边形上的对应连续线段必有一凸点。多边形中任一 凸点都对应一局部无效环。 根据定理1 ，局部无效环可以从一凸点出发确定其干涉区间得到。以图2 7 为例，从凸点p i 出发找出凸干涉边对p i r i p 1 与p i p h ，沿图示方向找出的红线所示 的连续线段( 干涉点集合) 对应一局部无效环。 定理2 全局无效环在原始多边上的对应连续线段必有一凹点。 根据定理2 ，全局无效环可以从一凹点出发确定其干涉区域得到。以图2 8 为侧，首先判别凹点是否为干涉点，若为干涉点就找出包含反射边c e 的凹干涉 边对c e 与o e ，沿图示方向找出红线所示的连续线段( 干涉点集合) 对应一全局无 一二维组合曲线的等距方法研究 效环。要注意的是凹点并不一定为干涉点。 以上两个定理均为本文自行提出。 p ( t 。) ( 1 ( o ) ( 1 圉2 ，7 局部无效环鹩确定 篷2 8 全局无效环的确定 2 3 二维求交算法概述 二维求交问题是计算直线段、圆弧及一般曲线的交点。人们对直线段求交进 行了大量研究【1 8 】1 1 9 2 0 1 1 2 1 】f 2 2 】【2 3 】【2 4 1 ，并提出了很多有效方法：如三角化法【2 5 】、包围 盒法【2 “、扫描线法 2 7 】等。但任何一种方法都没有完全解决好求交问题中速度与 精度的有效统一，有的算法侧重于通用性与速度，有的却注重精度。求交问题可 以加以折衷处理，扫描线法就是一种常用的直线段求交方法。 多边形链属于般曲线的特殊情况，由直线段通过首尾相连组成的折线。扫 描线法也可以应用到多边形链求交中，但多边形链求交不同于直线段求交：一是 多边形链由顺序相连的直线段组成，求交点时可以利用多边形链的凸凹性、单调 性等信息以提高求交效率：二是多边形链中两相邻直线段的连接点