MINKOWSKI和理论及应用/郭希娟

Minkowski和是计算几何研究领域的一个分支，可应用于引导机械装配中配合件的精准对接，监测机床刀具的切割渗透深度、机器人与障碍物的相对位置关系及机器人定位操作等实际情况；在机械装配、机器人路径规划、虚拟仿真等许多领域都有着很好广泛的应用前景。本书包含了作者10余年来在多面体Minkowski和算法理论和应用方面的研究成果，共分10章。章系统阐述了多面体Minkowski和计算方法和碰撞干涉检测算法的靠前外研究现状；第2章对本书中用到的相关基础理论知识进行了简要概述；第3章至第6章详细介绍了凸多面体Minkowski和的四种不同计算方法；第7章和第8章介绍了凹多面体的凸剖分理论方法，以及涉及凹多面体与凹多边形的Minkowski和算法；第9章和0章介绍了Minkowski和在飞机大部件自动对接和机械零件自动装配方面的一些应用成果。本书可供从事机械装配、机器人路径规划、虚拟仿真等领域研究的师生和学者在Minkowski和应用过程中进行参考。

郭希娟，燕山大学信息科学与工程学院教授、博士生导师，现从事计算机器人、计算机图像处理、无线网络通信等方面的研究。曾主持完成重量科研项目l项、省级科研项目8项，作为完成.人获得省部级奖励l项（河北省科学技术奖二等奖），在靠前外学术刊物和靠前会议上发表论文200余篇。

