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

1、学位论文三维空间内凹多面体的minkowski和的算法研究2009年11月工学硕士学位论文三维空间内凹多面体的minkowski和的算法研究硕士研究生：导师：申请学位级别：工学硕士学 科、专 业：计算机应用技术所 在 单 位：信息科学与工程学院授予学位单位：classified index: tp301.6u.d.c.: 654dissertation for the master degree in engineeringresearch on computing minkowski sum of non-convex polyhedral in thress demensioncandid

2、ate:supervisor:academic degree applied for:master of engineeringspeciality:computer application technologyuniversity:yanshan university硕士学位论文原创性声明本人郑重声明：此处所提交的硕士学位论文三维空间内凹多面体的minkowski和的算法研究，是本人在导师指导下，在攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结

3、果将完全由本人承担。 作者签字 日期： 年 月 日硕士学位论文使用授权书三维空间内凹多面体的minkowski和的算法研究系本人在攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归所有，本人如需发表将署名为第一完成单位及相关人员。本人完全了解关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 保密，在 年解密后适用本授权书。本学位论文属于不保密。（请在以上相应方框内打“” ）作者签名： 日期： 年 月 日导师签名： 日期： 年 月 日摘要摘 要

4、计算几何是计算机理论科学的一个重要分支，该学科已经有了巨大的发展，产生了一系列的理论成果。minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义，其研究成果已在机器人学、动态仿真、计算机图形学等许多领域中得到了广泛的应用，尤其在机器人学领域，它是计算无碰撞路径的一个重要工具。因此，如何快速而准确地计算避障路径，一直是国内外学者研究的重要课题。首先，在对国内外研究现状进行综合分析的基础上，进一步研究了计算两个凸多面体minkowski和的求和算法。本文脱离以往算法中基于传统的高斯映射的算法，以减少计算平面划分叠置的次数、提高算法的执行效率为目标，提出了正四面体映

5、射和点投影的概念，通过计算凸多面体的正四面体映射和点投影，把三维空间的问题转换到二维平面进行解决。其次，凸剖分是计算凹多面体的minkowski和的一个重要步骤。为了有效地计算凹多面体的minkowski和，在研究了国内外许多凸剖分算法后，本文采用集合论和图论的思想，提出了基于成功回路的凹多面体的剖分算法，同时对剖分算法的时间复杂度进行了分析。再次，给出了计算凹多面体的minkowski和算法的总体思想。采用成功回路的算法对凹多面体进行剖分，得到若干子凸多面体；利用正四面体映射和点投影的算法计算所有可能成对的子凸多面体的minkowski和；通过已改进的enhanced marching cu

6、bes算法合并子凸多面体的minkowski和多面体的边界。最后，通过实验验证了上述的研究内容，给出了实验结果，并将结果与现有的算法进行了对比分析。关键词 计算几何；正四面体映射；点投影；凹多面体；成功回路；enhanced marching cubes；minkowski和iiiabstractabstractcomputational geometry is an important embranchment of computer theoretical science. the subject has already made a tremendous development and

7、produced a series of theoretical results. minkowski sum algorithm has the great significance in theory and application as an embranchment of computational geometry. it plays an important role in robotics, dynamic simulation, computer graphics, and so on, especially in the field of robotics, it is an

8、 important tool for computing collision-free path. therefore, how to calculate the path of obstacle avoidance quickly and accurately has been an important research subject of the home and foreign scholars.firstly, this paper researches the existed approach of minkowski sum of two convex polyhedral.

9、in order to reduce the amount of computing overlay of two planar subdivisions and improve the efficiency of the algorithm, this paper separates from the previous algorithm based on the traditional gaussian map and proposes the method of regular tetrahedron map and point projection to resolve this pr

10、oblem. through this method, it can reduce the problem in 3d to 2d. secondly, convex decomposition is an important step of computing minkowski sum of two non-convex polyhedral. so, for effectively computing the minkowski sum of non-convex polyhedral, the papers uses the idea of set theory and graph t

