平面域任意散乱点自动三角化的研究

基于平面区域内散乱点的Ｄｅｌａｕｎａｙ三角剖分准则,本文提出一种适用于平面区域内任意散乱点的通用三角化算法。文中详述了三角化的具体实现过程和在三角化过程中可能出现的各种“接触”情况,给出了程序流程图。最后给出实例并把此种方法成功地运用到三维光学数字成像系统。     

二维约束点集Delaunay三角剖分算法研究

在已有算法基础上，提出了任意二维约束点集Delaunay三角剖分的新算法，算法仅在局部产生少量新点，并在局部对三角剖分进行修改，便可保证整体三角剖分符合Delaunay性质。     

面向四面体网格生成的曲面Delaunay三角化算法

提出了一种曲面域Delaunay三角网格的直接构造算法。该算法在曲面网格剖分的边界递归算法和限定Delaunay四面体化算法的基础上,利用曲面采样点集的空间Delaunay四面体网格来辅助曲面三角网格的生成,曲面上的三角网格根据最小空球最小准则由辅助四面体网格中选取,每个三角形都满足三维Delaunay空球准则,网格质量有保证,并且极大的方便了进一步的曲面边界限定下的Delaunay四面体化的进行。     

基于Voronoi最小邻近点集的Delaunay三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay三角化生成算法,该算法以Delaunay三角形及其对偶Voronoi图的局部性特征为基础,通过在局部搜索最小Voronoi邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用领域。     

二维域的有限三角剖分

本文提出了一种适用于多连通的多边形区域的三角剖分和非爱的受限数据的三角剖分算法。该算法简单、直观，采用翼边型数据结构，用Ｄｅｌａｕｎａｙ剖分方法实现。     

二维域的有限三角剖分

本文提出了一种适用于多连通的多边形区域的三角剖分和非连通的受限数据的三角剖分算法。该算法简洁、直观，采用翼边型数据结构，用Ｄｅｌａｕｎａｙ剖分方法实现。     

三维点集Delaunay三角剖分的自动生成与修改算法

本文在已有算法的基础上，提出了一个三维点集Ｄｅｌａｕｎａｙ三角剖分的自动生成及其修改算法。自动生成算法对点在空间的位置没有任何限制，修改算法充分利用已完成的计算量，当动态增加或减少一点时，仅在局部进行适当的调整即可保证整体三角剖分符合Ｄｅ－ｌａｕｎａｙ性质。文中给出了算法正确性的证明。     

AutoCAD中基于超图约束驱动参数化设计的实现

使用超图表示约束模型,采用基于超图约束驱动的几何推理约束满足法进行参数化设计,几何实体的计算基于特征点。作者结合在AutoCAD上开发参数化设计模块的实践,得出该方法能处理多实体约束关系(如面积约束),提高求解效率,降低时间复杂度。     

AutoCAD 中基于超图约束驱动参数化设计的实现

 使用超图表示约束模型,采用基于超图约束驱动的几何推理约束满足法进行参数化设计,几何实体的计算基于特征点。作者结合在ＡｕｔｏＣＡＤ上开发参数化设计模块的实践,得出该方法能处理多实体约束关系（如面积约束）,提高求解效率,降低时间复杂度。     

一种利用Delaunay三角剖分的碰撞检测算法

虚拟现实中物体对象分布及运动情况呈现复杂多样,碰撞检测算法很难达到实时性和准确性的要求.提出了一种基于Delaunay三角剖分的多物体碰撞检测实时算法.该算法运用包围体紧密拟合物体对象,以包围体的中心构建离散数据点集,生成Delaunay三角网格,实施碰撞检测,避免层次包围盒和空间划分的不利因素,物体的更新等操作限定在局部的三角形内.实验表明在多物体的碰撞检测中,即使存在若干移动物体,算法能够满足实时性和准确性的要求.     

ASPECTS OF 2-D DELAUNAY MESH GENERATION

