Delaunay triangulation and 3D adaptive mesh generation

Delaunay triangulation and its complementary structure the Voronoi polyhedra form two of the most fundamental constructs of computational geometry. Delaunay triangulation offers an efficient method for generating high-quality triangulations. However, the generation of Delaunay triangulations in 3D with Watson's algorithm, leads to the appearance of silver tetrahedra, in a relatively large percentage. A different method for generating high-quality tetrahedralizations, based on Delaunay triangulation and not presenting the problem of sliver tetrahedra, is presented. The method consists in a tetrahedra division procedure and an efficient method for optimizing tetrahedral meshes, based on the application of a set of topological Delaunay transformations for tetrahedra and a technique for node repositioning. The method is robust and can be applied to arbitrary unstructured tetrahedral meshes, having as a result the generation of high-quality adaptive meshes with varying density, totally eliminating the appearance of sliver elements. In this way it offers a convenient and highly flexible algorithm for implementation in a general purpose 3D adaptive finite element analysis system. Applications to various engineering problems are presented     

Kinetic collision detection between two simple polygons

We design a kinetic data structure for detecting collisions between two simple polygons in motion. In order to do so, we create a planar subdivision of the free space between the two polygons, called the external relative geodesic triangulation, which certifies their disjointness. We show how this subdivision can be maintained as a kinetic data structure when the polygons are moving, and analyze its performance in the kinetic setting.     

A time-of-scan laser triangulation technique for distance measurements

This paper reports the development of an electro-optic device for relative distance measurement. The time-of-scan triangulation technique has been used as measurement principle and a rotating mirror employed as beam deflection system. A calibration technique is needed to calculate the geometrical parameters of the system. The device has an accuracy of 100 μm, a working distance of 20 cm and a range of 10 mm. The accuracy obtained depends on the instability of the rotation speed of the mechanical scanner that affects the measurement of the scanning time.     

N‐flips in even triangulations on the sphere

A triangulation is said to be even if each vertex has even degree. For even triangulations, define the N‐flip and the P2‐flip as two deformations preserving the number of vertices. We shall prove that any two even triangulations on the sphere with the same number of vertices can be transformed into each other by a sequence of N‐ and P2‐flips. © 2005 Wiley Periodicals, Inc. J. Graph Theory     

Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

一种基于光学三角法的形貌测量系统

提出了一种基于光学三角原理的物体形貌测量方法。从理论上推导出了被测点的相对高度与像点距离的线性公式,通过这个公式可以由像点距离计算出被测点的高度。在实际的测量系统中,通过工作台的精确位移和像点的移动距离可标定出线性公式中的未知系数。把被测物体放在工作台上,先测出被测点的像的相对位移,然后再通过公式计算出被测点相对屏幕的距离。试验中测量了一个圆柱体上的一些点的三维坐标,通过这些数据绘出了圆柱体的三维形貌。     

一种离散点插值算法用于重建光谱反射率

提出了一种用离散点插值算法来重建光谱反射率的方法。首先建立数字相机响应值与典型反射样品表面光谱反射率之间的查找表,然后进行Delaullay分区、提取和插值,最后通过数字相机的输出数据来准确地重建物体表面的光谱反射率。实验结果表明,该方法能够重建典型反射样品的光谱反射率,能够实时获取被摄场景的多光谱图像,易于硬件的实现。     

一种标定三角测量法激光位移计的方法

三角测量的原理公式中因变量、自变量及系统结构参数之间具有非线性关系，并且这些系统结构参数在工程上难以精确测量，因此激光位移计的标定变得很困难。本文通过设置辅助变量及组合参数，使变量之间关系线性化，然后采用最小二乘法拟合出组合参数的准确值，实现激光位移计的准确标定。在此过程中对自变量的测量值做适量修正，可部分消除光学系统畸变对组合参数拟合结果的影响，减小拟合残差。本文给出了用该方法标定激光位移计的实验结果     

基于非结构自适应网格的复合有限体积法

利用文献[1]中将Lax-Wendroff格式和Lax-Friedrichs格式整体复合作用构成二维无结构网格上的复合型有限体积法,同时利用Delaunay方法,根据流场流动特性变化的梯度值为指示器对网格进行加密和粗化,实现自适应,并将此方法应用到二维浅水波方程的求解上,进行了二维部分溃坝,倾斜水跃的数值实验.结果表明,该方法是一个计算稳定、能适应复杂的求解域、能很好地捕捉激波、且计算速度快的算法.