11、heory and propose a new algorithm to decompose non-convex polyhedron that based on successful loop after studying the convex decomposition algorithms. at the same time, the complexity of the algorithm is analyzed.thirdly, the paper gives the overall idea of computing the minkowski sum of non-convex

12、polyhedral. it uses successful loop to decompose non-convex polyhedral into convex pieces, then computes their pair wise minkowski sum that based on regular tetrahedron map and point projection, last, uses the reformative approach of the enhanced marching cubes to unite the boundary of polyhedral mi

13、nkowski sum of the sub polyhedral. finally, we validate the above algorithm and give the results. we also do some comparison and analysis with the existing algorithm.keywords computational geometry; regular tetrahedron map; point projection; non-convex polyhedron; successful loop; enhanced marching

14、cubes; minkowski sum目录目录摘 要iabstractii第1章 绪论11.1 课题研究意义11.2 minkowski和算法的研究现状21.2.1 国外研究现状31.2.2 国内研究现状41.3 minkowski和算法的应用61.3.1 机器人路径规划61.3.2 碰撞检测61.4 本文研究内容71.5 本文组织结构8第2章 理论基础92.1 相关的几何定义92.1.1 欧几里得空间92.1.2 点92.1.3 直线与线段92.1.4 多面体102.1.5 平面图及平面划分102.1.6 凸集与凸包102.2 基础知识及内容102.2.1 minkowski和的定义102

15、.2.2 minkowski和的性质112.2.3 平面划分的叠置122.2.4 边界表示法132.2.5 移动立方体算法132.3 算法与数据结构132.3.1 算法142.3.2 数据结构152.4 本章小结18第3章 计算凸多面体的精确minkowski和193.1 引言193.2 现有的minkowski和求和算法193.3 相关定义213.4 正四面体映射213.4.1 正四面体映射的定义213.4.2 空间坐标转换关系223.4.3 数据结构及相关信息243.5 点投影253.5.1 点投影的定义253.5.2 空间坐标转换关系263.5.3 数据结构及相关信息283.6 基于正四

16、面体映射和点投影的minkowski和求和算法283.6.1 算法思想293.6.2 算法描述303.6.3 算法分析333.7 本章小结34第4章 计算凹多面体的minkowski和354.1 引言354.2 凹多面体minkowski和求和算法概述354.3 凹多面体凸剖分算法364.3.1 凸剖分算法的研究现状364.3.2 相关定义与定理374.3.3 基于成功回路的凹多面体的剖分算法394.3.4 算法分析434.4 合并子minkowski和多面体434.4.1 相关定义434.4.2 合并子minkowski和多面体算法概述444.4.3 改进的合并算法454.4.4 算法分析4

17、74.5 计算简单凹多面体的minkowski和算法总体思想474.6 本章小结48第5章 实验与分析495.1 实验环境设置495.2 leda简介495.3 精确实数计算505.4 minkowski和求和算法的实验验证515.4.1 凸多面体minkowski和求和算法实现及分析525.4.2 简单凹多面体minkowski和求和算法实现及分析565.5 本章小结61结 论63参考文献65第1章 绪论第1章 绪论1.1 课题研究意义“计算几何”这个术语最初是由minsky和papert作为模式识别的代用词被提出来，到了a.r.forrost才有了正式的定义：“对几何外形信息的计算机表示、

18、分析和综合”。到了20世纪70年代末，shamos(沙莫斯)和hoey(霍伊)利用计算机有效地计算出平面点集的voronoi图，并发表了一篇著名的论文，从此一门新的学科计算几何从算法设计与分析中孕育而生1。该领域中的问题所带来的挑战性，也使得一大批科研人员为之呕心沥血、辛勤耕耘，从而使这一崭新的研究领域在比较短的时间内取得了辉煌的成果，对许多问题已经有了一系列比较成熟的计算几何算法。minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义。它广泛应用于机器人学、计算机图形学、固体建模、计算机动画和cad/cam等领域2。尤其在机器人学领域，minkowski和算

