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.     

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.     

基于块段模型的三维GIS混合数据结构模型研究*

为了有效地表示三维GIS空间实体,在地质块段模型的基础上,提出了基于八叉树和四面体格网的混合数据结构模型(block octree tetrahedron,BOT模型).采用BOT模型生成算法对块段模型进行重新分割,八叉树作整体描述,四面体格网作局部精确描述,并以不同的灰度值表示不同的单元块属性.同时,为节省存储空间,提出了线性BOT编码技术.实验结果表明,BOT模型充分发挥了八叉树和四面体格网的优点,可以在不增加存储空间的前提下实现对三维目标更高效、更精确的表达.     

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

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

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三角剖分结果正确,鲁棒性明显增强,并与理论分析一致,验证了改进算法的正确性和有效性．     

基于物理的波浪实时模拟方法

为解决广域范围内波浪状态的实时计算和可视化问题,结合无粘滞流体力学的物理模型,提出了一种以三角形为控制单元的有限体积简化算法。该算法的优点在于：以不规则边界区域的非规则三角网格为基础,通过简化通量向量分裂方法获得三角形控制单元的边界数值通量,能快速逼近二维浅水方程的解进而模拟非规则边界浅水的实时流动。实验结果显示,所提方法能在符合现实世界物理规律的前提下较好地实现大规模波浪的实时可视化模拟。     

基于Delaunay三角剖分的有向传感器网络覆盖增强算法*

针对视频传感器网络的区域覆盖问题,提出一种基于Delaunay三角剖分思想的几何算法,选取围绕传感器的具有最大面积的Delaunay三角形重心作为决策方向。在此基础上,将Delaunay三角剖分的几何方法与分布式贪婪算法进行了融合,引入“贡献率”概念反映节点在其候选方向上可能覆盖区域的大小,以解决冗余覆盖的问题。仿真结果证明了该算法的有效性。     

Delaunay三角网动态更新算法的研究进展

通过对Delaunay三角网动态更新算法进行研究,综述了Delaunay三角网中插入和删除点、约束线算法以往研究.详细介绍点定位、LOP优化、对角线交换等关键技术的研究进展,并对比各种方法的优缺点,分析已解决的问题和仍存在的问题.最后对更新算法研究不足之处进行总结,并提出若干可能的研究方向.     

摄影测量中一种非编码点的自动匹配方法

在极限约束法基础上提出了一种非编码点匹配的改进算法,首先采用极限约束法得到候选匹配对应点,然后按编码点位置将图像Delaunay三角化,缩小匹配范用。在对应Delaunay三角形内确定匹配点,若在三角形范围内仍不能唯一的确定匹配点,则通过交比不变性来实现对应点的匹配。本方法不限制标志点的粘贴位置,满足摄影测量中实际应用要求。