EGIS (1994), copyright EGIS Foundation.
The initial purpose is to provide dynamic terrain modeling: it has induced us to develop a general and universal simulation model built on the definition of synchronous processes working in a quasi-parallel model.
This simulation integration is realized on a terrain model, which is structured, on an object oriented basis, unrestricted, portable and not depending of the hardware.
The detailed study of several processes allows to consider all data which can be generated or extracted from the model itself. More especially, by extracting one or several resulting graphs from Digital and Topological Terrain Model graphs. The way of obtaining all these Digital and Topological Terrain Model graphs is the main topic of this paper.
From all the combined graphs (of the Digital and Topological Terrain Model) we can get a resulting graph by two methods:
This last one corresponds to the studied automated generation of graphs (working on Digital and Topological Terrain Model), presented here. This generation uses the properties of the Digital and Topological Terrain Model object to locate it in its physical context (spatial position) and structural context (its position in comparison to other objects). In this paper, we successively present: the context of the Digital and Topological Terrain Model, and two kinds of resulting graphs, one dealing with the crests and another dealing with the talwegs.
The simulation modeling, presented in previous works (Hubert 1991) (Hubert 1993), has been defined with an oriented object approach and concerned natural phenomena acting on a terrain area. This paper belongs to this simulation context.
The modelisation concerns phenomena working simultaneously on and in a geographic area and having two fundamental aspects:
[End Page 371]
These synchronous processes work and are defined on the Digital and Topological Terrain Model. Their simulation is obtained by the association of an engine and a Sequencing set. This Sequencing Set contains the activable process chaining according to their activation date, during a time period.
This chaining is dynamic: it depends on the process relationships, which modify themselves their activation date. There is only one active process at a current time in the system, but this inter-action makes dynamic the process chaining. The simulation works in a quasi-parallel mode. The model is general, universal, may be applied to a large natural and anthropic process. In this context, these defined processes can be grouped into different sets. The concerned processes, in this paper, are the processes generating a new state of the Digital and Topological Terrain Model; and in particularly way, those which allow an automatic searching of a graph. It's an automatic increase of the Knowledge Structure, build with the Digital and Topological Terrain Model components.
The propound Digital and Topological Terrain Model is different from other Digital Terrain Model, by the fact that it combines at the Digital Terrain Model metrics a fundamental concept, the Topology. It's built on the Set Theory, and is composed of elements, properties, and relations.
Consequently, the metrics represent a object property; opposite to a common use in many other classical Digital Terrain Model, it isn't the basis of the model.
This Digital and Topological Terrain Model, uses the cartographic form of a geographical area: the graph Theory (Berge 1973) allows to assimilate each theme (Geology, Hydrography, Topography, and Vegetation) as a valued hypergraph. One general theme as the Geology or the Hydrography or the Vegetation: this graph is composed of areas, with boundaries, the arcs, having themselves an initial and a final vertices. The HBDS representation (Bouille 1977) of this valued and oriented graph takes 3 HBDS classes (Area, Vertex, Arc). The graph metric (coordinates of each point of an arc, coordinates of each vertex) is carried by class attributes: it's a property of each class.
The Topology is represented by relationships, being between vertices, arcs, and areas (for instance adjacent area, initial vertex, input arc to a vertex, rigth area..) ..it's materialized by HBDS links between 3 classes. The particular kind of the Topography is described in following paragraph.
The obtained model is the one of polythematic map: it's composed of several superimposed graphs. The picture (Fig 1) is the HBDS representation of the Digital and Topological Terrain Model.
A crest is composed of points having the highest local altitude, allowing the crossing of a side to an other side on the relief. It's a slope variation axis of the relief areas. Then, it concerns the isolines with the highest altitude, called top isolines.
The relief is represented by isolines. In the Digital and Topological Terrain Model, this map is assimilated to an oriented and valued graph. It's composed of two object types: the isoline, and the level or altitude that characterizes it.
[End Page 373]
[End Page 373]
An isoline is a result of the intersection between an isovalue horizontal plane and the relief. Without considering the map boundaries, and limit other cases, an isoline is a closed arc. Its initial vertex is not distinguished of its final vertex: then the obtained graph is composed not of 3 classes but 2 classes only: isoline and level classes (Fig 1).
The Topology is carried by the HBDS links on the isoline class and level class (predecessor isoline, successor isoline, neighbouring isoline, contained isoline). The Topology appears with the dual graph construction of the topographical graph.
The HBDS attributes ((x,y) of intermediary point) represent the metrics.
Each graph with isovalue curves (isopiezes,isoyetes..) follows the same model.
The definition of the crest and its connexion with the Topography allow to following remarks:
This topological limitation enables to obtain the minimum graph of the crest. Afterwards, it's encreased with new arcs, cutting the isolines of the topographical graph. The resulting graph of the crests is composed of 3 sets (arc, area, vertex) in which the areas are not materialized (the arcs of this graph are not boundaries of closed areas).
In each top isoline, it's necessary to compute an arc or a set of arcs representing the crest. This line depends only on the topographical environment. Its plotting and its shape is not random: the crest line represents a ridge of the relief 3D shape. These ridges are output ridge as opposed to input shapes (or concave shape of relief).
The first step consists of recognizing, in the plan representation of these isolines, the geometrical and spatial properties of the relief. The delimitation of isolines areas, where crest arcs can be build, is defined like a recognition of significant shapes in the top isolines. This searching results of specialization of representative points of an isoline. The arcs plotting of the crest starts on remarkable points and is the result of pattern recognition among maximal altitudes concerning the top isoline.
An isoline is a closed arc: its shape is marked out special points: the inflexing points and singular points. These last ones materialize the valley bottom (talweg) or the relief edge. The inflexing point shows a change between a "relief' shape and "talweg" shape" (and its opposite case) (Fig 3).
Two successive inflexing points mark the bounds of an isoline lobe. A singular point characterizes the limit of a lobe. The recognition of the sequence of 2 inflexing points for a
[End Page 374]
[End Page 375]
singular point allows to draw clearly an isoline lobe; especially the isoline lobe concerning a relief.
It's realized by an algorithmic module named "rechebrous" which detects these spatial configurations along run direction on the isoline (here direct sense) (Fig 4).
The "rechebrous" and "recheinflex" modules allow to encrease the knowledge structure of Digital and Topological Terrain Model: there are creation of specific points (on isoline), on HBDS graph structure (Fig 4).
Initialisation of this crest building will be made, only, from singular points to the isoline center.
Particular kinds
When an isoline has a single shape (such as an ellipsoidal or a circular shape) there's not singular and inflexing points). A circular isoline doesn't possess a stretch axis: its crest can't be determined. A isoline with ellipsoidal shape has a barycenter. Its stretch axis will be the axis linking 2 far points and the barycenter. These 2 points are the most removed from the barycenter. This resulting axis is assimilated to a arc of crest, concerning this top isoline.
The singular points, located on the top isoline, are points where a crest line goes to stop. This topological property gives us the general principle of crest building:
- Each singular point is an origin point (initial vertex of a future arc of the crest), where a pattern is established following the highest altitude (greater or equal z isoline) (Fig 3).
Making an arc from an origin point
This searching is realized step by step: a fictitious observant, put on an origin point ro, looks at the directions of 8 "cardinal" points around it (4 cardinal points senso stricto plus 4 cardinal intermediary points). He can progress only one step (given intervalle dx,dy). According to a maximal altitude criterion (and other constraints), he must choose one of the 8 points. His new position will become the new current position seat for following iterations : he draws his way along a line of highest altitude, making an arc of the graph. He will stop when he meets a top isoline bound or a multiple point of the crest (Fig 3).
Obtaining 8 "cardinal" points: La Porte interpolation
8 "cardinal" points limit a mesh of a net, which is built progressively during each iteration. Its beginning is a original point ro. A dx variation, dy variation and the first point ro on the isoline, define this net.
The current position is the center of a mesh. Each mesh point has a (xp,yp) coordinates computed with dx and dy intervals. An interpolation method, La Porte solution (La Porte-Vignes 1974), is used to compute zp altitude for each mesh p point. This algorithm named interxy() uses a landmarks number, surrounding the unknown point (interpolate point). These landmarks must be distributed uniformly. Consequently we superimpose a grid to the graph of the Topography (each side of mesh is any cm for a map at 1/50000 scale). Around the interpolate point, the meshes cover different sides of the hill: this recovered area supplies a good sample of points, used to interxy0. These points are intermediary points of each isoline, cutting by these meshes. Successive matrixes, containing 9 points and surrounding the current point (pc), are computed at every iteration (the mesh side is less or equal 1 cm).
[End Page 376]
[End Page 377]
Choosing the highest direction
Selecting a new current position (pc), during the advancing is made according several criteria:
Elaboration of the graph of the crest
The building of n first arcs (according the principle in previous paragraph ) has its origin on n singular points, respectively. When an i arc among these n arcs, built in parallel walking, meets a multiple point, this one becomes a final vertex of i arc. This building of each one of n arcs, stops respectively, upon the n multiple points met. These n multiple points bounds a d area belonging to the top isoline. Each multiple point is taken as the origin of a new walking; this searching way retakes the same computation than previous one working from singular points. Finally, this searching stops when the d area is enough little for the highest point becoming its barycenter.
The computed graph is composed of 3 classes: Arc, Vertex, Area (Fig 11. It has following properties:
This extensive graph gives us few interesting topological elements.
A talweg is the most large slope axis, in a valley. With elementary talwegs, we obtain a network.
To recognize a talweg, it's necessary, in first, to identify a valley (on the relief) and secondly the most large slope axis.
The lobes, concerning valley shapes for a isoline, are obtained easily with the 2 modules, "rechebrous", "recheinflex", used to build the graph of the crests.
[End Page 378]
The automatic searching of talwegs uses the recognition of shapes of isolines. The singular points carry an attribute, "relief type"; if a point is the most distant point of a valley, this attribute is false. If lobe represents an edge of relief, then this attribute is true. An isoline is characterized by a set of singular points (valley type).
To obtain an arc of a talweg, we draw successively elementary segments linking 2 singular points, belonging respectively to 2 successor isolines. This drawing follows the dual graph of the Topography.
The algorithm of lobe recognition applied to top isolines, must be generalized to the set of isolines. The important number of iterations allows to integrate a vectorial compute mode (SIMD mode). This searching must consider every remarks:
A light inflexing shape in a isoline, mustn't be identified as a talweg. The talweg recognition uses a threshold, defined from a triangle, linking the 2 inflexing points (bounds of lobe) and the singular point. This triangle is adjusted on the singular point and must have a height greater than the threshold.
It build on the fact that the most large slope axis is given by the minimal distance between 2 points belonging to 2 successor isolines. Each isoline has specific points (valley type). For each valley point of each top isoline, we give a talweg arc. And linking at this point, the arc is generated following the valley points with a successor topological relationship. It depends on the smallest distance criterion. When 2 valleys points arrive on a same point, this one becomes their final vertex. The searching stops when there is no successor isoline.
The talweg network is assimilated to a graph, composed of arcs and vertices. It is included to Digital and Topological Terrain Model. It's linked to the Topography by the fact that each talweg point belongs to an isoline. The topological properties of the topographical graph helps to build this graph (Fig 1).
[End Page 379]
This study only concerns a topographical graph, composed of directed isolines: it means that these isolines limit a hill. The basin (or crater ) kinds must consider the isolines with a opposite direction (the isoline direction is an attribute of HBDS class "isolines"). The searching area isn't the top isoline but is the area delimited by the top isolines pair. One of this isoline pair is the top direct isoline, the other one is the top isoline with a opposite direction. These 2 top isolines have the same level. The search must be reconsidered according to other criteria. The crest and talweg automatic searching induces an increase of the knowledge structure of the Digital and Topological Terrain Model; it's a consequence of the Digital and Topological Terrain Model topological properties and its metrics. A topological model alone reduces the searching area of a crest line. A Digital Terrain Modeling (raster type) can't detect the top areas in the map: there is any object identifiable in comparison with other elementary objects; its structure is too poor. ( the elementary cell isn't an adapted object). Consequently in a Digital Terrain Model, all areas of the Digital Terrain Model (all nets) are been considered for computing the crest graph or the talweg graph.
This searching shows the problem of that one extract of map representing (vector mode), and what is the meaning of this map ? The answer is to find again the properties of its building. It's the recognition of 3D shape in a 2D representation. The crest obtention is fundamental; but the interpolation methode (Laporte algorithm based on hyperbolic parabolic) used is not the topic center. The interpolation results are satisfying, and we didn't do a comparative study or find a new interpolation. This study is a recognition of properties and shapes on a map represented by its graph.
This search doesn't allow only a direct application to drainage basin, but also the comparison between the graph of the talweg and the one of the hydrography. This last one is a restriction of the graph of the talwegs (thus a subgraph). The graph of crests is relevant to a particular case of the search of the axis of the isolines surrounding the different local top, whatever their altitude may be. This axis corresponds to upper ridge of the 3D unit area, modeled by a graph of isovalues (such as water table..). It may be applied in an enlarged context to other graphs. This study concerns several themes which must be integrated into environmental surveying systems, with an important part to play in a general GIS.
ARQUES, F., JANEY, N. (1992), Modelisation des cartes planaires pour la synthese d'images de reliefs montagneux. MICAD, Actes de la l leme conference, pp. 247-262. BATTON-HUBERT, M. (1993), Expert system managing a large set of discrete processes for 3D cartography and mapping. EUROCARTO XI, Proceedings pp. 67-77
BERGE, C. (1973) Graphes et hypergraphes. Dunod universite (ed), Paris.
BERSTEL, J., PIN, JE., POCCHIOLA M. (1991), Mathematiques et informatique.Tome 2 Combinatoire et arithmetique, McGRAW-Hill(ed), Paris.
BOUILLE, F (1977), Un modele universel de banque de donnes simultanement partageable, portable, et repartie. These de Doctorat d'Etat. Universite Paris 6, 550p.
[End Page 381]
BOUILLE, F. (1977), Apport des graphes et hypergraphes en informatique cartographique, Publication de la Commission 3 du Comite Francais de cartographie, 12p.
BOUILLE, F. (1982), Actual tools for Cartography Today, Cartographica N.2, pp.27-32 DAVIS, C. (1982), Etude algorithmique de structures de donnees topologiques en cartographie polythematique. Introduction a 1'algorithmetrie, These de Doctorat d'Etat, universite Paris 6, 385 p.
HUBERT, M. (1991), 4D Topological terrain modeling with discrete simulation applyed to impact surveying. GIS IGU Conference, Brno, 17p.
HUBERT, M. (1993), Integration d'une simulation spatio-temporelle a un Modele Topologique et Numerique de Terrain These de I'Universite Paris 6, 78lp.
LA PORTE, M., VIGNES,J. (1974), Algorithmes numeriques.Analyse et mise en oeuvre. Editions Technip. Tome 1. Arithmetique des ordinateurs; Systemes lineaires.
LA PORTE, M., VIGNES,J. (1974), Algorithmes numeriques.Analyse et mise en oeuvre. Editions Technip. Tome 2, Equations et systemes non lineaires.
ROUDIER P. (1993), Synthese des paysages realistes par simulation de processus d'erosioy These de l'Ecole Nationale Superieure des Mines de Saint -Etienne et de I'Universite J. Monnet.
[End Page 381]