19、法起到了重要的作用，主要应用在机器人的运动规划中。机器人学(robotics)是与机器人设计、制造和应用等相关的学科，主要研究机器人的控制与被处理物体之间的相互关系3。机器人学有着极其广泛的研究和应用领域，这些领域体现出广泛的学科交叉，涉及众多的课题，如机器人控制、智能、传感、机器人装配以及机器语言等，在工业、农业、空间和海洋以及国防等领域得到越来越普遍的应用。机器人学的最终目标之一，就是设计出一个独立自主的机器人，它能够接受高级任务并且在没有人的干涉下自主执行并完成任务4。路径规划问题是指在有障碍物的工作环境中寻找一条恰当的从给定初始位姿到终止位姿的运动路径，使机器人在运动过程中能安全、无碰

20、撞地绕过所有障碍物5。因此，能否对运动路径进行快速而准确地规划成为衡量机器人智能高低的一个重要标准。为了更好地解决机器人的路径规划问题，人们往往用多面体模型来模拟工作空间中的机器人与障碍物，其中多面体又可以分为凸多面体和凹多面体。这样，检测机器人与障碍物之间的碰撞情况就转换为检测多个几何体之间的碰撞情况6。根据工作环境，机器人的路径规划可以分为动态路径规划和静态路径规划。动态环境即时变环境，含有运动轨迹已知或未知的障碍物。对于轨迹已知的情况下的规划可以将其转化为若干静态问题解决；但对于运动轨迹未知的情况，机器人需要在运动中不断地检测与障碍物之间的碰撞情况。在静态环境下，机器人仅仅能够做平移或翻

21、转运动，通常障碍物为静态的刚性物体，并且机器人与障碍物的几何形状和位置是已知的。在这种条件下，机器人可根据先验环境模型找出从起始点到目标点的可行或最优路径，并沿着这条路径顺利地完成任务。这个看似简单的问题在计算几何学中却成为具有挑战性的问题，并且成为机器人研究领域中的一个研究热点问题。minkowski和是计算无碰撞路径的一个重要工具，可以定义为，在欧几里得空间中，假设p和q为两个封闭的几何对象，那么p和q的minkowski和为几何对象m，其中p和q分别是p和q上的点，p+q是p和q的位置矢量和7。也就是说若，则有。假设多面体p为工作空间中的任意一个障碍物，多面体r为沿平面做平移运动的机器人

22、，则p所对应的r障碍物为，其中-r与r关于坐标原点对称。除此之外，minkowski和还可以用来计算两个多面体之间的渗透深度、精确检测物体之间的碰撞情况以及应用到机器人装配仿真等等，有着很广泛的应用8。可见，研究两个几何对象的minkowski和求和算法，对于解决机器人的路径规划问题有着十分重要的现实价值。1.2 minkowski和算法的研究现状1983年，t.lozano-perez首次利用minkowski和来计算位姿空间障碍物(configuration space obstacle)，并应用到机器人的运动规划中9。目前研究人员已经提出了计算三维空间内两个多面体的minkowski和的

23、多种不同方法，主要目标都是计算minkowski和的边界值，并提供一些方法来表示它10。其中，计算凸多面体的minkowski和的方法已经有了成熟的算法，而凹多面体的minkowski和一直停留在获得近似值。1.2.1 国外研究现状1987年，l.j.guibas和r.seidel提出了计算简单多胞体minkowski和多面体的敏感输出(output-sensitive)算法，该算法定义了二维平面上的一个操作，称作卷积(convolution)11。1996年，j.basch和l.guibas等人扩展了上述算法，提出了以定义在多面体运动轨迹上的卷积计算为基础的方法来计算三维空间内多面体的min