This paper aims to outline the different phases necessary to implement a Delaunay-type automatic mesh generator. First, it summarizes this method and then describes a variant which is numerically robust by mentioning at the same time the problems to solve and the different solutions possible. The Delaunay insertion process by itself, the boundary integrity problem, the way to create the field points as well as the optimization procedures are discussed. The two-dimensional situation is described fully and possible extensions to the three-dimensional case are briefly indicated. © 1997 by John Wiley & Sons, Ltd.     

USING LONGEST-SIDE BISECTION TECHNIQUES FOR THE AUTOMATIC REFINEMENT OF DELAUNAY TRIANGULATIONS

In this paper we discuss, study and compare two linear algorithms for the triangulation refinement problem: the known longest-side (triangle bisection) refinement algorithm, as well as a new algorithm that uses longest side bisection techniques for refining Delaunay triangulations. We show that the automatic point insertion criterion, taken from the fractal property of optimal (linear) longest-side bisection algorithms, assures the construction of good quality Delaunay triangulations in linear time. Numerical evidence, showing that the practical behaviour of the new algorithm is in complete agreement with the theory, is included. © 1997 by John Wiley & Sons, Ltd.     

任意多边形边界内散乱点的三角划分

本文提出了一种简洁通用、用于处理平面上任意多边形内不规则分布点的三角划分算法，并给出了该算法在离散数据参数Ｂｅｚｉｅｒ三角曲面造型中的应用。     

散乱数据点三角剖分方法综述

构造散乱数据插值曲面首先必须对散乱数据点实行三角剖分。本文简要阐述三角剖分的基本概念。并按优化准则将现有的各种三角剖分方法进行分类比较,为建立更好的凸域三角剖分算法提供依据,并为解决复杂多边形区域散乱数据点三角剖分奠定基础。     

OPTIMAL DELAUNAY POINT INSERTION

An efficient algorithm for Delaunay triangulation of a given set of points in d dimensions is presented. Various steps of the point insertion algorithm are reviewed and many acceleration procedures are implemented to speed up the triangulation process. New features include the search for a neighbouring point by a layering scheme, locating the containing simplex by a random walk, formulas of important geometrical quantities of a new simplex based on those of an old one, a novel approach in establishing the adjacency relationship using connection matrices. The resulting scheme seems to be one of the fastest triangulation algorithms known, which enables us to generate tetrahedra in ℝ³ with a linear generation rate of 15 000 tetrahedra per second for randomly generated points on an HP 735 workstation.     

UNSTRUCTURED GRID GENERATION AND A SIMPLE TRIANGULATION ALGORITHM FOR ARBITRARY 2-D GEOMETRIES USING OBJECT ORIENTED PROGRAMMING

This paper describes the logic of a dynamic algorithm for a general 2D Delaunay triangulation of arbitrarily prescribed interior and boundary nodes. The complexity of the geometry is completely arbitrary. The scheme is free of specific restrictions on the input of the geometrical data. The scheme generates triangles whose associated circumcircles contain no nodal points except their vertices. There is no predefined limit for the number of points and the boundaries. The direction of generation of the triangles cannot be determined a priori as opposed to the moving front techniques. An automatic node placement scheme reflecting the initial boundary point spacings is used. The successive refinement scheme results in such a point distribution that the triangulation algorithm need not perform any geometric intersection check for overlapped triangles and penetrated boundaries. Further computational saving is provided by using a special binary tree (ADT) in which the points are ordered such that contiguous points in the list are neighbours in physical space. The method consists of a set of simple rules to understand. The dynamic nature of the Object Oriented Programming (OOP) of the algorithms provides efficient memory management on the insertion, deletion and searching processes. The computational effort bears a linear relation-ship between the CPU time and the total number of nodes. Some of the existing methods in the literature regarding triangular mesh generation are discussed in context. © 1997 by John Wiley & Sons, Ltd.     

裁剪曲面的三角化及图形显示

结合自主版权的超人ＣＡＤ／ＣＡＭ系统的开发，本文提出了一种适合于裁剪曲面图形显示的曲面三角化算法，该算法将曲面的三角化转化为曲面参数域的三角化，并将二维图形的集合运算与Ｄｅｌａｕｎａｙ三角剖分应有和于曲面参数域边界的处理，从而使裁剪曲面在边界上的三角形分布均匀。