任意多面体的剖分算法及应用

本文提出了一种将任意多面体剖分为四面体的算法，给出了算法理论基础的证明、算法具体实现步骤及所用数据结构。该算法首先根据多面体类型，查找出符合剖分要求的多面体一个面与一个顶点，构成一个简单多面体，将原多面体剖分为该简单多面体和一个新的多面体，再 对新的多面体重复剖分，直到多面体全部剖分为简单多面体。每个简单多面体进一步剖分为四面体。最后，文章讨论了该算法在机器人碰撞检测中的应用。     

基于成功回路的凹多面体的剖分算法

提出了一种对任意凹多面体不添加顶点的凸剖分方法,该算法首先把凹多面体抽象为无向图,无向图的顶点为多面体的顶点,边为多面体的棱和对角棱,权值为棱或对角棱的长度,然后根据普利姆算法构造最小生成树的思想来构造一个成功回路,利用该回路对多面体进行剖分。重复执行此过程,直到剖分后的所有多面体都是非凹的。该算法能够对多面体进行不添加顶点的剖分,同时可以对任意凹多面体多面体进行剖分,包括含有空洞的凹多面体。     

一种任意多面体剖分成四面体的改进算法

针对原相关算法中存在的不足,提出了凸顶点的凸空间从原多面体中完整剖分出去的充要条件。引入平面切角和空间切角的概念,使剖分思想更加直观、简化。对空间多边形进行Delaunay三角剖分时,充分考虑了凸空间的结构特点,采用了透视投影的思想,使投影后的平面多面形保持了原空间多边形的拓扑结构和顶点的凹凸性,保证了三角剖分的合理性、正确性。基于空间相关性的思想,对凸顶点的邻接点生成有向空间包围盒,快速排除与凸空间不相交的面,加快了多面体剖分的速度;最后给出了改进后的剖分算法,对相关应用有着极大的实用价值。     

基于边/面遮挡关联性的多面体凸剖分方法

提出一种多面体凸剖分的方法,与国际上已有的工作相比,在计算速度、空间需求和新增顶点等方面均降低了复杂度,有大幅的效率提高,且在处理凹边很多的多面体时具有更大的优越性.其工作步骤是根据多面体的面、边沿某些方向正投影时面与面之间、边与边之间的遮挡关系进行局部化操作,以渐进地凸剖分多面体.它对应用中的常见模型表现出的时间复杂度、空间复杂度皆近似为O(n),而新点数不超过O(r n~(0.5)),这里,n为模型的点数,r为凹边数.实验结果表明,与目前国际上常用的"切割分裂"方法相比,新方法的速度提高了14～120倍,空间下降至"切割分裂"方法的1/2.3～1/7.4,而新增加的点数则最多为"切割分裂"方法的1/28,甚至有些情况下无须增加新点就能完成凸剖分.新方法剖分出的凸多面体绝大多数是四面体,多于"切割分裂"方法所得凸多面体数量.但是,很多应用是要求多面体被剖分为四面体的.如果进一步将凸多面体四面体化,则新方法的结果个数将明显少于"切割分裂"方法,因为新方法的剖分过程中所增加的新点要少很多.新方法还能方便地处理包含空洞的多面体,甚至是包含孤立面、孤立边和孤立点的非流形多面体.     

约束四面体剖分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念,在此基础上设计了一种在空间区域上做约束Delaunay四面体剖分的算法。该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分,然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分。利用约束Delaunay四面体剖分算法,该文进一步设计了一种三维物体表面重建算法。     

任意平面多边形顶点凸凹性的快速新算法

给出了一个基于叉积,顶点凸凹性,顺逆性的关系,同时确定ｘｏｙ平面多边形顶点凸凹性和顺逆性的快速新算法,该算法简单,直观,且不需要事先假定顶眯序列的顺逆性,用该算法解决了三维空间平面多边形的顶点凸凹性问题,算法的时间复杂度为ｏ（ｎ）。     

约束四面体部分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念，在此基础上设计了一种在空间区域上约束Delaunay四面体部分的算法，该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分，然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分，利用约束Delaunay四面体剖分算法，该文进一步设计了一种三维物体表面重建算法。     