24、kowski和12。1993年，p.k.ghosh为计算凸多面体和凹多面体的minkowski和提出了统一的算法，它以倾斜图(slope diagram)表示法为基础13。计算两个多面体的minkowski和等同于分别计算两个多面体的倾斜图，然后合并它们的倾斜图，并从合并的倾斜图中提取minkowski和的边界值14。通过使用立体投影(stereographic projection)方法，多面体的倾斜图转换为二维图形，这样就把问题降低到较低维数的空间中进行解决。1997年，b.aronov和m.shair等人提出了计算普通多边形或多面体的minkowski和的基本框架：首先，对每个多边形(或

25、多面体)进行凸剖分，得到若干个子凸多边形(或多面体)；然后，计算取自不同多边形(或多面体)的所有可能成对的子凸剖分的minkowski和；最后，合并第二步中所有子minkowski和多边形(多面体)15。基于上面的剖分框架，2002年，p.k.agarwal和e.flato等人给出了计算凹多边形的minkowski和算法，并提出了多种不同的剖分方法16。由于凹多面体的minkowski和求和算法过于复杂，目前，人们主要研究能够得到满足某些标准的近似值的求和算法，如文献17,18。2000年，e.flato和d.halperin在文献19中给出了计算普通多边形的minkowski和算法，该算法是

26、基于cgal(computational geometry algorithm library)20实现的。2001年，基于ghosh在文献13中提出的倾斜图表示法，h.bekker和j.b.t.m.roerdink比较了三种计算凸多面体minkowski和的方法，最终提出了在线性时间内计算三维空间凸多面体minkowski和的新方法，但是该方法只对非常简单的凸多面体适用21。2002年，e. flato和f.fogel等人给出了minkowski和算法的应用领域，提供了为建造平面集合的精确、有效的minkowski和所使用的软件包22。2003年，y.y.wu和j.j.shah等人分别对基于

27、凸包(convex hull)的凸多面体的minkowski和求和算法与基于倾斜图的凸多面体的minkowski和求和算法进行了优化23。遵循文献13提出的方法，2007年，e.fogel和d.halperin提出了基于立方体高斯映射cgm(cubical gaussian map)计算三维空间内凸多面体的精确minkowski和算法24，该算法也是基于cgal实现的。1.2.2 国内研究现状国内对minkowski和算法的研究起步较晚。其中，对凸多面体的minkowski和算法的研究取得了一些很好的成果；对凹多面体的剖分和子minkowski和多面体的合并的研究也有了一定的进展。2007年，

28、郭希娟和高艳丽提出了基于正四面体中心投影rtcp(regular tetrahedron central projection)和三角形内简单平面凸划分的叠置算法计算凸多面体精确minkowski和的优化算法25。基于正四面体中心投影算法，2008年，郭希娟和谢蕾又给出了进一步优化基于正四面体高斯映射rtgm(regular tetrahedron gaussian map)的算法26。通过对国内外研究现状的分析，可以得出计算多边形或者多面体的minkowski和算法主要有六种，即基于凸包的求和算法、基于凸剖分的求和算法、基于倾斜图的求和算法、基于立方体高斯映射的求和算法、基于正四面体中心投影

29、的求和算法以及基于正四面体高斯映射的算法。其中，基于凸包的minkowski和求和算法是非常著名的算法之一，该算法直接源于minkowski和的定义，它可以表示为：，其中，ch表示凸包操作，、分别表示多面体p和q中顶点的集合15。在计算minkowski和多面体的过程中，该算法需要区分内部点、外部点和边界点，创建这些点集的凸包不但需要很高的计算费用，并且该算法的计算结果不是图而是一个点集。基于倾斜图的minkowski和求和算法，根据高斯映射的规则，把多面体的体元(包括多面体的顶点、棱、面)映射到单位球表面，并采用立体投影方法把每个多面体的倾斜图转化为平面图形，然后计算平面图形的叠置，从叠置的

