# Computational geometry and GIS for digital terrain modeling

Cheikh.A.T.C Ndiaye, Ndeye Fatou Ngom, Niang Oumar

<figure><img src="image_1.png" /></figure>

## To cite this version:

Cheikh.A.T.C Ndiaye, Ndeye Fatou Ngom, Niang Oumar. Computational geometry and GIS for digital terrain modeling. 2016. hal-01311145

HAL Id: hal-01311145

https://hal.science/hal-01311145

Preprint submitted on 3 May 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Computational geometry and GIS for digital terrain modeling

Cheikh H. T. Chérif Ndiaye* — Ndèye Fatou Ngom** — Oumar Niang***

**RÉSUMÉ.** Les systèmes d’information géographiques (SIG) et la géométrie algorithmique sont à l’originique de beaucoup de problèmes associés à la représentation géométrique. Parmi ces problèmes figurent le besoin d’avoir un maillage qui permet d’améliorer le calcul de l’écoulement hydrologique sur la surface et les modèles numériques de terrain. La triangulation de Delaunay est un outil efficace à cause de ces propriétés intrinsèques (topologiques, géométriques et morphologiques) qui sont prises en compte lors de la construction du maillage afin d’aboutir à une représentation plus réaliste et à la réduction du coup de calcul pour évaluer le flux aux bords. Dans ce travail, nous présentons d’abord quelques problématiques liées à la géométrie algorithmique et au GIS et ensuite nous proposons un modèle de description urbaine pour la simulation d’inondation intégrant un modèle numérique de terrain basé sur la triangulation de Delaunay et un modèle de batiments.

**ABSTRACT.** Geographic Information System (GIS) and computational geometry are source for many geometric issues. Among issues addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. Delaunay triangulation emerges to be an efficient tool because of its useful properties: realistic physical representation taking into account topological, geometrical and morphometric properties; the flux across any edge with its neighbors is always normal to its boundary by definition and thus reduces the computational cost to evaluate flux across the volume boundary. In this paper, issues concerning GIS and computational geometry is first presented. Then, we propose an application for urban modeling integrating terrain modeling based on Delaunay triangulation that can be used as support for flood simulation and building modeling.

**MOTS-CLÉS** : Géométrie algorithmique, triangulation de delaunay, modélisation urbaine, modélisation numérique de terrain, simulation d’écoulement

**KEYWORDS** : computational geometry, delaunay triangulation, urban modeling, digital terrain model, flood simulation.

<footnote>* Mathematic and computer science department / LACGAA laboratory / LTISI laboratory
Cheikh Anta Diop University of Dakar, Dakar, SENEGAL
riffondiaye@gmail.com</footnote>

<footnote>** Computer and telecommunications department / LTISI laboratory
Polytechnic school of Thiès, SENEGAL
ndefangom@gmail.com, fngom@ept.sn</footnote>

<footnote>*** Computer and telecommunications department / LTISI laboratory
Polytechnic school of Thiès, SENEGAL
niangom@yahoo.fr, oniang@ept.sn</footnote>
# 1. Introduction

Geographic information Science (GIS) is a multi-disciplinary area with contributions mainly coming from the spatial sciences (geodesy, geography, cartography), computer science (databases, artificial intelligence and computational geometry) and applied science (spatial planning, archeology, geology, civil engineering and biology). Thus, a substantial part of all activities performed by a GIS involves computing with the geometric data (such as location, shape, proximity, and spatial distribution) which calls for efficient methods to store, manipulate, analyze, and display such amounts of data [6]. In the past, the importance of the data geometric aspects was often underestimated and the proposed solutions often suffered from lack of foundations, both from a geometric point of view (e.g the result of an operation defined just as the output of a certain algorithm) and from a computer science perspective [18]. The needs for a solid theoretical background and for high performance reasoning make the field of GIS an interesting source of problems to work on for computational geometers. Computational geometry is about the design and analysis of algorithms for geometric problems. The success of the field as research discipline can on the one hand be explained from the beauty of the problems studied and the solutions obtained, and on the other hand, by the many application domains (computer graphics, geographic information system, vision, path planning, image processing) where geometric algorithms play a fundamental role [7].

