地理信息系统文献翻译——摘要

重构一组采样点的几何图形，常用的方法是使用三角网连接这些点并找到它们的凸壳。在本次研究中，解决复杂问题时Delaunay三角网算法在重构三维几何图形中的使用远大于在二维中的使用。当我们不想在连接点上添加任何约束时，Delaunay三角网就特别适用。此外，Delaunay三角网还有一些特性，如最佳性跟唯一性。

背景介绍

在1990年初，三维GIS的发展已经是空间信息科学中最富动态性的领域之一。这种早期工作，对三维栅格（基于长方形跟像素）的可视化和分析以及矢量折线在三维空间中的索引产生了有效的技术。然而，相比之下，将离散点插值成连贯稳健的模型在抽象、结构复杂的地形领域还是主要的未解决问题。

本文研究扩展从二维到三维的基于三角网的的插值方法，使用混合的执行机制，以优化性能，讨论地学插值的特殊要求，因为他们影响到三角网的创建。

三维Delaunay三角网的算法跟程序

Voronoi图

一个连接点的问题的系统的方法，可以追溯到1850年，Dirichlet提出了一个将给定区域细分成一套组多边形域的方法。给出在平面T中的两点Pi、PJ，根据线段PiPj的中垂线将平面T分为两个区域，平面Vi与平面Vj。平面Vi包含所有最接近pi的点;如果我们有更多的点，我们可以很容易地扩展这个概念说，Vi是被分配给Pi的区域，所以vi中的每一个点比其它点更接近pi。

空间的细分由不同的点确定，以便每个点根空间区域较近的点相关联，这样的细分叫狄利克雷镶嵌。

这个过程适用于生成独特的凸多边形集合的闭合区域，这种覆盖整个区域的凸多边形集合叫做Voronoi区域。这个定义可以扩展到高维的地方，例如在三维空间，Voronoi区域是凸多面体。如果我们连接共享一个的Voronoi区域的边界所有成对的点，我们得到了一个包含这些点的凸三角网这个三角网就是。Delaunay三角网。图就是Voronoi区域和Delaunay三角网之间的关系在二维空间的一个例子。1、同样，我们可以得到更高的层面三角网。例如，在三维空间，如果我们连接在Voronoi图中共享一个面的点对，就形成了一个四面体，填补整个区域。......

Abstract

A common method for the reconstruction of a geometric figure given a set of sample points is the use of a triangulation algorithm to connect the points and find the convex hull. In this research, Delaunay triangulation procedures have been used in the reconstruction of 3D geometric figures where the complexity of the problem is much greater than the 2D case. The use of Delaunay triangulations is particularly suited when we do not want to force any constraints on the set of points to be connected. Besides, Delaunay triangulations have some interesting properties as optimal equiangularity and uniqueness (2D).

Introduction and context

During the early 1990's one of the most dynamic fields in spatial information science has been the development of three dimensional GIS [RAP89] [RAP 91]. This early work has generated effective techniques for the visualisation and analysis of three dimensional rasters (based on cuboids or voxels) and for the indexing of vector polylines in three dimensional space [TUR91]. However, by contrast, the interpolation of sparse point datasets into coherent and robust models in unseen, structurally complex geoscientific domains remains a central and largely unsolved problem [RAP 95].

This paper reports research into methods of extending triangulation-based interpolation methods from two to three dimensions, suggests hybrid implementation mechanisms to optimise performance and discusses the particular requirements of geoscientific interpolation as they affect the triangulation procedure.

Algorithms and procedures for 3D Delaunay triangulation

Voronoi diagrams

A systematic approach to the problem ......