30、结果中抽取minkowski和的边界值。采用立体投影方法不仅会使算法在处理退化情况时存在着很大的局限性，而且会增加算法的实现难度，很难得到精确的计算结果。基于立方体高斯映射的minkowski和求和算法，通过自定义的立方体高斯映射，把三维空间内的凸多面体的体元映射到立方体表面，从而得到六个平面划分面，计算两个凸多面体的minkowski和就等同于计算六对平面划分的叠置。通过计算六对平面划分中各面的附加信息，得到minkowski和多面体的立方体高斯映射表示，最后求逆映射得到精确的minkowski和多面体。基于正四面体中心投影的minkowski和算法，首先按照高斯映射规则，将凸多面体映射到单

31、位球面上，再取单位球面的外切正四面体，通过自定义的正四面体中心投影得到凸多面体在正四面体上的投影。求两个凸多面体的minkowski和等同于求四对平面划分的叠置。通过计算四对平面划分中各面的附加信息，得到新多面体的正四面体中心投影，最后求逆映射得到minkowski和多面体。基于正四面体高斯映射的minkowski和算法，为计算两个给定位置和形态的凸多面体的minkowski和表示，取凸多面体的外切正四面体，根据自定义的正四面体高斯映射把凸多面体映射到外切正四面体的四个表面上，求两个凸多面体的minkowski和等同于求四对平面划分的叠置，通过计算平面划分中各面的附加信息，得到新多面体的正四面

32、体高斯映射，最后求逆映射得到minkowski和多面体。基于凸剖分的minkowski和算法，是计算凹多边形或凹多面体的minkowski和的常用算法。对于二维空间内的凹多边形而言，常用的方法就是把凹多边形剖分为若干个凸多边形，通过计算凸多边形minkowski子和的并来得到凹多边形的minkowski和。理论上，剖分策略的选择与求和速度无关，但实际上，它严重影响着整个求和算法的运行时间，特别是计算三维空间内的凹多面体的minkowski和。因此，迫切需要寻找某种策略来降低计算凹多面体的minkowski和的求和算法的时间复杂度，同时由于基于剖分法中的合并算法的复杂度很高，目前仍然没有人提出计

33、算凹多面体的精确minkowski和的算法。因此研究凹多面体的精确minkowski和求和算法是一项具有挑战性及重要意义的课题。1.3 minkowski和算法的应用minkowski和算法在许多领域中有着广泛的应用，如机器人学、碰撞检测、模拟仿真、计算机图形学等等，下面重点介绍该算法在机器人路径规划和碰撞检测中的应用。1.3.1 机器人路径规划机器人学的最终目标之一，就是设计出独立自主的机器人。在指挥这种机器人时，只需要告诉它去做什么，而不必告诉它如何去做，其中尤为重要的一个方面就是，机器人应该懂得如何对自己的运动进行规划27。路径规划是机器人学算法中的一个重要问题，其本质是在众多障碍物之间

34、为机器人寻找一条最优或近似最优的无碰撞路径，该问题经常用位姿空间方法来描述。所谓的位姿空间，也称c空间，是机器人的参数空间；机器人的工作空间是机器人在其中实际运动的那个空间，也就是真实的世界。自由c空间(free configuration space)是机器人避免与障碍物发生碰撞的所有位置点的集合27。为了规划路径，需要拥有一个能够捕捉自由位姿空间连通性的表示，而minkowski和算法可以来计算所需的表示，并且能够获得一条精确的无碰撞路径。假设多面体p为工作空间中的障碍物，多面体r为移动机器人，那么通过计算位姿空间障碍物来确定一条无碰撞的路径，这个问题就转变为计算多面体p与-r的minko

35、wski和，其中-r与r关于坐标原点对称。1.3.2 碰撞检测碰撞检测是检测两个物体在空间中是否重叠或它们的边界线是否至少共享一个点17。在虚拟环境中，由于用户的交互，物体之间经常发生碰撞，为保持虚拟环境的真实感和用户的沉浸感，快速精确的碰撞检测是必不可少的。传统的碰撞检测方法主要有空间分解法和层次包围盒技术，这两种算法都只能近似的检测物体是否发生碰撞，minkowski和算法能够精确地检测出物体之间是否发生碰撞。该问题用渗透深度来描述，两个多面体p和q的渗透深度是指使得两个多面体不相交，其中一个多面体必须移动的最小距离17。通过计算原心到minkowski和()表面上的最小距离来得到。若渗透