This paper first reviews issues concerning GIS and computational geometry in order to improve the understanding of the diversity of the possible interactions between computational geometry and GIS and application to terrain modeling and simulation. Indeed, real time hydrological processes simulation relies on spatial distribution representing discretization of representative terrain maps. Triangular network is typically the basis of such discretization. Thus some preprocessing become relevant, before running any simulation on the discretized space, to get a more realistic physical representation taking into account topological, geometrical and morphometric properties. Among other issues to be addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. The issues related with GIS and computational geometry is presented. The aim is to improve the understanding of the diversity of the possible interactions of the two fields. Then we project application for urban modeling. This application includes three main processing stages. The first stage deals with the construction of a geometric terrain representation based on Delaunay Triangulation. In this stage, theoretical background for flood simulation based on the Delaunay decomposition is proposed. The second stage copes with the urban area modeling including a step of building modeling process.

Section 2 discusses geographic information systems issues. Section 3 presents computational geometry tools that can be used in GIS. Section 4 introduces techniques and tools to generate digital terrain model based on irregular triangular networks. We propose a method of generating DTM based on Delaunay triangulation and java graphics 3d libraries. Section 5 proposes a coupled hydrological and digital elevation model for flood simulation. Conceptual principles and schematic processing steps are given. Section 6 presents
an urban model integrating the creation of building which has impact on the water flow. Conclusion and futures works are given in section 7.

## 2. GEOGRAPHY INFORMATION SYSTEM (GIS)

A geographic information system (GIS) can be seen as a system of hardware, software and procedures designed to support the capture, management, analysis, modeling and display of spatially referenced data for solving complex planning and management problems. The main issues addressed are related to geometric primitive, data models and terrain analysis.

### 1) Geometrics primitives

Terrain modeling never ceased to evolve gradually with the development of representation techniques. Indeed, construction of terrain involves conversion among geometrics primitives such as points, lines, triangular surfaces and parametric curve and surface. The resulting parametric surfaces allows modeling complicated objects. There are two types of curves and surfaces

- Interpolating curves and surfaces, including all points of controls in the curve (curve Catmull-Rom and Coons surfaces) [18].

- Curves and surfaces approximation: that does not necessarily pass by all points of controls but rather close to them (Bezier, B-Splines, β-Splines) [18].

Illustrations of parametric curves and surfaces are given by Figure 1 and Figure 2.

### 2) Cubic parametric curves

A cubic parametric curve is defined by,

$$Q(t) = (x(t), y(t), z(t)), t \in \mathbb{R} \qquad [1]$$

$$x(t) = a_x t^3 + b_x t^2 + c_x t + d_x$$

$$y(t) = a_y t^3 + b_y t^2 + c_y t + d_y$$

$$z(t) = a_z t^3 + b_z t^2 + c_z t + d_z$$

If t belong to [0.0, 1.0], then

$$Q(t) = (x(t), y(t), z(t)) = T.C \text{ where } C = \begin{pmatrix} a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z \\ d_x & d_y & d_z \end{pmatrix} \text{ and } T = (t^3, t^2, t, 1)$$

[2]

The matrix C can be transformed into a matrix M called basic matrix and a column vector G of four geometrics constraints called vector geometry [18].
$$Q(t) = (x(t), y(t), z(t)) = T.C = T.M.G = (t^3, t^2, t, 1) \begin{pmatrix} m_{11} & m_{12} & m_{13} & m_{14} \\ m_{21} & m_{22} & m_{23} & m_{24} \\ m_{31} & m_{32} & m_{33} & m_{34} \\ m_{41} & m_{42} & m_{43} & m_{44} \end{pmatrix} \begin{pmatrix} g_1 x & g_1 y & g_1 z \\ g_2 x & g_2 y & g_2 z \\ g_3 x & g_3 y & g_3 z \\ g_4 x & g_4 y & g_4 z \end{pmatrix} [3]$$

<figure><img src="image_3.png" /><figcaption>Figure 1. Example of parametric curves [24]</figcaption></figure>

### 3) Cubic parametric surfaces

The cubic parametric surfaces are generalization of cubic parametric curves. They are defined from a set of control points which is called mesh tiles or patches [24]. Parametric surface is defined by the following equation, $t \in [0, 1]$