章Minkowski和的国内外研究现状（1）1.1Minkowski和定义（1）1.2Minkowski和算法研究现状（1）1.3碰撞检测算法研究现状（4）1.4本章小结（5）参考文献（5）第2章Minkowski和算法基础知识（12）2.1数学基础（12）2.1.1几何定义（12）2.1.2空间解析几何基础知识（15）2.1.3线性代数基础（15）2.1.4群论基础（16）2.2Minkowski和的性质（16）2.3工作空间和参数空间（17）2.3.1工作空间的概念（17）2.3.2参数空间的概念（17）2.3.3禁止C空间与自由C空间（17）2.3.4几何对称镜像的概念（18）2.4三维物体常用的描述方法（19）2.4.1八叉树表示法（19）2.4.2扫描表示法（19）2.4.3边界表示法（19）2.4.4半空间表示法（20）2.4.5CSG表示法（20）2.4.6高斯映射方法（20）2.5双向链接边表（21）2.5.1相关概念（21）2.5.2顶点记录（21）2.5.3半边记录（22）2.5.4面记录（23）2.5.5应用举例（23）2.5.6扩展的邻接表（25）2.6Voronoi图（25）2.6.1平面点的Voronoi多边形（25）2.6.2Voronoi图（26）2.6.3Voronoi图的对偶图（26）2.6.4Voronoi图的性质（26）2.6.5Delaunay三角形（27）2.7算法的预备知识（27）2.7.1算法的时间复杂度（28）2.7.2算法的空间复杂度（28）2.8本章小结（29）参考文献（29）Minkowski和理论及应用目录第3章基于正四面体高斯映射的凸多面体Minkowski和算法（31）3.1引言（31）3.2相关定义（32）3.3正四面体高斯映射（32）3.3.1正四面体高斯映射的定义（32）3.3.2空间坐标转换关系（33）3.4基于正四面体高斯映射的Minkowski和计算方法（35）3.4.1数据结构及相关信息（35）3.4.2算法思想（38）3.4.3算法描述（39）3.4.4算法分析（42）3.5三角形内简单平面凸划分的叠置算法（42）3.5.1基本概念（43）3.5.2数据结构（44）3.5.3叠置算法（44）3.5.4算法分析（50）3.6本章小结（50）参考文献（51）第4章直接映射的凸多面体Minkowski和算法（52）4.1引言（52）4.2相关定义及理论（53）4.3直接映射方法（55）4.3.1空间参数坐标系的建立（56）4.3.2菱形多面体高斯映射方法（56）4.3.3正三角形垂直映射方法（60）4.3.4算法正确性验证（61）4.3.5正三角形平面划分叠置遍历算法（62）4.3.6平移映射的凸多边形Minkowski和算法（67）4.3.7算法描述（70）4.3.8算法分析（71）4.4本章小结（72）参考文献（73）第5章基于分裂点的Minkowski和算法（74）5.1引言（74）5.2基于分裂点的平面凸多边形Minkowski和算法（74）5.2.1基于分裂点的凸多边形Minkowski和算法理论基础（74）5.2.2基于分裂点的凸多边形Minkowski和算法分析（78）5.3基于分裂点的空间凸多面体Minkowski和算法（81）5.3.1基于分裂点的凸多面体Minkowski和算法理论基础（81）5.3.2基于分裂点的Minkowski和算法分析（85）5.4本章小结（88）参考文献（88）第6章基于几何体代数结构的凸多面体Minkowski和计算方法（91）6.1引言（91）6.2多面体的代数结构（91）6.2.1多面体代数结构的构建（91）6.2.2多面体代数结构的性质（92）6.2.3多面体各顶点极点区域结构（94）6.3基于凸多面体代数结构的Minkowski和计算方法建模（96）6.3.1符号说明（96）6.3.2计算方法建模理论分析（96）6.4凸多面体的Minkowski和算法分析（101）6.4.1数据结构（101）6.4.2算法伪代码（104）6.4.3算法时间复杂度分析（105）6.5本章小结（107）参考文献（107）第7章凹多面体的Minkowski和算法（109）7.1引言（109）7.2凹多面体的四面体剖分算法（110）7.2.1算法数据结构（111）7.2.2算法思想（111）7.2.3多面体顶点凹凸性判断算法（112）7.2.4Delaunay三角剖分的算法（113）7.2.5凸剖分算法复杂度分析（114）7.3基于成功回路的凹多面体凸剖分算法（114）7.3.1相关定义与定理（114）7.3.2算法思想（116）7.3.3很优回路生成算法（116）7.3.4算法描述（117）7.3.5算法分析（118）7.4基于距离场的Minkowski子和合并算法（118）7.4.1相关定义（120）7.4.2网格点到三角面片的最短距离算法（121）7.4.3距离场符号生成算法（124）7.4.4改进的距离场生成算法（125）7.5基于改进的移动立方体Minkowski子和合并算法（126）7.5.1相关定义（126）7.5.2传统的移动立方体法（127）7.5.3改进的移动立方体算法 （129）7.5.4改进的移动立方体算法描述（136）7.5.5改进的移动立方体算法分析（138）7.6本章小结（139）参考文献（139）第8章涉及凹多面体及凹多边形的Minkowski和计算方法建模与分析（143）8.1引言（143）8.2基于几何体代数结构的凹多面体与凸多面体Minkowski和计算方法建模与分析（144）8.2.1简单凹多面体（145）8.2.2基于几何体代数结构的凹多面体与凸多面体Minkowski和计算方法建模（145）8.2.3算法描述与算法分析（152）8.3基于多边形代数结构的凹多边形Minkowski和计算方法（159）8.3.1平面多边形代数结构（159）8.3.2基于多边形代数结构的凹多边形Minkowski和计算方法建模理论（160）8.3.3算法描述与分析（163）8.4本章小结（166）参考文献（167）第9章基于Minkowski和的飞机大部件自动对接（169）9.1概述（169）9.2自动对接技术设计（170）9.2.1设计简述（170）9.2.2坐标系建立（171）9.2.3构造新的Minkowski和且分类（171）9.2.4原点与Minkowski和的位置关系简述（171）9.2.5准确位置关系的算法描述（172）9.2.6自动对接详细设计（175）9.3机翼自动对接虚拟仿真（177）9.3.1Minkowski和算法实验分析（177）9.3.2OpenGL的框架搭建和环境配置（180）9.3.3三维建模及装配仿真（181）9.4本章小结（188）参考文献（188）0章基于Minkowski和的机械零件自动装配技术研究（190）10.1引言（190）10.2自动装配技术理论基础（191）10.2.1齿轮状凹多面体的凸分解算法（191）10.2.2类齿轮状凹多面体的补形算法（194）10.3基于Minkowski和的零件装配设计（197）10.3.1指导装配理论基础（197）10.3.2装配空间建立（199）10.3.3最小距离矢量算法（201）10.3.4自动装配设计流程（204）10.4零件自动装配虚拟仿真实验（206）10.4.1实验对象简介（206）10.4.2算法实验环境（207）10.4.3仿真数据的精度问题（209）10.4.4装配仿真实验（210）10.5本章小结（216）参考文献（217）