36、深度大于等于零，说明两个多面体发生碰撞，反之，两个多面体不会发生碰撞。1.4 本文研究内容本文在对国内外研究现状全面分析的基础上，完成对三维空间内凹多面体minkowski和求和算法的进一步研究，主要包括下述内容。(1)计算简单凸多面体的minkowski和的求和算法 通过深入研究正四面体中心投影算法和正四面体高斯映射算法，发现这两种算法都需要计算四次划分平面叠置，并且都没有给出具体的映射函数关系式。因此，本文提出了正四面体映射和点投影的概念，把三维空间的问题转换到二维空间进行解决，且只需要计算一对平面划分的叠置，更高效的计算凸多面体的精确minkowski和。(2)简单凹多面体的剖分算法 通

37、过深入研究国内外凹多面体的剖分算法，发现大多数的剖分算法会生成大量新点，产生很多凸多面体。因此，本文采用图论和集合论的思想，提出了基于成功回路的凹多面体的剖分算法，该算法不仅不产生新的顶点，而且能够处理有空洞的多面体。(3)计算简单凹多面体的minkowski和求和算法 首先，根据(2)中提出的剖分算法对凹多面体进行剖分，得到若干子凸多面体；其次，利用(1)中提出的求和算法计算所有可能成对的子凸多面体的minkowski和；最后，在合并子凸minkowski和多面体时，利用已改进的enhanced marching cubes算法获得凹多面体的近似的minkowski和多面体边界。1.5 本文

38、组织结构论文分为5章，其余部分组织如下。第2章介绍与本课题相关的基础理论。首先，是对基本几何定义的介绍；然后，阐述了minkowski和的定义、性质及相关的几何操作；最后，介绍有关算法的基本知识，该部分为课题的研究打下了坚实的理论基础。第3章提出了一种新的计算凸多面体的minkowski和的求和算法。首先，介绍现有的求和算法，分析它的主要思想；然后，以提高算法的执行效率为目标，提出正四面体映射和点投影的概念，给出正四面体映射和点投影的映射规则，并由此提出基于该映射的凸多面体的精确minkowski和求和算法。最后，对算法的时间复杂度进行了分析。第4章提出了一种新的凹多面体的剖分算法，并给出了计

39、算凹多面体的minkowski和求和算法思想。以提高算法的精确度和效率为目标，首先，本章采用图论和集合论的思想，提出了基于成功回路的凹多面体的剖分算法；其次，在合并子凸多面体minkowski和时，利用现有已改进的enhanced marching cubes算法，最终获得近似的多面体minkowski和边界；最后，给出计算简单凹多面体minkowski和的算法的总体思想。第5章是实验与分析，对所研究的内容及算法进行了实验验证并给出实验结果。最后，对本课题进行了全面总结，同时针对课题中存在的问题提出了进一步改进的思路，并规划了未来的研究方向。7第2章 理论基础第2章 理论基础下面给出一些本章中

40、将要用到的几何概念、定义和基础知识。2.1 相关的几何定义本文考虑的对象是欧几里得三维空间中的点集，假设有一个参考坐标系，使得每个点表示为相应维数的笛卡尔坐标的向量。除了点之外，还将考虑包含两个给定点的直线、直线上两定点确定的直线段、三个给定点确定的平面等。下面给出本文所涉及到的基本几何对象的定义。2.1.1 欧几里得空间若用(或)表示维欧几里得空间，那么具有度量的实数的元组空间，称为欧几里得空间28。2.1.2 点中的点定义为一个元组。点也可以解释为有个分量的向量，此向量的起点为坐标原点，终点为点28。点是整个几何学的基础，它只有位置，没有大小。2.1.3 直线与线段在中给定两个不同的点和，