基于象限划分的简单多边形方向与顶点凸凹性快速判别算法

文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法。通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系：不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由“比较”运算来完成,只有在必要时才运用“乘／除法”运算;算法利用“假设一检测”方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性。文中算法的时间复杂度为O（n）。一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次。     

基于近似最少切割面的凹多面体剖分算法

为了提高凹多面体的剖分效率、减少剖分后增加的顶点数和凹边数,利用回路提出一种对任意的凹多面体不添加任何顶点的有效的凸剖分方法。首先将凹多面体抽象成无向图,然后利用深度优先搜索策略找出由这个无向图的边所组成的最优回路,该回路上的边的个数最少,并且凹边个数多。由该回路上的边组成的一系列切面对凹多面体进行一次切割。该方法可以在对多面体不添加任何顶点的情况下找到近似最好的回路,形成近似最少的切割面,对多面体的切割接近最少,剖分后得到的多面体个数近似最少。     

基于环链的多面体剖分快速算法研究

利用环链提出了一种对任意多面体不添加顶点的凸剖分快速方法 ,它对多面体的剖分个数接近最少 .该方法首先从多面体的棱和对角棱所构成的所有环中 ,以最小周长选取一个最好的环 ,然后利用这个环的各个边所形成的一系列面 ,对多面体进行一次剖分 .实验证明 ,这种方法可找到对多面体不添加顶点剖分的最好剖分面 ,使剖分的次数接近最少 ,具有较好的实用价值和广泛的应用前景 .     

Two Algorithms for Decomposing a Polyhedron into Convex Parts

Two algorithms are presented for splitting a polyhedron into convex components: one for the case of a simple polyhedron and one for a more general case, when the polyhedron may have ring-shaped faces and cavities. The time requirement in both cases is O ( DN log N ), where D is the number of concave dihedral angles and N is the number of edges. The algorithm for the simple oasis produces at most D + 1 convex pieces which is the minimal number of the convex components.     

一种基于加减法求交和顶点类型的凹多边形水平扫描填色算法

本文给出了一种只有加减运算就能求大平线线与凹多边形边界交点的方法,并根据顶点类型定义,将凹多边形顶点分成“水平顶点”、“极占”、“拐点”三类。设计了基于三类顶点的边界存储结构;建立了凹多边形水平扫描填色算法,解决了当交为顶点时可能产生的“交点对”不配对的问题。     

Minimum vertex distance between separable convex polygons

The minimum vertex distance between two separable convex polygons is found by an optimal algorithm which is linear in the number of vertices.     

寻求简单多边形凸壳的线性时间算法

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选，使剩余顶点的角的大小排成递增序，然后用Graham扫描方法删去非凸壳顶点，最后得到多边形凸壳的顶点序列.第二个算法不断删去多边形的凹点及新产生的 凹点，最后得到凸壳顶点序列。这两种算法简单，易于实现，时间复杂性都是O（n)。     

风力机的线性变参数主动容错控制

针对风力机具有非线性和参数的不确定性的特征,提出了基于线性变参数(linear parameter varying,LPV)增益调度的风力机主动容错控制方法,降低故障对机组动态特性的影响.基于LPV凸分解方法,将风力机的非线性模型转化为具有凸多面体结构LPV模型,利用线性矩阵不等式(linear matrix inequalities,LMIs)技术对凸多面体各个顶点分别设计满足性能要求的控制器,再利用各顶点设计的反馈控制器得到具有凸多面体结构LPV容错控制器.仿真结果表明,LPV增益调度技术可以成功地应用于风力机系统的容错控制.     

An Efficient Algorithm for Line Clipping by Convex and Non-convex Polyhedra in E3

A new algorithm for clipping lines against convex polyhedron with O(N) complexity is given with modification for non-convex polyhedron. The suggested algorithm is faster for higher number of facets of the given polyhedron than the traditional Cyrus-Beck's algorithm. Some principal results of comparison of all algorithms are shown and give some ideas how the proposed algorithm could be used effectively.