三维空间内凹多面体的Minkowski和的算法研究 精品.doc

三维空间内凹多面体的Minkowski和的算法研究第1章 绪论1.1 课题研究意义“计算几何”这个术语最初是由Minsky和Papert作为模式识别的代用词被提出来，到了A.R.Forrost才有了正式的定义：“对几何外形信息的计算机表示、分析和综合”。到了20世纪70年代末，Shamos(沙莫斯)和Hoey(霍伊)利用计算机有效地计算出平面点集的Voronoi图，并发表了一篇著名的，从此一门新的学科计算几何从算法设计与分析中孕育而生1。该领域中的问题所带来的挑战性，也使得一大批科研人员为之呕心沥血、辛勤耕耘，从而使这一崭新的研究领域在比较短的时间内取得了辉煌的成果，对许多问题已经有了一系列比较成熟的计算几何算法。Minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义。它广泛应用于机器人学、计算机图形学、固体建模、计算机动画和CAD/CAM等领域2。尤其在机器人学领域，Minkowski和算法起到了重要的作用，主要应用在机器人的运动规划中。机器人学(Robotics)是与机器人设计、制造和应用等相关的学科，主要研究机器人的控制与被处理物体之间的相互关系3。机器人学有着极其广泛的研究和应用领域，这些领域体现出广泛的学科交叉，涉及众多的课题，如机器人控制、智能、传感、机器人装配以及机器语言等，在工业、农业、空间和海洋以及国防等领域得到越来越普遍的应用。机器人学的最终目标之一，就是设计出一个独立自主的机器人，它能够接受高级任务并且在没有人的干涉下自主执行并完成任务4。路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定初始位姿到终止位姿的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有障碍物5。因此，能否对运动路径进行快速而准确地规划成为衡量机器人智能高低的一个重要标准。为了更好地解决机器人的路径规划问题，人们往往用多面体模型来模拟工作空间中的机器人与障碍物，其中多面体又可以分为凸多面体和凹多面体。这样，检测机器人与障碍物之间的碰撞情况就转换为检测多个几何体之间的碰撞情况6。根据工作环境，机器人的路径规划可以分为动态路径规划和静态路径规划。动态环境即时变环境，含有运动轨迹已知或未知的障碍物。对于轨迹已知的情况下的规划可以将其转化为若干静态问题解决；但对于运动轨迹未知的情况，机器人需要在运动中不断地检测与障碍物之间的碰撞情况。在静态环境下，机器人仅仅能够做平移或翻转运动，通常障碍物为静态的刚性物体，并且机器人与障碍物的几何形状和位置是已知的。在这种条件下，机器人可根据先验环境模型找出从起始点到目标点的可行或最优路径，并沿着这条路径顺利地完成任务。这个看似简单的问题在计算几何学中却成为具有挑战性的问题，并且成为机器人研究领域中的一个研究热点问题。Minkowski和是计算无碰撞路径的一个重要工具，可以定义为，在欧几里得空间中，假设P和Q为两个封闭的几何对象，那么P和Q的Minkowski和为几何对象M，其中p和q分别是P和Q上的点，p+q是p和q的位置矢量和7。也就是说若，则有。假设多面体P为工作空间中的任意一个障碍物，多面体R为沿平面做平移运动的机器人，则P所对应的R障碍物为，其中-R与R关于坐标原点对称。除此之外，Minkowski和还可以用来计算两个多面体之间的渗透深度、精确检测物体之间的碰撞情况以及应用到机器人装配仿真等等，有着很广泛的应用8。可见，研究两个几何对象的Minkowski和求和算法，对于解决机器人的路径规划问题有着十分重要的现实价值。1.2 Minkowski和算法的研究现状1983年，T.Lozano-perez首次利用Minkowski和来计算位姿空间障碍物(Configuration Space Obstacle)，并应用到机器人的运动规划中9。目前研究人员已经提出了计算三维空间内两个多面体的Minkowski和的多种不同方法，主要目标都是计算Minkowski和的边界值，并提供一些方法来表示它10。其中，计算凸多面体的Minkowski和的方法已经有了成熟的算法，而凹多面体的Minkowski和一直停留在获得近似值。1.2.1 国外研究现状1987年，L.J.Guibas和R.Seidel提出了计算简单多胞体Minkowski和多面体的敏感输出(Output-Sensitive)算法，该算法定义了二维平面上的一个操作，称作卷积(Convolution)11。1996年，J.Basch和L.Guibas等人扩展了上述算法，提出了以定义在多面体运动轨迹上的卷积计算为基础的方法来计算三维空间内多面体的Minkowski和12。1993年，P.K.Ghosh为计算凸多面体和凹多面体的Minkowski和提出了统一的算法，它以倾斜图(Slope Diagram)表示法为基础13。计算两个多面体的Minkowski和等同于分别计算两个多面体的倾斜图，然后合并它们的倾斜图，并从合并的倾斜图中提取Minkowski和的边界值14。通过使用立体投影(Stereographic Projection)方法，多面体的倾斜图转换为二维图形，这样就把问题降低到较低维数的空间中进行解决。1997年，B.Aronov和M.Shair等人提出了计算普通多边形或多面体的Minkowski和的基本框架：首先，对每个多边形(或多面体)进行凸剖分，得到若干个子凸多边形(或多面体)；然后，计算取自不同多边形(或多面体)的所有可能成对的子凸剖分的Minkowski和；最后，合并第二步中所有子Minkowski和多边形(多面体)15。基于上面的剖分框架，20XX年，P.K.Agarwal和E.Flato等人给出了计算凹多边形的Minkowski和算法，并提出了多种不同的剖分方法16。由于凹多面体的Minkowski和求和算法过于复杂，目前，人们主要研究能够得到满足某些标准的近似值的求和算法，如文献17,18。2000年，E.Flato和D.Halperin在文献19中给出了计算普通多边形的Minkowski和算法，该算法是基于CGAL(putational Geometry Algorithm Library)20实现的。20XX年，基于Ghosh在文献13中提出的倾斜图表示法，H.Bekker和J.B.T.M.Roerdink比较了三种计算凸多面体Minkowski和的方法，最终提出了在线性时间内计算三维空间凸多面体Minkowski和的新方法，但是该方法只对非常简单的凸多面体适用21。20XX年，E. Flato和F.Fogel等人给出了Minkowski和算法的应用领域，提供了为建造平面集合的精确、有效的Minkowski和所使用的软件包22。20XX年，Y.Y.Wu和J.J.Shah等人分别对基于凸包(Convex Hull)的凸多面体的Minkowski和求和算法与基于倾斜图的凸多面体的Minkowski和求和算法进行了优化23。遵循文献13提出的方法，20XX年，E.Fogel和D.Halperin提出了基于立方体高斯映射CGM(Cubical Gaussian Map)计算三维空间内凸多面体的精确Minkowski和算法24，该算法也是基于CGAL实现的。1.2.2 国内研究现状国内对Minkowski和算法的研究起步较晚。其中，对凸多面体的Minkowski和算法的研究取得了一些很好的成果；对凹多面体的剖分和子Minkowski和多面体的合并的研究也有了一定的进展。20XX年，郭希娟和高艳丽提出了基于正四面体中心投影RTCP(Regular Tetrahedron Central Projection)和三角形内简单平面凸划分的叠置算法计算凸多面体精确Minkowski和的优化算法25。基于正四面体中心投影算法，20XX年，郭希娟和谢蕾又给出了进一步优化基于正四面体高斯映射RTGM(Regular Tetrahedron Gaussian Map)的算法26。通过对国内外研究现状的分析，可以得出计算多边形或者多面体的Minkowski和算法主要有六种，即基于凸包的求和算法、基于凸剖分的求和算法、基于倾斜图的求和算法、基于立方体高斯映射的求和算法、基于正四面体中心投影的求和算法以及基于正四面体高斯映射的算法。其中，基于凸包的Minkowski和求和算法是非常著名的算法之一，该算法直接源于Minkowski和的定义，它可以表示为：，其中，CH表示凸包操作，、分别表示多面体P和Q中顶点的集合15。在计算Minkowski和多面体的过程中，该算法需要区分内部点、外部点和边界点，创建这些点集的凸包不但需要很高的计算费用，并且该算法的计算结果不是图而是一个点集。基于倾斜图的Minkowski和求和算法，根据高斯映射的规则，把多面体的体元(包括多面体的顶点、棱、面)映射到单位球表面，并采用立体投影方法把每个多面体的倾斜图转化为平面图形，然后计算平面图形的叠置，从叠置的结果中抽取Minkowski和的边界值。采用立体投影方法不仅会使算法在处理退化情况时存在着很大的局限性，而且会增加算法的实现难度，很难得到精确的计算结果。基于立方体高斯映射的Minkowski和求和算法，通过自定义的立方体高斯映射，把三维空间内的凸多面体的体元映射到立方体表面，从而得到六个平面划分面，计算两个凸多面体的Minkowski和就等同于计算六对平面划分的叠置。通过计算六对平面划分中各面的附加信息，得到Minkowski和多面体的立方体高斯映射表示，最后求逆映射得到精确的Minkowski和多面体。基于正四面体中心投影的Minkowski和算法，首先按照高斯映射规则，将凸多面体映射到单位球面上，再取单位球面的外切正四面体，通过自定义的正四面体中心投影得到凸多面体在正四面体上的投影。求两个凸多面体的Minkowski和等同于求四对平面划分的叠置。通过计算四对平面划分中各面的附加信息，得到新多面体的正四面体中心投影，最后求逆映射得到Minkowski和多面体。基于正四面体高斯映射的Minkowski和算法，为计算两个给定位置和形态的凸多面体的Minkowski和表示，取凸多面体的外切正四面体，根据自定义的正四面体高斯映射把凸多面体映射到外切正四面体的四个表面上，求两个凸多面体的Minkowski和等同于求四对平面划分的叠置，通过计算平面划分中各面的附加信息，得到新多面体的正四面体高斯映射，最后求逆映射得到Minkowski和多面体。基于凸剖分的Minkowski和算法，是计算凹多边形或凹多面体的Minkowski和的常用算法。对于二维空间内的凹多边形而言，常用的方法就是把凹多边形剖分为若干个凸多边形，通过计算凸多边形Minkowski子和的并来得到凹多边形的Minkowski和。理论上，剖分策略的选择与求和速度无关，但实际上，它严重影响着整个求和算法的运行时间，特别是计算三维空间内的凹多面体的Minkowski和。因此，迫切需要寻找某种策略来降低计算凹多面体的Minkowski和的求和算法的时间复杂度，同时由于基于剖分法中的合并算法的复杂度很高，目前仍然没有人提出计算凹多面体的精确Minkowski和的算法。因此研究凹多面体的精确Minkowski和求和算法是一项具有挑战性及重要意义的课题。1.3 Minkowski和算法的应用Minkowski和算法在许多领域中有着广泛的应用，如机器人学、碰撞检测、模拟仿真、计算机图形学等等，下面重点介绍该算法在机器人路径规划和碰撞检测中的应用。1.3.1 机器人路径规划机器人学的最终目标之一，就是设计出独立自主的机器人。在指挥这种机器人时，只需要告诉它去做什么，而不必告诉它如何去做，其中尤为重要的一个方面就是，机器人应该懂得如何对自己的运动进行规划27。路径规划是机器人学算法中的一个重要问题，其本质是在众多障碍物之间为机器人寻找一条最优或近似最优的无碰撞路径，该问题经常用位姿空间方法来描述。所谓的位姿空间，也称C空间，是机器人的参数空间；机器人的工作空间是机器人在其中实际运动的那个空间，也就是真实的世界。自由C空间(Free Configuration Space)是机器人避免与障碍物发生碰撞的所有位置点的集合27。为了规划路径，需要拥有一个能够捕捉自由位姿空间连通性的表示，而Minkowski和算法可以来计算所需的表示，并且能够获得一条精确的无碰撞路径。假设多面体P为工作空间中的障碍物，多面体R为移动机器人，那么通过计算位姿空间障碍物来确定一条无碰撞的路径，这个问题就转变为计算多面体P与-R的Minkowski和，其中-R与R关于坐标原点对称。1.3.2 碰撞检测碰撞检测是检测两个物体在空间中是否重叠或它们的边界线是否至少共享一个点17。在虚拟环境中，由于用户的交互，物体之间经常发生碰撞，为保持虚拟环境的真实感和用户的沉浸感，快速精确的碰撞检测是必不可少的。传统的碰撞检测方法主要有空间分解法和层次包围盒技术，这两种算法都只能近似的检测物体是否发生碰撞，Minkowski和算法能够精确地检测出物体之间是否发生碰撞。该问题用渗透深度来描述，两个多面体P和Q的渗透深度是指使得两个多面体不相交，其中一个多面体必须移动的最小距离17。通过计算原心到Minkowski和()表面上的最小距离来得到。若渗透深度大于等于零，说明两个多面体发生碰撞，反之，两个多面体不会发生碰撞。1.4 本文研究内容本文在对国内外研究现状全面分析的基础上，完成对三维空间内凹多面体Minkowski和求和算法的进一步研究，主要包括下述内容。(1)计算简单凸多面体的Minkowski和的求和算法 通过深入研究正四面体中心投影算法和正四面体高斯映射算法，发现这两种算法都需要计算四次划分平面叠置，并且都没有给出具体的映射函数关系式。因此，本文提出了正四面体映射和点投影的概念，把三维空间的问题转换到二维空间进行解决，且只需要计算一对平面划分的叠置，更高效的计算凸多面体的精确Minkowski和。(2)简单凹多面体的剖分算法 通过深入研究国内外凹多面体的剖分算法，发现大多数的剖分算法会生成大量新点，产生很多凸多面体。因此，本文采用图论和集合论的思想，提出了基于成功回路的凹多面体的剖分算法，该算法不仅不产生新的顶点，而且能够处理有空洞的多面体。(3)计算简单凹多面体的Minkowski和求和算法 首先，根据(2)中提出的剖分算法对凹多面体进行剖分，得到若干子凸多面体；其次，利用(1)中提出的求和算法计算所有可能成对的子凸多面体的Minkowski和；最后，在合并子凸Minkowski和多面体时，利用已改进的Enhanced Marching Cubes算法获得凹多面体的近似的Minkowski和多面体边界。1.5 本文组织结构分为5章，其余部分组织如下。第2章介绍与本课题相关的基础理论。首先，是对基本几何定义的介绍；然后，阐述了Minkowski和的定义、性质及相关的几何操作；最后，介绍有关算法的基本知识，该部分为课题的研究打下了坚实的理论基础。第3章提出了一种新的计算凸多面体的Minkowski和的求和算法。首先，介绍现有的求和算法，分析它的主要思想；然后，以提高算法的执行效率为目标，提出正四面体映射和点投影的概念，给出正四面体映射和点投影的映射规则，并由此提出基于该映射的凸多面体的精确Minkowski和求和算法。最后，对算法的时间复杂度进行了分析。第4章提出了一种新的凹多面体的剖分算法，并给出了计算凹多面体的Minkowski和求和算法思想。以提高算法的精确度和效率为目标，首先，本章采用图论和集合论的思想，提出了基于成功回路的凹多面体的剖分算法；其次，在合并子凸多面体Minkowski和时，利用现有已改进的Enhanced Marching Cubes算法，最终获得近似的多面体Minkowski和边界；最后，给出计算简单凹多面体Minkowski和的算法的总体思想。第5章是实验与分析，对所研究的内容及算法进行了实验验证并给出实验结果。最后，对本课题进行了全面总结，同时针对课题中存在的问题提出了进一步改进的思路，并规划了未来的研究方向。第2章 理论基础下面给出一些本章中将要用到的几何概念、定义和基础知识。2.1 相关的几何定义本文考虑的对象是欧几里得三维空间中的点集，假设有一个参考坐标系，使得每个点表示为相应维数的笛卡尔坐标的向量。除了点之外，还将考虑包含两个给定点的直线、直线上两定点确定的直线段、三个给定点确定的平面等。下面给出本文所涉及到的基本几何对象的定义。2.1.1 欧几里得空间若用(或)表示维欧几里得空间，那么具有度量的实数的元组空间，称为欧几里得空间28。2.1.2 点中的点定义为一个元组。点也可以解释为有个分量的向量，此向量的起点为坐标原点，终点为点28。点是整个几何学的基础，它只有位置，没有大小。2.1.3 直线与线段在中给定两个不同的点和，线性组合(是实数，即)是中的一条直线28。给定中两个不同的点和，若在线性组合中加入条件，则得到点和的凸组合，即(，)，此凸组合描述了连接两点和的直线段，并记为(无序对)28。线段是直线的一部分，并以两个端点为界限。2.1.4 多面体由若干平面多边形围成的封闭连通的空间区域称为多面体(允许有洞)29。一般说来，多面体是指边界和内部域的并。多边形的顶点和边是多面体的顶点和边，多边形是多面体的小面。2.1.5 平面图及平面划分假设图G=(V，E)，其中V为顶点集，E为边集，如果图G能够没有交叉地嵌入平面，那么称图G为平面图。平面图的直线平面嵌入确定平面的一个划分，称为平面划分(也称平面剖分)28。设平面图的顶点数、边数和区域数分别为v，e和f，则由欧拉公式有v-e+f=2。2.1.6 凸集与凸包假设S是二维平面上的非空点集，p1和p2是S中任意两点，若存在一点p=tp1+(1-t)p2，其中，则称S是凸集30。这就是说，如果S中任意两点所连线段全部位于S之中，那么S是凸的。此定义可以推广到高维。平面中n个点的有限集合S的凸包CH(S)是一个凸多边形30。在中，S的CH(S)是包含S的最小凸域的边界，其顶点为S中的点，并且S中所有的点均包含在CH(S)内。2.2 基础知识及内容下面将给出Minkowski和的定义、性质及相关的几何操作。2.2.1 Minkowski和的定义Minkowski和的定义是由德国数学家Hermann Minkowski最早提出的。在欧几里得空间内，假设P和Q为两个封闭的几何对象，它们的Minkowski和可以表示为：在不改变两个操作数相对方位的情况下，一个操作数Q沿着另一个操作数P的外轮廓滑行，Q的参考点经过的轨迹就是P和Q的Minkowski和。如图2-1所示。图2-1 P和Q的Minkowski和Fig. 2-1 The Minkowski Sum of P and Q另外，P和Q的Minkowski和也可以表示为几何对象M，其中p和q分别为属于几何对象P和Q的点，为位置矢量与的矢量和。例如，在欧几里得二维平面内，假设并且，那么有。下面给出二维平面内两个三角形的Minkowski和，如图2-2所示。PQQP图2-2 三角形P和Q的Minkowski和Fig. 2-2 Minkowski Sum of triangle P and Q2.2.2 Minkowski和的性质从上面的定义可知，计算两个几何对象S1与S2的Minkowski和具有下列性质31,32。(1)与实数运算相似，求两个几何对象的Minkowski和满足交换规则和分配规则，即式子S1S2=S2S1与S1(S2S3)=(S1S2)(S1S3)成立。(2)设几何对象S1与S2为两个凸多边形，分别含有n和m条边，则Minkowski和是由不超过n+m条边构成的凸多边形。(3)设S1与S2为两个多边形，分别含有n和m个顶点，S1与S2的Minkowski和的时间复杂度上界分为下列几种情况。若S1与S2均为凸多边形，则计算的时间复杂度上界为O(n+m)。若S1与S2中一个为凸多边形，另外一个为非凸多边形，则计算的时间复杂度上界为O(nm)。若S1与S2均为非凸多边形，则计算的时间复杂度上界为O(n2m2)。(4)设S1与S2为两个多面体，分别含有n和m个顶点，S1与S2的Minkowski和所需要的时间分为下列几种情况。若S1与S2均为凸多面体，则计算所需要的时间为O(n2m2)。若S1与S2均为非凸多面体，则计算所需要的时间为O(n3m3)。2.2.3 平面划分的叠置求平面划分的叠置是将两个或者多个平面划分图层进行叠加，并产生一个新平面划分图层的操作，其结果是将原来平面划分中的图元分割成新图元，新图元综合了原来两个图层或者多个图层的属性33。给定两个平面划分D1和D2，它们的叠置是一个新的平面划分，记作Overlay(D1,D2)。如果在Overlay(D1,D2)中存在一张面f，在D1和D2中分别存在面和，那么面f是的一个极大连通子集27。简单的说是由来自D1和D2的边共同在平面上导出一个子区域划分，如图2-3所示，黄色点为新的交点。图2-3 平面划分的叠置Fig. 2-3 Overlay of planar subdivisions一般的叠置问题，首先给出分别对应于D1和D2的两个双向链接边表，然后计算出对应于Overlay(D1,D2)的双向链接边表，同时要求对Overlay(D1,D2)中的每张平面划分面加上标注，以指明在D1和D2中它分别属于哪张平面划分面，这样能够直接访问存储在这些面记录中的附加信息。双向链接边表的定义将在2.3节中给出。2.2.4 边界表示法物体可以通过描述它的边界来表示，称为边界表示法34。边界就是物体内部点与外部点的分界面。定义了物体的边界，该物体也就被唯一的定义了。边界表示法的一个很重要的特点是描述了物体的信息，包括几何信息与拓扑信息两个方面。物体的几何信息是指顶点、边、面的位置、大小、形状等几何数据。拓扑信息是指物体上所有的顶点、棱边、面间的连接情况35。2.2.5 移动立方体算法移动立方体MC(Marching Cubes)算法是基于规则体数据抽取等值面的经典算法36。传统的MC算法的基本思想是逐个处理数据场中的立方体(体单元)，分类出与等值面相交的立方体，采用插值计算出等值面与立方体的交点。根据立方体每一顶点与等值面的相对位置，将等值面与立方体的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近。该算法对体数据中的体素逐个进行处理，每个被处理的体素，以三角面片表示其内部的等值面。2.3 算法与数据结构算法与数据结构专门研究从解决非数值计算的现实问题中抽象出来的数据在计算机中如何表示、快速存取和处理的方法。计算几何与计算机科学中的算法设计与分析、数据结构等学科的关系非常密切，它常常要用到这些学科的知识。设计求解几何问题的算法首先应该具备两个条件，一是分析并理解问题的几何特征，二是掌握计算几何中的几何结构、特殊的算法设计方法及相应的数据结构。由于本文的研究内容与几何算法的设计与分析相关，因此就必须介绍一下关于算法和数据结构的基本知识。2.3.1 算法算法是对特定问题求解步骤的一种描述，是指令的有限序列，是求解一个问题类的无二义性的有穷过程28。这里的求解过程是指求解问题执行的一步一步动作的集合，每一步动作只需要有限的存储单元和有限的操作时间。简单的说，算法就是解决特定问题的方法。描述一个算法可以采用文字叙述，也可以采用传统流程图、N-S图或PAD图等等。一个算法具有下列重要特性。(1)有穷性 算法只执行有限步，并且每步应该在有限的时间内完成。(2)确定性 算法中的每一条指令必须有确切的含义，无二义性。(3)可行性 算法中描述的操作都必须足够基本，即都是可以通过已经实现的基本运算执行有限次来实现。(4)输入 算法具有零个或多个输入。(5)输出 算法具有一个或多个输出，没有输出的算法没有任何意义。算法的复杂度是衡量算法效率的方法，其中包括算法的时间复杂度和算法的空间复杂度。为了说明复杂度的概念，先介绍问题规模的概念。随着处理问题的数据增大，处理会越来越困难复杂，把描述数据增大程度的量叫做问题规模37。规模越大，消耗的时间越多。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂度，它是规模n的函数，记为T(n)。算法的空间复杂度是指解决问题的算在执行时所占用的存储空间，记作S(n)28。下面主要讨论算法的时间复杂度。由于一般不需要知道精确的时间耗费，只要知道时间耗费的增长率大体在什么范围内即可，因此引入算法复杂度阶的概念。如果对某一个正常数c，一个算法能在时间2内处理规模是n的输入，则称此算法的时间复杂度是O(n2)，读作“n2阶”。一般情况下，都是取一个简单形式的函数作为阶数的规范，如，。一个算法的时间复杂度，如果是O(2n)，则称算法需要指数时间；如果是O(nk)(k为有理数)，则称此算法为多项式时间算法。当n很大时，指数时间算法和多项式时间算法存在很大的差别。以多项式时间为限界的算法称为有效算法。因此应该尽可能选用多项式阶O(nk)的算法，而不希望用指数阶的算法。算法的时间复杂度可分为最坏情况的时间复杂性和平均情况的时间复杂性30。对于给定规模为n的各种输入，某算法执行每条指令所需要的时间之和的最大值，称为该算法的最坏情况的时间复杂性；对于给定规模为n的各种输入，执行每条指令所需要的时间之和的平均值，称为平均情况的时间复杂性(或期望复杂性或平均特性)。由于规模为n的输入出现的概率不同，所以有时要考虑加权平均特性。2.3.2 数据结构数据结构是指相互之间存在着一种或多种特定关系的数据元素的集合，简言之是带结构的数据元素的集合37。由于算法与数据结构关系非常紧密，因此在进行算法设计时首先要确定相应的数据结构。本文除了用到通用的数据结构邻接表、队列以外，还用到一种特殊的结构：双向链接边表DCEL(Doubly Connected Edge List)27。双向链接边表适于表示嵌入到平面的平面划分，它是一种简单而有效的数据结构，并且是一种基于边的表示方法，同时包含顶点和面(平面划分面)的信息。也就是说，对于任一个子区域，与之相对应的双向链接边表为其中的每个顶点，每条半边和每张面都设置了一个记录，即顶点记录、半边记录和面记录，在这些记录中，分别存有几何信息、拓扑信息和附加信息。在双向链接边表数据结构中，规定每条无向边都由两条具有相对方向的半边(Half Edge)表示，这两条半边互称为孪生半边，并且都与它左侧的面相关联；对于任何一条半边，都有唯一的一条后继半边，以及唯一的一条前驱半边；每条有向半边都有起点和终点。下面给出DCEL结构的各组成部分，如图2-4所示。一般情况下，在对应顶点的顶点记录中，设有一个名为Coordinates(v)的域，用来存放顶点的坐标。此外，还有一个名为IncidentEdge(v)的指针，指向以顶点为起点的某一条半边。在对应于面的面记录中，设有一名为Outerponent(f )的指针，指向该面的外边界(Outer Boundary)上的任意一条半边。若是无界面(Unbouned Face)，则此指针为Null。此外，还有一个名为Innerponent(f )的列表，其中设有多个指针，分别对应于该面的各个空洞；每个指针所指的，是其对应空洞的边界上的某一条半边。在对应于半边的半边记录中，设有一个名为Origin(e)的指针，指向该半边的起点；另有一个名为Twin(e)的指针，指向其孪生半边；还有一个名为IncidentFace(e)的指针，指向位于半边左边的面，即半边参与围成的那张面。半边的终点无需存储，因为它等于Origin(Twin(e)。半边起点的选取，要使得从半边的起点走向终点的过程中，IncidentFace(e)位于的左侧。此外，半边记录中还设有两个指针Next(e)和Prev(e)，分别指向沿着IncidentFace(e)边界的半边的后继半边与前驱半边。这样，沿着IncidentFace(e)的边界，以的终点为起点的半边只有Next(e)一条，而以的起点为终点的半边也只有Prev(e)一条。Origin(e)Next(e)IncidentFace(e)Twine(e)ePrev(e)图2-4 DCEL结构的各组成部分Fig. 2-4 ponent of DCEL structure每个顶点和每条边所对应的信息量，都是常数规模的。面记录占用的空间可能会更多一些，因为面f中含有多少个空洞，列表Innerponent(f )中就需要有多少项。然而，只要将所有的Innerponent(f )列表合起来统计，就会发现其中指向任何一条半边的指针都不会超过一个。由此可以得出结论：每个平面划分所需存储空间的规模，与该平面划分本身的复杂度呈线性关系。e1,a下面给出了一个简单的平面划分区域的子区域所对应的双向链接边表，如图2-5所示。表2-1、表2-2和表2-3分别给出相应的顶点记录、面记录、半边记录。e1,be4,ae4,be3,be3,af1e2,ae2,bv4v3v2v1f2图2-5 简单的平面划分Fig. 2-5 Simple planar subdivision表2-1 顶点记录Table 2-1 Records of verticesVertexCoordinatesIncidentEdgev1(0,4)e1,av2(2,4)e4,bv3(2,2)e2,av4(1,2)e2,b表2-2 面记录Table 2-2 Records of facetsFaceOuterponentInnerponentsf1Nulle1,af2e4,aNull表2-3 半边记录Table 2-3 Records of half edgesHalf-edgeOriginTwinIncidentFaceNextPreve1,av1e1,bf1e4,be3,ae1,bv2e1,af2e3,be4,ae2,av3e2,bf1e2,be4,be2,bv4e2,af1e3,ae2,ae3,av3e3,bf1e1,ae2,be3,bv1e3,af2e4,ae1,be4,av3e4,bf2e1,be3,be4,bv2e4,af1e2,ae1,a上面介绍的双向链接边表，只是一种通用版本。在某些具体的应用中，顶点v本身可能不含任何属性信息，此时，就可以将它们各自的坐标，直接存储在相关联的半边的Oringe( )域中，而不必专门为顶点记录定义一种数据类型。除此之外，在很多实际应用中，子区域划分中的面并不具有任何含义，此时可以完全舍弃掉面记录，以及各半边对应的IncidentFace( )域。在双向链接表的某些实现中，可能要求平面划分的顶点和边所对应的图是连通的，既然连通图对应的子区域划分绝对不会出现空洞，因此列表Innerponent( )也就不必存在了。2.4 本章小结本章主要对Minkowski和算法涉及的基本知识进行了简要的介绍。几何学是整个Minkowski和算法设计的基础，本章首先介绍了与研究内容相关的基本几何对象的定义。其次，描述了Minkowski和的概念及性质，并介绍了相关的几何操作，如平面划分的叠置、移动立方体算法等。最后，介绍了有关算法的基本知识，重点介绍了双向链接边表。通过对算法所涉及的基本知识的介绍，为后续研究奠定了基础。第3章 计算凸多面体的精确Minkowski和3.1 引言在欧几里得三维空间中，求两个凸多面体的Minkowski和是一项重要的几何操作，它等同于两个凸多面体中所有点的矢量和的集合38。为了提高算法的执行效率、加快求和速度，在深入分析现有算法的基础上，本章脱离以往算法中基于传统的高斯映射的算法，提出一种全新的计算凸多面体精确Minkowski和的算法。该算法以文献27中的子区域划分的叠置算法为基础，通过给出一种自定义的映射方式，即正四面体映射和点投影，把三维空间的问题转换到二维空间进行解决，求两个凸多面体的Minkowski和就等同于计算一对平面划分的叠置。除此之外，还根据求和的需要及特征完成了属性分配过程。3.2 现有的Minkowski和求和算法为了求两个凸多面体的Minkowski和，研究人员已经提出了多种有效的方法。下面主要介绍基于立方体高斯映射的凸多面体Minkowski和求和算法，并对其进行分析。基于高斯映射的定义，E.Fogel和D.Halperin在文献24中提出了CGM的概念。它可以描述为：在欧几里得三维空间内，凸多面体的CGM是一个从多面体体元到立方体表面的集值函数。首先，为凸多面体P的每个点p分配一条指向P的支撑平面的法线向量，则P的每个小面均对应着一条法向量，使所有法向量的起始点都处在立方体的中心，这样多面体的一个小面就能够映射为立方体某个面上的一个点；然后，按照同样的映射规则，多面体的一条边至多映射为三条连接的线段，它们分别位于三个邻接的立方体表面上；多面体的一个顶点映射为一个凸多边形，此多边形至多位于五个邻接的立方体表面上。在这里，立方体的边平行于坐标轴，并且长度为2。与基于倾斜图的求和方法相似，该算法同样是把三维空间中的问题转换到二维空间进行解决，而两者不同之处在于，后者通过把多面体体元映射到立方体表面，以达到降维的目的。下面给出这种求和算法的简单描述。算法3.1：基于CGM的两个凸多面体的Minkowski和的算法CGMO。输入：由CGM表示的凸多面体；输出：,其中P为由CGM表示的Minkowski和多面体。CGMO (P0, P1 Pr, P)Begin(1) P;(2) for (i=1; ir; +i)把的所有边插入到P中;(3) for (i=0; ir; +i)把的附加信息加入到的相应附加信息中;(4) 计算存储在边界半边和边界顶点内的附加信息;(5) 计算Minkowski和多面体的每个小面的方程式;(6) Return P;End在步骤2中，对于Pi表面上的每一条映射边(不妨设为e)，均对应着一条含有指针的线段l，l在拓扑上等于边e，其指针指向边e的任意一条半边。在这一步中，实际上是把线段l插入到P的表面划分中；当此步结束时，在P的表面划分中，每条边(不妨设为)都含有一个指针，该指针指向所源于的半边。整个插入过程主要基于平面直线扫描算法27。在步骤3中，Pi的每个平面划分面都存储着相应的附加信息，这些附加信息是与划分面相对应的多面体Pi的顶点坐标。也就是说，Minkowski和多面体的顶点坐标被存储在P的划分面内。为了计算P的附加信息，对于每个输入值，都需要遍历P的所有平面划分面。采用上面的求和算法计算两个凸多面体的Minkowski和等同于计算六对平面划分的叠置，并通过计算存储在划分面中的附加信息，最终能够得到由CGM表示的Minkowski和多面体。该算法仅仅适用于计算凸多面体的Minkowski和，对于凹多面体的情况无能为力。3.3 相关定义定义4.1：体元 在欧几里得三维空间中，称多面体的顶点、棱、面为多面体的体元25。定义4.2：凸多面体(非凸多面体) 把多面体的任一个面展成平面，如果其余的面都位于这个平面的同一侧，这样的多面体叫凸多面体。反之，则为非凸多面体。定义4.3：外包正四面体 假设一凸多面体在正四面体内部，且正四面体的中心在凸多面体内部，则称该正四面体为凸多面体的外包正四面体。定义4.4：邻接表(Adjacency List) 对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表37。3.4 正四面体映射下面首先给出正四面体映射的定义，然后通过选定的空间坐标系，根据映射规则把凸多面体上的体元映射到正四面体的表面，并给出了具体的映射关系式。3.4.1 正四面体映射的定义定义4.5：正四面体映射 以凸多面体的外包正四面体的中心为起点(求解时对所有凸多面体的外包正四面体，都定义为单位正四面体)，向凸多面体上的任意点(包括凸多面体的顶点以及边上的点)引射线，该射线与正四面体的交点，为凸多面体体元在正四面体上的映射点，该映射称为正四面体映射。正四面体映射的映射过程为：凸多面体的点映射为正四面体的面上的点；边映射为一条或多条连接的线段，并且这些线段处在一个或几个邻接的三角形面内，假设凸多面体棱AB的两个端点映射在不同的面上，分别为面和面，则AB映射为两条线段，这两条线段的交点在面和面的相交线上；面映射至多处在三个连接面内的凸多边形。这样，通过映射得到凸多面体的正四面体映射，也就是正四面体表面的划分，记作T。并且由于映射源为凸多面体，因此对四个三角形面的划分均为凸划分。正四面体映射的每个面由三个顶点和三条边进行初始化，这些顶点和边定义了一个正三角形。在创建正四面体映射时，这些顶点、边或者边的一部分都可能成为投影的真实图元，同时还需要引入非真实图元，它不仅可以加快遍历，而且对于计算两个平面划分的叠置也是必要的。3.4.2 空间坐标转换关系为了有效的计算凸多面体Minkowski和的精确值，首先必须对三维空间中的每个点定义精确的坐标值，同时还需要恰当的选取坐标系。下面给出本文选取的坐标系，如图4-1，空间坐标系的原点O为底面三角形的中心，x轴平行于，正方向为向量的方向，y轴正方向为x轴逆时针旋转90度方向，z轴正方向为向量的方向。其中，O为正四面体的中心。p3xyOp1p0p2zO图4-1 坐标系的选取Fig. 4-1 Choosing of Coordinate System给定了坐标系的选取，可以得到凸多面体映射到正四面体表面的坐标转换关系式。设A为凸多面体上任意的一点，坐标为(x,y,z)。则映射关系式分为以下几种情况。若射线OA与底面相交，通过正四面体映射在面上的新坐标为，则两个坐标之间的映射关系为式(4-1)，其中。 (4-1)若射线OA与侧面相交，通过正四面体映射在面上的新坐标为，则两个坐标之间的映射关系为式(4-2)。 (4-2)若射线OA与侧面相交，通过正四面体映射在面上的新坐标为，则两个坐标之间的映射关系为式(4-3)。 (4-3)若射线OA与侧面相交，通过正四面体映射在面上的新坐标为，则两个坐标之间的映射关系为式(4-4)。 (4-4)对于任意两个点和，如果，三个条件中至少有一个成立，则映射后；同时，对于映射后的任意点都对应着唯一的，因此该映射是可逆的。3.4.3 数据结构及相关信息凸多面体的正四面体映射前后需记录一些信息，第一次记录映射前凸多面体的顶点和顶点之间的关联关系，以及多面体的棱，用于映射后划分平面；第二次是记录正四面体表面的划分，用于3.5节中投影后划分平面。对于第一次记录，采用数据结构中的邻接表来记录顶点的坐标值及与该顶点相关的边。对凸多面体中的每个顶点建立一个单链表（n个顶点建立n个单链表），第个单链表中的结点表示与顶点的所有邻接顶点，因此也称为邻接表，即中每个表结点均有两个域，存放与相邻接的顶点的序号的邻接点域adjvex和将邻接表的所有表结点链在一起的链域next。例如：顶点vi邻接表的头结点包含两个域：存放顶点vi的信息(坐标值)的顶点域vertex和vi的邻接表的头指针即指针域firstedge。对于第二次记录，采用DCEL数据结构表示平面划分中顶点、半边和面(指平面划分面)之间的关联关系，特定地设置顶点记录、半边记录和面记录。设置情况如下，其中顶点记录为：顶点的坐标，以该顶点为起点的任意一条关联半边；半边记录为：半边的终点，半边的孪生半边，半边的后继半边，半边的相关面，在半边的相关面中存储着与它相关联的平面划分面，若关联面为三角形以外的区域，则记为Null；面记录为：与该面相关联的任意一条半边。在这些记录中不仅存有几何的、拓扑的信息，而且还存储着一些辅助信息。对于整个求和过程，这些信息是十分必要的。其中，顶点的辅助信息为：(1)该顶点是否为真实图元(即是否存在凸多面体上的点映射到正四面体的顶点)；(2)该顶点是否处在正四面体的顶点位置、棱上或者三角形面内；半边的辅助信息为：该半边是否为真实图元(即是否存在凸多面体的棱映射为该半边)。通过本节给出的坐标之间的映射关系，可以把凸多面体上的顶点坐标转换为相应的正四面体表面上的坐标，并记录相应的信息。为了便于平面划分叠置的计算，需要把三维空间问题转换到二维平面下解决，下面将给出正四面体侧面划分节点投影到面P的方法。3.5 点投影下面首先给出点投影的定义，然后根据投影规则把正四面体表面上的划分点投影到平面P，并给出了具体的点投影关系式。3.5.1 点投影的定义定义4.6：点投影 将正四面体表面(包括棱)上的任意划分点投影到指定区域，称为点投影。如图4-2。p1p3xyOp1p0p2zOp2p0nkm图4-2 正四面体的侧面划分节点投影到平面PFig. 4-2 The no