41、线性组合(是实数，即)是中的一条直线28。给定中两个不同的点和，若在线性组合中加入条件，则得到点和的凸组合，即(，)，35第3章 计算凸多面体的精确minkowski和此凸组合描述了连接两点和的直线段，并记为(无序对)28。线段是直线的一部分，并以两个端点为界限。2.1.4 多面体由若干平面多边形围成的封闭连通的空间区域称为多面体(允许有洞)29。一般说来，多面体是指边界和内部域的并。多边形的顶点和边是多面体的顶点和边，多边形是多面体的小面。2.1.5 平面图及平面划分假设图g=(v，e)，其中v为顶点集，e为边集，如果图g能够没有交叉地嵌入平面，那么称图g为平面图。平面图的直线平面嵌入确定平

42、面的一个划分，称为平面划分(也称平面剖分)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.

43、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的点，为位置矢量与的矢量和。例如，在欧

44、几里得二维平面内，假设并且，那么有。下面给出二维平面内两个三角形的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条边，则minkow

45、ski和是由不超过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均为非凸多面体，则计算所需

46、要的时间为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 pla

47、nar subdivisions一般的叠置问题，首先给出分别对应于d1和d2的两个双向链接边表，然后计算出对应于overlay(d1,d2)的双向链接边表，同时要求对overlay(d1,d2)中的每张平面划分面加上标注，以指明在d1和d2中它分别属于哪张平面划分面，这样能够直接访问存储在这些面记录中的附加信息。双向链接边表的定义将在2.3节中给出。2.2.4 边界表示法物体可以通过描述它的边界来表示，称为边界表示法34。边界就是物体内部点与外部点的分界面。定义了物体的边界，该物体也就被唯一的定义了。边界表示法的一个很重要的特点是描述了物体的信息，包括几何信息与拓扑信息两个方面。物体的几何信息

48、是指顶点、边、面的位置、大小、形状等几何数据。拓扑信息是指物体上所有的顶点、棱边、面间的连接情况35。2.2.5 移动立方体算法移动立方体mc(marching cubes)算法是基于规则体数据抽取等值面的经典算法36。传统的mc算法的基本思想是逐个处理数据场中的立方体(体单元)，分类出与等值面相交的立方体，采用插值计算出等值面与立方体的交点。根据立方体每一顶点与等值面的相对位置，将等值面与立方体的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近。该算法对体数据中的体素逐个进行处理，每个被处理的体素，以三角面片表示其内部的等值面。2.3 算法与数据结构算法与数据结构专门研究从解决

49、非数值计算的现实问题中抽象出来的数据在计算机中如何表示、快速存取和处理的方法。计算几何与计算机科学中的算法设计与分析、数据结构等学科的关系非常密切，它常常要用到这些学科的知识。设计求解几何问题的算法首先应该具备两个条件，一是分析并理解问题的几何特征，二是掌握计算几何中的几何结构、特殊的算法设计方法及相应的数据结构。由于本文的研究内容与几何算法的设计与分析相关，因此就必须介绍一下关于算法和数据结构的基本知识。2.3.1 算法算法是对特定问题求解步骤的一种描述，是指令的有限序列，是求解一个问题类的无二义性的有穷过程28。这里的求解过程是指求解问题执行的一步一步动作的集合，每一步动作只需要有限的存储

50、单元和有限的操作时间。简单的说，算法就是解决特定问题的方法。描述一个算法可以采用文字叙述，也可以采用传统流程图、n-s图或pad图等等。一个算法具有下列重要特性。(1)有穷性 算法只执行有限步，并且每步应该在有限的时间内完成。(2)确定性 算法中的每一条指令必须有确切的含义，无二义性。(3)可行性 算法中描述的操作都必须足够基本，即都是可以通过已经实现的基本运算执行有限次来实现。(4)输入 算法具有零个或多个输入。(5)输出 算法具有一个或多个输出，没有输出的算法没有任何意义。算法的复杂度是衡量算法效率的方法，其中包括算法的时间复杂度和算法的空间复杂度。为了说明复杂度的概念，先介绍问题规模的概