$$Q(t) = \text{S.M.G}(t) \text{ where } G(t) = \begin{pmatrix} G_1(t) \\ G_2(t) \\ G_3(t) \\ G_4(t) \end{pmatrix} [4]$$

The $G_i$ are cubic and are defined as follow

$$G_i(t) = (T.M'.P_i) \text{ with } P_i = (P_{i1}, P_{i2}, P_{i3}, P_{i4})^T$$

As each $P_{ij}$ is a control point of $G_i(t)$, then

$$Q(s,t) = \text{S.M.G}(t) = \text{S.M.} \begin{pmatrix} P_{11} & P_{12} & P_{13} & P_{14} \\ P_{21} & P_{22} & P_{23} & P_{24} \\ P_{31} & P_{32} & P_{33} & P_{34} \\ P_{41} & P_{42} & P_{43} & P_{44} \end{pmatrix} [5]$$

Figure 2 illustrates an example of Bezier surface computed from a set of control points. Figure 3 shows the smooth appearance of different representation of the surface. However, real terrain is far having a smooth and polished appearance and the necessary calculation time which appears to be relatively high.

### 4) Data models and structures

There are basically three ways to store data: raster model, vector model and digital elevation model. The raster representation is a space oriented representation: the domain is
<figure><img src="image_4.png" /><figcaption>Figure 2. Bezier surface computed from control points [24]</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3. Different representations of Bezier surfaces [24]</figcaption></figure>
subdivided in atomic regions similar to the pixels in digital image. Raster model provides direct information about a given location. However, besides their size raster structure has the disadvantage of providing an approximate geometry, whose accuracy is dependent on the resolution of the grid.

In vector model, points are stored with their coordinates according to some reference system, line segments by their two end points, and regions are defined by their bounding line segments. When incidence relations between points, segments, and regions are stored explicitly, we speak of a topological data structure. Raster model are more suitable to support queries by location while vector models are more suitable to support queries by content. Thus, hybrid representations, such as digital elevation model (DEM), are more generally adopted. DEM includes the raster-based elevation matrix, and the vector-based isoline model and triangulated irregular network (Figure 4). The elevation matrix is a two-dimensional array of square cells, each cell storing a height value or elevation. The isoline model is a way to represent and visualize a real-valued function defined over the plane. The triangulated irregular network is a subdivision of the plane in non-uniform triangles. Indeed, in relatively flat areas we can do with a small number of large triangles, while smaller triangles are used in areas with a lot of variation in height.

<figure><img src="image_6.png" /><figcaption>**Figure 4.** An elevation matrix, isoline model, and TIN for the same source data [6]</figcaption></figure>

### 5) Terrain analysis

Topographic features are special points, lines and region that have a special meaning for describing the shape and the topologies of the terrain [21]. They correspond to local differential properties of the ground. In the case of TIN, point and linear features are vertices and chain of edges in the underlying triangulations; areal features are connected collection of triangles defining convex, concave and flat regions. Terrain analysis includes several geometric operations such as topological features extraction at resolution variable on the domain and computation of path on a surface. Rendering processes are based on realistic visualization and compression techniques. Defining a global reference system, terrain visibility and converting among different representation are challenges of primary interest in geographic data processing and require computation geometry tools.
<figure><img src="image_7.png" /><figcaption>Figure 5. Topographical features classifications [21]</figcaption></figure>

### 3. III. COMPUTATIONAL GEOMETRY IN GIS

Computational geometry occurs in all stages of the GIS data cycle. Geometric algorithms are useful in data correction (after data acquisition and input), in data retrieval (through queries), data analysis (like map overlay and geostatistics), and data visualization (for maps and animations). For instance, line segment intersection by plane sweep solves map overlay, Voronoi diagrams are helpful in neighborhood analysis, Delaunay triangulations are widely used for terrain modeling, and geometric data structures help with efficient spatial indexing in large spatial data sets [4]. Such problems are closely related to various well-known GIS operations like map overlay, buffer computation map generalization and spatio-temporal data mining and range searching.

#### 3.1. Digital elevation model

Digital elevation modeling deals with generating a model for a terrain in a GIS that is realistic. The model is built on an initial data set which can consist of points with elevations or digitized contour lines with elevations. Generating a terrain that fits with the input data, the high-level information is a problem where several conflicting criteria have to be taken into account. The modeling problem and corresponding algorithms are a continuing direction of future research that has hardly been addressed from the computational geometry perspective [4]. However, in the cases of TIN, Delaunay triangulation, which is optimal according the minimum angle, is more widely used.

#### 3.2. Delaunay triangulation

From irregularly distributed data, either a regular grid or an irregular triangular network can be formed [9,17]. There are three basic requirements for TIN formation : for a given set of data points, the resulting TIN should be unique if the same algorithm is used. The geometric shapes of resultant triangles are optimum (each triangle is nearly equilateral) ; each triangle is formed with nearest neighbor points, that is, the sum of the three edges of the triangle is minimum [9]. In all the possible alternatives, Delaunay triangulation is the one most widely used because it satisfies all three requirements.

A Delaunay triangulation is a set of linked but non overlapping triangles uniquely defined if the points are in general position : no two points are identical, no three points lie on a common line, no four points lie in the same plane and no five points lie in the same
sphere. The circumscribing circle of each triangle would not include any other points. As the Delaunay triangulation is a dual diagram of the Voronoi diagram (Figure 6), the Delaunay triangulation network can be formed either directly by algorithm or indirectly through the Voronoi diagram which is much easier in raster mode. The resulting triangulation network is independent of the starting point. Therefore, the selection of a starting point is only for the convenience of algorithm implementation. Delaunay's constraint on the mesh selects for nearly equilateral triangles, which evenly distribute the feature bias. TINs' vertices are derived from the features of the reference image, regardless of those features' positions. If we compare grid-based heightmaps to TINs at various resolutions, we would observe that the grid of the first heightmap grows and shrinks around a point of origin, while the TIN's mesh is anchored to the most important features of the reference image. Thus, TINs consistently represent multiple features of the terrain, while grid heightmaps can only consistently represent a feature if it lies at the grid's point of origin.

<figure><img src="image_8.png" /><figcaption>**Figure 6.** Set of points (top), Voronoi diagram (right), Delaunay circle (left), Delaunay triangulation of the point</figcaption></figure>

# 4. COMPUTING THE GEOMETRIC TERRAIN MODEL

Modern acquisition techniques provide huge dataset that permit to represent terrain accurately. However, high representation accuracy is paid in terms of high costs for storage and processing. So there must be a trading between the representation cost and accuracy. In this section we present a method of computing Triangular Irregular Network (TIN).

## 4.1. Computation of the Delaunay triangulation

Delaunay triangulation can be found in either dynamic or static mode. Static triangulation means that the triangulation network that has already been constructed will not be altered by adding new points in the formation process. In contrast, with a dynamic trian-
gulation, the network already constructed will be changed if a new point is added, so as to meet the Delaunay circumcircle principle.

### 4.1.1. Materials

We tested the triangulation with Java using a Window 7 environment. The program has been written in java but can be easily transferred in Java Applet so it can run in the internet. The real time rendering of the digital terrain model require Java 3D library. The Java3D library uses OpenGL or Direct3D operating software library to create the necessary algorithms to set up the 3D virtual universe.

### 4.1.2. Computation of the DTM based on TIN

The geometric terrain model is based on TIN computed from Delaunay triangulation algorithm.

**- Algorithms for computing the Delaunay triangulation**

There are mainly four algorithms for computing the Delaunay triangulation : Incremental, Gift Wrap, divide and Conquer and QuickHull [4,9]. In this paper, the incremental algorithm and the Quickhull algorithm were used to compute respectively the 2D and 3D Delaunay triangulation. The incremental algorithm work as follow : to insert a new site, we walk across the triangulation, starting from the most recently created triangle, until we find the triangle that contains the new site. This triangle and any adjacent triangles that contain this new site in their circumcircle are eliminated and the resulting empty spot is re-triangulated. The expected time to insert a new site is roughly $O(n^{1/2})$ where n is the current number of sites [20]. The *Quickhull* algorithm finds a point on the hull, then repeatedly looks for the next point until it returns to the start [19]. The algorithm has $O(n \log(n))$ complexity. The data input is a text file containing points with x, y and z coordinates. The incremental algorithm is less time consuming but is difficult to generalize in 3D. That's why we chose the *QuickHull* algorithm for computing the 3D triangulation. However, there should be noted that by fixing the z coordinate, the *QuickHull* algorithm can also be used to compute 2D triangulation. The output of the *Delaunay triangulations* is a set of vertices and faces, printed in files that can be easily rendered.

**- Implementation and visualization**

Even if many implementations of Delaunay triangulation have been proposed, to the best of our knowledge many of them suffer of platform dependencies and none is able to handle dynamic Delaunay triangulation as robust as it should be. In this paper, the implementation has been done in Java so as to have full control of the transformations on the model. To render 3D model using Java3D requires the construction of the Scene Graph to implement its 3D graphical operations. The Scene Graph of our application is divided in two main branches or Branchgroup. The diagram of Figure 7 outlines the position of each Java3D variable within the Scene Graph.

The platform enables the visualization of the digital terrain as set of points or as a triangulated surface that can be associated with weight (Figure 7, Figure 8). As Java3D has been used for the implementation, there is also possibility to look the surface from different point view through an interaction with the keyboard or the mouse. Besides, the program can be easily transferred in Java Applet application so it can be run on the internet.
<figure><img src="image_9.png" /><figcaption>Figure 7. scene describing the structure of the program</figcaption></figure>

# 5. FIRST STEPS TOWARDS FLOOD SIMULATION

Real time flood simulation relies on spatial distribution representing discretization of representative terrain maps. Among other issues to be addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. The model described here is based on the model presented by [22] resumed by Figure 9. The processes considered are overland flow, subsurface flow, evaporation and infiltration.

## 5.1. Domain decomposition

DT is a realistic physical representation taking into account topological, geometrical and morphometric properties. Besides, the flux across any edge with its neighbor is always normal to its boundary by definition and thus reduces the computational cost to evaluate flux across the volume boundary. In the model, Delaunay triangulation is used to represent the watershed terrain and incorporate watershed boundaries, the stream network, soil type, geology, elevation contours or other feature particular to the domain. Starting points for the watershed domain start from a set of user defined control points : hydrographic points and critical terrain points (maximum or minimum of local surface, convexity or concavity).

## 5.2. Governing Hydorlogical processes equations

The governing equations are local system of ODEs representing multiple hydrological processes (Figure 6) within triangle or element i including

<figure><img src="image_10.png" /><figcaption>Figure 8. Triangulation of complex contour structure</figcaption></figure>
– Surface overland flow :

$$
\frac{\delta h}{\delta t} = P_0 - I - E_0 - Q_{oc} + \sum_{j=1}^{3} Q_s [6]
$$

Where h is the local water depth, Qs is surface flow from element i to its neighbor j,
P_o, I and E_0 are precipitation, infiltration and evaporation respectively.

– Subsurface flow :

$$
\left( \frac{d\xi}{dt} = I - q^0 - ET_s \right)_i \left( \frac{d\xi}{dt} = q^0 + \sum_{j=1}^{3} Q_g^{-Q_l+Q_{gc}} \right) [7]
$$

where ξ is unsaturated moisture storage of element I. ξ is saturated moisture storage, q⁰ is unsaturated zone and saturated zone; I and ET are incoming infiltration and outgoing evapotranspiration at land surface respectively; Qs is lateral groundwater flow from element I to its neighbor Ql is vertical leakage through and underlying confining bed; Qgc is discharge/recharge from/to aquifer to/from channel.

One advantage of this study is flexibility in this constitution relationship and there is
no intrinsic limitation to other possible forms or hydrological processes.

6. Urban modeling

In urban modeling, building description is the first step towards the construction of
an efficient representation. Building can be modeling under vector form using primitives
likes planes and straights lines. Indeed planes describe facades or roofs, while the lines
represent the facades or roof edges.

6.1. Building construction

In recent years a new standard CityGML was validate in the worldwide by Open-
Geospatial Consortium [23]. The main purpose is to give norm of building in the urban
environment. It defines many levels of details that explains how the buildings have to be
create. For example, in figure 10, the level of detail 1 (LoD1) represents building with just
extruded polygons (flat roofs), Lod 2 corresponds to detailed roofs and vertical facade
and flat. Lod3 corresponds to more detailed facade, complex roof, all textured. The LoD
4 offers details with an interior modeling. In the our model, The LOD 2 is used during the
process of building modeling.

<figure><img src="image_11.png" /><figcaption>**Figure 9.** Sample of 3D representation of building. Three representations of the same building in different level of details[23].</figcaption></figure>

For the construction of building, we use a 3D modeler called Wings3D [26]. The
procedure is as follow.
initialization : put an image;

**while** image *exists* **do**
  - travel image
  - get contours of all shape in the image
  - clean it to eliminate no significant details of contour (smallest things that have no impact on the simulation)
  - adjust some geometric configurations which can cause mesh damage
  - do an extrusion to get building's shape in three dimensions

**end**

<figure><img src="image_12.png" /><figcaption>**Figure 10.** Input image : 2D perspective view of a scene of urban area[25]</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>**Figure 11.** Contours computed from the 2D input image</figcaption></figure>

The tests of the algorithm have been made with the 2D perspective views of the figure 12 as input image. In the first step, we search the contours of all parts that delimit the different building. Once finished a removal process begin to eliminate no significant contours like illustrated by Figure 13. In the next step, we do an extrusion to all contours found to get the 3D building's shape. The result is illustrated by Figure 14. In the last step, the numerical terrain computed from Delaunay triangulation and the building constructed from a modeler are put in a single scene.
<figure><img src="image_14.png" /><figcaption>**Figure 12.** 3D Building reconstruction from the contour image
**6.2. Towards a model of flood simulation**</figcaption></figure>

The processing steps of the model are resumed by Figure 9. Spatial discretization of the hydrological model coupled with a digital elevation model of surface is first performed. The governing equations of hydrological model are based on a system of ODE (Equation X, Equation Y) extracted from Saint Venant equations. The hydrological model will be integrated using a semi-discrete finite volume method. The finite volume elements are prisms projected from a Delaunay Triangulation based TIN. The model is designed to simulate hydrological processes such as water movement, water quality and sediment transport in surface and subsurface.

<figure><img src="image_15.png" /><figcaption>**Figure 13.** Step processing of the hydrological model based on DT domain decomposition</figcaption></figure>
# 7. Conclusion

In this paper we have first reviewed issues concerning computational geometry and GIS. At the state of the art, computational geometry offers rigorous and powerful tools for solving a variety of geometric problems in GIS. However, a number of problems that could be solved with computational geometry tools remain to be solved. We used java application based on the convex hull algorithm to build triangular irregular network for 2D set of points and 3D set of points. Java 3D graphics package was used to render the three dimensional model of TIN. In the last section, we introduce conceptual principles and steps processing for a hydrological model based on Delaunay triangulation terrain decomposition. We also gives first step for urban area modeling.

Futures works will focus on improving the digital terrain model by providing tools for the user to move through the virtual world, to supply elevation datasets, to drape images over the model, to generate statistics and perform simulation of hydrological processes over the model. After that we will superpose our two model (DTM and building) because our final aim is to create an interactive, real-time three-dimensional terrain model that can be rendered with free 3d graphics libraries, which may be used as a base for digital terrain analysis, natural phenomena real time simulation for decision making.
## 8. Bibliographie

[1] DANIEL SELMAN, « Java 3D programming. Manning publications Co. », 2002.

[2] J.M. WARE, C.B. JONES, G.L. BUNDY, « A triangulated spatial model for cartographic generalization of areal objects. », *In proceedin of COSIT, pages 173-192, 1995*

[3] M. VAN KREVELD, J.E. GOODMANN, J. OROURKE, « Geographic Information Systems. », *Handbook of Discrete and Computational Geometry, chapter 58, pages 12931314*. Chapman Hall/CRC, Boca Raton, 2004.

[4] M. VAN KREVELD, « Digital elevation Models : overview and selected TIN algorithms », *Departement of computer science. Course notes for CISM advanced school on algorithmic foundations of geographical information systems, 1996,*

[5] RENÉ WILLIBORDUS VAN OOSTRUM, « Geometric algorithms for geographic information systems », *PHD university of Nederlands, 1999,*

[6] VAN- OOSTEROM P.J.M, VAN KREVELD M.J., « Geo-information and computational geometry », *Nederlandses Commissie voor Geodesie Netherlands Geodetic Commission Delpft 2006,*

[7] MARK DE BERG, OTFRIED CHEONG, MARK VAN KREVELD, MARK OVERMARS, « Computational Geometry : Algorithms and application », *third edition*. Springer 2008,

[8] G. GRISE, M.M. HERMANN, « Surface reconstruction using Delaunay triangulation for application life sciences. », *Computer Physics communications, vol. 182, pp. 967-977, 2011,*

[9] Z. LI, Q. ZHU, C. GOLD, « Digital terrain modeling : principles and methods. », *CRC PRESS 2005,*

[10] I. V. FLORINSKY, « Digital terrain analysis in soil science and geology. », *Institut of Mathematical Problems of Biology, Russian Academy of Sciences, 2012,*

[11] N.F. NGOM, O. MONGA, M.O.M MAHMOUD, P. GARNIER, « 3D shape extraction segmentation and representation of soil microstructures using generalized cylinders », *J. Computer and Geosciences, vol. 39, pp. 50-63, 2012,*

[12] P. SANZANA, S. JANKOWFSKY, F. BRANGER, I. BRAUD, X. VARGAS, N. HITSCHFELD, J. GIRONAS, « Computer assisted mesh generation based on hydrological response units for distributed hydrological modeling », *J. Computers and Geosciences, vol. 57, pp. 32-43, 2013,*

[13] C. ARICO, M. SINAGRA, L. BEGNUDELLI, T. TUCCIARELLI, « MAST-2D diffusive model for flood prediction on domains with triangular Delaunay unstructured meshes », *J. Advances in Water Resources, vol. 34, pp. 1427-1449, 2011,*

[14] M. COLETTI, « The GeoMason Cookbook », *Department of Computer Science, George Mason University. Zeroth Edition, January 2013,*

[15] S. LUKE, « Multiagent Simulation and the Mason Library », *Department of Computer Science, George Mason University, Manual version 17, May 2013,*

[16] I.V. FLORINSKY, « Digital terrain analysis in soil science and geology », *Academic press, pp. 398, 2012,*

[17] N.F. NGOM, P. GARNIER, O. MONGA, S. PETH, « Extraction of three dimensional pore space from microtomography images using a geometrical approach », *J. Geoderma, 163 (1-2), pp. 127-134, 2011,*

[18] LEILA DE FLORIANI, PAOLA MAGILO, ENRICO PUPPO, « Application of computational geometry to geographic information system. », *Dipartimento di Informatica e Scienze dell'Informazione Universita di Genova, 2010,*

[19] BARBER, DOBKIN, HUHDANPAA, « The Quickhull Algorithm for Convex Hull », *Transactions on Mathematical Software, Vol. 22, No. 4, December 1996,*
[20] PAUL CHEW, « Voronoï diagram and Delaunay triangulation », December 2007.

[21] M. KALBERMATTEN, D. VAN DE VILLE, D. TUIA, D. JOOST « Multiscale analysis of geomorphological and geological features in high resolution digital elevation model using wavelet transform », *Geomorphology* 138 (1) 352-357,

[22] YIZHONG QU, « An integrated hydrologic model for multi-process simulation using semi-discrete finite volume approximation », *PHD. The Pennsylvania State University. 2004,*

[23] MEHDI REZOUG, « MODELISATION ET OPTIMISATION DES INONDATIONS URBAINES AVEC UNE APPROCHE MULTICRITERES », *Doctorat, UNIVERSITÉ DÉVRY VAL DESSONNE, 22 Octobre 2012,*

[24] WAFIA BOUBGUIRA, « Modélisation numérique de terrain : Etude de Synthèse et Application », *Laboratoire de LIRE, 07, Fevrier, 2007,*

[25] WWW.INSERTION-PAYSAGERE.FR, « PC6 vue aérienne aménagement lotissement », *Jason Mc Alpin, 2003,*

[26] JON J. STROTHER, « Wings3D : users reference manual. »,