On sorting triangles in a delaunay tessellation

In a two-dimensional Delaunay-triangulated domain, there exists a partial ordering of the triangles (with respect to a vertex) that is consistent with the two-dimensional visibility of the triangles from that vertex. An equivalent statement is that a polygon that is star-shaped with respect to a given vertex can be extended, one triangle at a time, until it includes the entire domain. Arbitrary planar triangulations do not possess this useful property which allows incremental processing of the triangles.This work was partially supported by the National Science Foundation's US-Italy Collaborative Research Program under Grant INT-8714578 and Information, Robotics, and Intelligent Research Grant IRI-8704781.     

Applications of the discrete element method in mechanical engineering

Compared to other fields of engineering, in mechanical engineering, the Discrete Element Method (DEM) is not yet a well known method. Nevertheless, there is a variety of simulation problems where the method has obvious advantages due to its meshless nature. For problems where several free bodies can collide and break after having been largely deformed, the DEM is the method of choice. Neighborhood search and collision detection between bodies as well as the separation of large solids into smaller particles are naturally incorporated in the method. The main DEM algorithm consists of a relatively simple loop that basically contains the three substeps contact detection, force computation and integration. However, there exists a large variety of different algorithms to choose the substeps to compose the optimal method for a given problem. In this contribution, we describe the dynamics of particle systems together with appropriate numerical integration schemes and give an overview over different types of particle interactions that can be composed to adapt the method to fit to a given simulation problem. Surface triangulations are used to model complicated, non-convex bodies in contact with particle systems. The capabilities of the method are finally demonstrated by means of application examples. Commemorative Contribution.     

Mesh data structure selection for mesh generation and FEA applications

The data structure representing a mesh and the operators to create and query such a database play a crucial role in the performance of mesh generation and FE analysis applications. The design of such a database must balance the conflicting requirements of compactness and computational efficiency. In this article, 10 different mesh representations are reviewed for linear tetrahedral and hexahedral meshes. A methodology for calculating the storage and computational costs of mesh representations is presented and the 10 data structures are analysed. Also, a system for ranking different data structures based on their computational and storage costs is devised and the various mesh representations are ranked according to this measure. Copyright © 2002 John Wiley & Sons, Ltd.     

《周培德三角剖分不是最小权三角剖分》一文商榷——反例不成立

周培协三角剖分是否能得到最小权三角剖分，周培德在《周培德三角部分不是最小权三角剖分》一文撰写之前已有新的结论，本文还指出《周培德三角剖分不是最小权三角剖分》一文所举反例不成立。     

A faster divide-and-conquer algorithm for constructing delaunay triangulations

An easily implemented modification to the divide-and-conquer algorithm for computing the Delaunay triangulation ofn sites in the plane is presented. The change reduces its (n logn) expected running time toO(n log logn) for a large class of distributions that includes the uniform distribution in the unit square. Experimental evidence presented demonstrates that the modified algorithm performs very well forn2¹⁶, the range of the experiments. It is conjectured that the average number of edges it creates—a good measure of its efficiency—is no more than twice optimal forn less than seven trillion. The improvement is shown to extend to the computation of the Delaunay triangulation in theL _p metric for 1<p.This research was supported by National Science Foundation Grants DCR-8352081 and DCR-8416190.     

逆向工程中带孔洞的曲面对象三角剖分法研究

在分析现有的一些三角剖分方法的基础上，提出一种新的基于边界扩展的3D三角剖分方法，该方法首先采用一种空间栅格装点法来进行初始点云数据精简；再构造种子三角形，通过连接已剖分网格区域的边界边与最优扩展点来形成三角形网格从而向外扩展。该法可以对带有内孔等其他非凸壳的复杂曲面对象点云直接进行三角剖分，无需人工分区。实际应用表明采用该法可以快速、有效地从三维数据点集建立几何模型。     

二维有限元自适应网格规划生成

在设计基准点、沿指定曲线等网格加密生成方式的基础上，根据二维区域几何特征和分析对象物理特性估计，通过选择合适的网格加密生成方式，作用于分析对象上，规划构造有限元自适应网格单元尺寸信息场，进而提出基于Delaunay部分的动态节点一单元一体化算法，实现几何特征和物理特性整体自适应的有限元网格自动生成。算例表明此方法可生成高质量、符合分析要求的有限元自适应网格。     

基于GP2Y0A02距离测量的仿真与辅助设计

为了实现非接触距离测量,利用多个仿真与设计软件设计了采用GP2Y0A02模块的距离光学测试系统。在PROTEUS中测量GP2Y0A02电压值,并在Matlab中采用多元线性回归建立GP2Y0A02电压与距离的拟合曲线,最后在开发的测量程序中利用拟合曲线求解得到距离量。测试结果表明,对于非线性位置测量采用适当数据处理方法能得到满意的测量精度。     

A geometric solution to the largest-free-sphere problem in zeolite frameworks

We have applied Delaunay triangulation to models of the known zeolite frameworks. We show that this well-established technique from computational geometry provides for each framework; (i) the location and shape of the open pores and channels, (ii) the diameter of the largest possible included sphere, and indirectly (iii) the diameter of the largest-free-sphere that can diffuse through the framework by at least one lattice translation. Since Delaunay triangulation naturally locates the empty spaces within a set of points, it provides a powerful computer-automated tool for determining the physical characteristics of pores and channels of zeolite frameworks. Such tools will further enhance the usefulness of large databases of hypothetical framework materials.

Here, we tabulate results for the 165 zeolite frameworks that are presently listed in the Atlas of Zeolite Frameworks. Of the known zeolites, refined as pure silicates, the largest included sphere occurs in the TSC framework, with a diameter of 16.39 Å. The largest-free-sphere has a diameter of 11.33 Å, for diffusion along the [0 0 1] direction in the VFI framework.     

改进Delaunay三角剖分算法

针对传统Delaunay算法对非凸三维曲面剖分结果不理想,提出了基于凸划分的改进Delaunay三角剖分算法．研究了复杂曲面剖分的特性,定义了非凸集合凸划分定理,对任意曲面相对投影平面进行划分．利用一组正交平面对任意复杂曲面的划分,通过变换域对曲面进行了Delaunay三角剖分．实验结果表明,改进算法能够在正交平面对头面数据集合进行正确凸划分,在投影平面改进Delaunay三角剖分结果正确,鲁棒性明显增强,并与理论分析一致,验证了改进算法的正确性和有效性．