51、念。随着处理问题的数据增大，处理会越来越困难复杂，把描述数据增大程度的量叫做问题规模37。规模越大，消耗的时间越多。利用某算法处理一个问题规模为n的输入所需要的时间，称为该算法的时间复杂度，它是规模n的函数，记为t(n)。算法的空间复杂度是指解决问题的算在执行时所占用的存储空间，记作s(n)28。下面主要讨论算法的时间复杂度。由于一般不需要知道精确的时间耗费，只要知道时间耗费的增长率大体在什么范围内即可，因此引入算法复杂度阶的概念。如果对某一个正常数c，一个算法能在时间cn2内处理规模是n的输入，则称此算法的时间复杂度是o(n2)，读作“n2阶”。一般情况下，都是取一个简单形式的函数作为阶数的

52、规范，如，。一个算法的时间复杂度，如果是o(2n)，则称算法需要指数时间；如果是o(nk)(k为有理数)，则称此算法为多项式时间算法。当n很大时，指数时间算法和多项式时间算法存在很大的差别。以多项式时间为限界的算法称为有效算法。因此应该尽可能选用多项式阶o(nk)的算法，而不希望用指数阶的算法。算法的时间复杂度可分为最坏情况的时间复杂性和平均情况的时间复杂性30。对于给定规模为n的各种输入，某算法执行每条指令所需要的时间之和的最大值，称为该算法的最坏情况的时间复杂性；对于给定规模为n的各种输入，执行每条指令所需要的时间之和的平均值，称为平均情况的时间复杂性(或期望复杂性或平均特性)。由于规模为

53、n的输入出现的概率不同，所以有时要考虑加权平均特性。2.3.2 数据结构数据结构是指相互之间存在着一种或多种特定关系的数据元素的集合，简言之是带结构的数据元素的集合37。由于算法与数据结构关系非常紧密，因此在进行算法设计时首先要确定相应的数据结构。本文除了用到通用的数据结构邻接表、队列以外，还用到一种特殊的结构：双向链接边表dcel(doubly connected edge list)27。双向链接边表适于表示嵌入到平面的平面划分，它是一种简单而有效的数据结构，并且是一种基于边的表示方法，同时包含顶点和面(平面划分面)的信息。也就是说，对于任一个子区域，与之相对应的双向链接边表为其中的每个顶

54、点，每条半边和每张面都设置了一个记录，即顶点记录、半边记录和面记录，在这些记录中，分别存有几何信息、拓扑信息和附加信息。在双向链接边表数据结构中，规定每条无向边都由两条具有相对方向的半边(half edge)表示，这两条半边互称为孪生半边，并且都与它左侧的面相关联；对于任何一条半边，都有唯一的一条后继半边，以及唯一的一条前驱半边；每条有向半边都有起点和终点。下面给出dcel结构的各组成部分，如图2-4所示。一般情况下，在对应顶点的顶点记录中，设有一个名为coordinates(v)的域，用来存放顶点的坐标。此外，还有一个名为incidentedge(v)的指针，指向以顶点为起点的某一条半边。在

55、对应于面的面记录中，设有一名为outercomponent(f )的指针，指向该面的外边界(outer boundary)上的任意一条半边。若是无界面(unbouned face)，则此指针为null。此外，还有一个名为innercomponent(f )的列表，其中设有多个指针，分别对应于该面的各个空洞；每个指针所指的，是其对应空洞的边界上的某一条半边。在对应于半边的半边记录中，设有一个名为origin(e)的指针，指向该半边的起点；另有一个名为twin(e)的指针，指向其孪生半边；还有一个名为incidentface(e)的指针，指向位于半边左边的面，即半边参与围成的那张面。半边的终点无需

56、存储，因为它等于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 component of dcel structure