Скачать 47.99 Kb.

Tao Wang Chinese Academy of Surveying and Mapping Beitaipinglu 16, Haidian, Beijing, China, 100039 wangtao@casm.ac.cn Abstract Contour line is a basic method for representing terrain. It has advantages over elevation Grid and TIN on that a group of contour lines can visually convey quantity attributes and undulation information of land surface at the same time. Readers of contour map can capture interested terrain information on global structures and local attributes of landscape efficiently and further manage engineering problems. This characteristic can be utilized to benefit digital terrain analysis, in which most functions depend on Grid and TIN and can barely acquire information adapted to variant scales. However, few numerical models exist which can efficiently acquire full information conveyed by contour lines. Experienced readers can virtually construct a mentally continuous surface from a group of nested contour lines. And high level information is derived from the virtual surface. Researchers recognized that the spatial (neighboring) relation between contour lines is a vital factor for the mental process. Therefore spatial relation need be extracted from contour map. The spatial relation of contour lines is different from that of other geographic features. Contour tree has been investigated by researchers and is used for recording contour lines’ spatial relation. However information managed by contour tree is not enough for terrain analysis based on contour lines. The direction of contour line is important because it can help distinguish interior and exterior of region bounded by it. Then with elevation label of contour lines descending direction of region between two neighboring contour lines can be determined. Direction is an indispensable ingredient of spatial relation of contour lines. There is adjacent relation between two neighboring contour lines, which exists over entire map. We propose that location, elevation and adjacent relation information are primary elements of contour lines’ spatial information for digital terrain analysis based on contour. Locally directional adjacency is employed for extending information recorded in contour tree to a full explanation of semantics of contour lines’ spatial relation. In this new model spatial relation of two adjacent contour lines can be classified according to geometric relation, elevation ordinal relation and direction of contour lines, which can facilitate digital terrain analysis of contour. To a contour map, this new model can differentiate seven configurations between contour lines. When one contour line is enclosed by another and both are clockwise or anticlockwise, they represent one local landform object and have different elevation values. And if one is clockwise and another is anticlockwise, they represent a craterlike landform and have equal elevation value. When two adjacent contour lines do not contain each other, they are on two neighboring local landform objects. They may be two pits or peaks or may be one pit and one peak. In order to extend local information to entire map, five properties are deduced from definition of directional adjacency to facilitate analyzing functions on contour lines and help on forming continuous surface of terrain. The basis of them is the consistency of contour lines’ direction on elevation dimension and the clearly distinction of spatial relation between contours. Further more quantitative properties are defined based previous research using Delaunay TIN on contour lines. The proposed directional adjacent relation of contour lines can help distinguish all configurations of contour lines. This new model and properties enrich contents of contour tree. It is especially advantageous in terrain analysis of landforms of planetary as moon or Mars on which craters spread everywhere. 1 Introduction Terrain is a fundamental factor in various research and engineering problems as hydrology, biology and meteorology (Moore etc, 1991). Contour, Regular Grid and TIN are three basic models representing digital terrain. Terrain contour lines are intersections of terrain surface and geographic planar surfaces of different elevations, on which every points have equal elevation. As 1dimensional curves, contour lines represent the 3dimensional landscape on the 2dimensional space. A group of contour lines bear abundant information on global and local terrain features because they are adaptive to undulation of terrain surface. Clarke etc (1982) believed that contour is a selective, aggressive, random elevation sampling scheme for representing terrain. Quantitative value, such as elevation, slope, aspect, surface curvature and drainage area can be extracted from adjacent contour lines. Object information (Moore etc, 1991), which is vaguer, such as valley, ridge, depression, mountain and structural relation among them can also be derived (Cronin, 1995; Kweon etc, 1994). In research of digital terrain analysis, there are intensive efforts on finding structural information of topography. Surface network (Wolf, 1991; Brandli, 1996) is a most investigated topic by researchers in order to address abstract representation of terrain, and most of the work is based on Regular Grid DEM (Rana, 2004). Kulik and Egenhofer (2003) designed a qualitative language to describe specific features based on horizons of terrain silhouette. However there are few research efforts on numerical models based on contour lines. A general GIS database stores location and elevation label for a contour line and uses it mainly for visualization and as data source of Grid and TIN DEM. A lot of terrain analyzing functions does not rely on contour line because it is hard to automatically construct a continuous surface which is visually obvious for human being (Mark, 1997; Cronin, 2000). However, contour lines have advantages over Grid and TIN DEM if contour lines’ spatial relation and nesting information, which make it an objectoriented model, can be provided. The spatial relation of contour lines is different from that of other geographic feature, which is built up on relation between geometric elements (Egenhofer and Franzosa, 1991). When contour lines are taken as 1dimensional closed curves, the topological relation can only be ‘disjoint’ from the pointset based spatial relation model. If intercontour regions bounded by adjacent contour lines are considered, the relation includes ‘contain’ and ‘disjoint’. Variation of elevation of adjacent contour lines has been noticed by researchers for a long time and contour tree (Morse, 1969) has being used for recording the special spatial relation, which accommodates geometric and ordinal relation. Contour lines and intercontour region are represented by nodes and edges of contour tree, whose root is the lowest contour lines or lowest intercontour region. There are three types of algorithms for constructing contour tree: mathematical morphologicbased, polygoninpolygon test based and TIN (or Voronoi) based (Roubal and Poiker, 1985; Kweon and Kanade, 1995; Cronin, 2000; Wang, 2004; Chen, Qiao and etc, 2004). The work is concentrated on finding enclosure or adjacent relation between contour lines. However, information on spatial relation between contour lines recorded in contour tree cannot be distinguished completely. When one contour line is enclosed by another on map, the spatial relation of them can be varied according to elevation values of them. But the enclosed one can only be denoted as a branch node of another in contour tree. This paper investigates the formalization of semantics of contour lines’ spatial relation and analyzing the spatial configuration of different relation according to both geometric and numeric of contour lines. 2 Directional Adjacency of Contour Lines Morse (1969) defined adjacent contour lines on a contour map which has not degenerate situation (without cliff or overlapping of other geographic features and annotations): “Two contour lines are said to be adjacent if a line can be drawn that connects the two contour lines and intersects no other contour lines.” Morse also noticed that the set of adjacent contour lines of a given contour line can be divided into two subsets: the left set and the right set. In the contour map showed in Figure 1, a is spatially adjacent to b and c and not to e and d. But according to Morse’s definition, each contour line in Figure 1 is adjacent to any others, even they are not geometrically adjacent. Fig. 1. Adjacency of contour lines. Previous works on constructing contour tree are all follow Morse’s definition implicitly although few mention this in publications. However, most existing algorithm trying to find adjacency information, whether based on mathematical morphologic operators or polygoninpolygon test, did not extract full set adjacent relation. Wang (2004) and Chen etc (2004) discussed the strategy for deriving all adjacent contour lines based on those acquired by directly searching, but the two subsets and semantics of different configuration are not distinguished further. In a real contour map, the configuration of contour lines can be very strange, especially at landscape of Karst or Loess. The enclosure relation at saddle area is complicated and it is hard to find enclosure information when boundary of map sheet may break one contour line into several parts. In this situation, refined adjacent relation is helpful for digital terrain analysis. Fig. 2. Elevation and geometric direction of contour lines. In order to accommodate situation of contour lines at terrace, Morse (1969) defined that when one traverses from one node to successive node on a contour line, if the left side is higher and right is lower, then this contour line is in positive direction. In this way, interior and exterior of region bounded by a contour line can be distinguished. And further, the closed curves of contour lines representing pit is geometrically clockwise and those representing peak is geometrically anticlockwise on the 2dimensional plane, as indicated in figure 2. Now contour line has an attribute of directionality, which can be represent by the orientation of contour lines. Digital computational model can find more meaningful information when all contour lines are in consistent direction. Wang (2004) designed an algorithm for adjusting direction of contour lines into positive. Assume all contour lines in a given map are processed by this algorithm and given two contour lines c_{1} with elevation H(c_{1}) and c_{2} with elevation H(c_{2}). The elevation interval is dH (there may be more than one dH value in one contour map, but it does not have any effects on directional adjacency). The definition of adjacent contour line of Morse is followed. If two contour lines c_{1} and c_{2} are adjacent, we denote it as: N_{Φ}(c_{1})=c_{2} and N_{Φ}(c_{2})=c_{1}. In order to determine positive direction of a contour line, we must convert Morse’s theoretical definition to one which can be implemented. Wang (2004) used Delaunay TIN to adjust direction of contour lines and the strategy can be employed to set an equivalent definition. Definition. Positive direction of contour line. In the Delaunay TIN on a contour map in which not all contour lines have same elevation, we can find a triangle whose two vertices v_{a}, v_{b} are on contour line c_{1} and the third v_{q} on is on contour line c_{2}, where v_{b} is a subsequent node of v_{a} on c_{1} and v_{q} is on the right of vector v_{a}v_{b}. If c_{1} is higher than c_{2}, c_{1} is in positive direction. Definition. Positive adjacent contour line. If c_{1} and c_{2} are adjacent contour line and c_{2} is on the left side of c_{1}, c_{2} is positive adjacent contour line of c_{1}. If H(c_{2})H(c_{1})>0, we denote N_{1}(c_{1})= c_{2} If H(c_{2})H(c_{1})=0, we denote N_{+0}(c_{1})= c_{2} Definition. Negative adjacent contour line. If c_{1} and c_{2} are adjacent contour line and c_{2} is on the right side of c_{1}, c_{2} is negative adjacent contour line of c_{1}. If H(c_{2})H(c_{1})<0, we denote N_{1}(c_{1})= c_{2} If H(c_{2})H(c_{1})=0, we denote N_{0}(c_{1})= c_{2} Definition. Directional adjacency. For two given contour lines c_{1} and c_{2}, directional adjacency is denoted as: N_{k}(c_{1}, c_{2})=1, k = 1, 1, +0, 0, Φ where k is called order of directional adjacency. Further, a contour line is zeroorder adjacent to itself: N_{+0}(c_{1}, c_{1}) = N_{0}(c_{1}, c_{1}) =1 3 Spatial Configurations of Directional Adjacency For convenience, we define a modular function M(•) to distinguish different set of contour lines. M(N_{+0})=M(N_{0})=0 M(N_{1})= M(N_{1})=1 M(N_{Φ})= Φ When M(N_{k})=p (p=0, 1, Φ), the related c_{1} and c_{2} are called porder adjacent contour pair. Specially, c_{1} and c_{2} are not adjacent if p=Φ. We further define sets of contour lines with equal characteristics. Set A_{+}={ c  N_{k}(c_{1}, c)=1, k =1, +0} denotes positive adjacent set of c_{1} Set A_{}={ c  N_{k}(c_{1}, c)=1, k = 1, 0} denotes negative adjacent set of c_{1} Set A_{1}={ c  N_{k}(c_{1}, c)=1, k = 1, 1} denotes 1order adjacent set of c_{1} Set A_{0}={ c  N_{k}(c_{1}, c)=1, k = +0, 0} denotes 0order adjacent set of c_{1} Set A_{Φ}={ c  N_{k}(c_{1}, c)=1, k =Φ} denotes nonadjacent set of c_{1} Set A_{+1}=A_{+}∩A_{1} denotes 1order positive adjacent contour lines of c_{1} Set A_{1}=A_{}∩A_{1} denotes 1order negative adjacent set of c_{1} Set A_{+0}=A_{+}∩A_{0} denotes 0order positive adjacent set of c_{1} Set A_{0}=A_{}∩A_{0} denotes 0order negative adjacent set of c_{1} Set A=A_{+}∪A_{}=A_{1}∪A_{0} = A_{+1}∪A_{1}∪A_{0}∪A_{+0} denotes adjacent set of c_{1} Set C=A∪A_{Φ} denotes full set of contour lines in the given map Table 1. Spatial Configurations of Adjacent Contour Lines
Now spatial relation of two adjacent contour lines can be classified according to geometric relation and elevation ordinal relation. Table 1 indicates that, if two adjacent contour lines have not containing relation as showed in (b), (d), (f) and (h), they are on two neighboring local landforms, pit or peak. And they can be further divided into two types by their elevation ordinal relation. Contour lines in (b) represent two peaks and those in (h) represent two pits. Those in (d) and (f) represent one pit and one peak. Although modular function produces different values, (d) and (f) indicate two equivalent configurations. If one is enclosed by another and both are clockwise or anticlockwise as showed in (a) and (g), they represent one local landform and have different elevation values. And if one is clockwise and another is anticlockwise, they represent a craterlike landform and have equal elevation value. From definition of directional adjacency, the following five properties can be deduced for application in digital terrain analysis. (1) N_{1}(c_{1}, c_{2})=1N_{1}(c_{2}, c_{1})=1, that means, N_{1}(c_{1})=c_{2}N_{1}(c_{2})=c_{1} or vice versa N_{1}(c_{2})=c_{1} N_{1}(c_{1})=c_{2} (2) N_{0}(c_{1}, c_{2})=1N_{0}(c_{2}, c_{1})=1, N_{+0}(c_{1}, c_{2})=1N_{+0}(c_{2}, c_{1})=1, that means, N_{0}(c_{1})=c_{2}(or N_{+0}(c_{1})=c_{2})N_{0}(c_{2})=c_{1}(or N_{+0}(c_{2})=c_{1}) (3) {N_{1}(c_{1}, c_{2})=1 and N_{1}(c_{1}, c_{3})=1}{N_{0}(c_{2}, c_{3})=1, N_{0}(c_{3}, c_{2})=1}, {N_{1}(c_{1}, c_{2})=1 and N_{1}(c_{1}, c_{3})=1}{N_{+0}(c_{2}, c_{3})=1, N_{+0}(c_{3}, c_{2})=1} (4) {N_{+0}(c_{1}, c_{2})=1 and N_{1}(c_{1}, c_{3})=1}{N_{1}(c_{2}, c_{3})=1}, {N_{0}(c_{1}, c_{2})=1 and N_{1}(c_{1}, c_{3})=1}{N_{1}(c_{2}, c_{3})=1} (5) {N_{1}(c_{1}, c_{2})=1 and N_{0}(c_{2}, c_{3})=1}{N_{1}(c_{1}, c_{3})=1}, {N_{1}(c_{1}, c_{2})=1 and N_{+0}(c_{2}, c_{3})=1}{N_{1}(c_{1}, c_{3})=1}, that means, for contour lines c_{1}, c_{2} and c_{3}, if N_{1}(c_{1})=c_{2}, N_{0}(c_{2})=c_{3}, then N_{1}(c_{1})=c_{3}; if N_{1}(c_{1})=c_{2}, N_{+0}(c_{2})=c_{3}, then N_{1}(c_{1})=c_{3}. In figure 1, if N_{1}(a)=b, N_{0}(b)=e, then N_{1}(a)=e. These properties, which extend local information to global, can facilitate analyzing functions on contour lines and help on forming continuous surface of terrain. The basis of them is the consistency of contour lines’ direction on elevation dimension and the clearly distinction of spatial relation between contours. 4 Quantitative Aspects of Directional Adjacency Above sections defined directional adjacency and its properties mostly from qualitative aspects. However digital terrain analysis needs quantitative properties and results. We designed an algorithm for extracting adjacent relation based on Delaunay TIN and defined Valid Node (Wang, 2004). Here more quantitative properties are defined or revised. One edge in TIN is an auxiliary edge if its two end nodes are located on two contour lines. Definition. Strong Valid Node. If there is an auxiliary edge whose one node P_{1} is on contour line c_{1} and another on c_{2}, P_{1} is called valid node of c_{2} on c_{1}. Further, if P_{1} is not valid node of any other contour line at the same side of c_{1} with c_{2}, P_{1} is called strong valid node. Definition. Valid Edge. If there are two consecutive nodes on c_{1} and they are valid nodes of c_{2}, the edge bounded by the two nodes is called valid edge. Definition. Weak Valid Node. If a node on c_{1} is not valid node of c_{2} and any other contour line at the same side of c_{1}, it is weak valid node of c_{2} on c_{1}. Definition. Weak Valid Part. If there are consecutive weak valid nodes of c_{2} on c_{1} which are bounded by two strong valid nodes of c_{2} on c_{1}, the part of c_{1} which starts from first strong valid node to next one and passes all weak valid nodes is weak valid part of c_{2} on c_{1}. Definition. Degree of Adjacency. For two given contour lines c_{1} with length l and c_{2}, if the length of all valid edges and valid parts of c_{2} on c_{1} is l_{v}, degree of adjacency of c_{1} to c_{2} is: D(c_{1}, c_{2})= l_{v} / l And similarly define degree of adjacency of c_{2} to c_{1} is D(c_{2}, c_{1}). Then degree of adjacency of c_{1} and c_{2} is: D_{c1c2 }= Max(D(c_{1}, c_{2}), D(c_{2}, c_{1})) Value D_{c1c2} varies from 0 to 1. If N_{Φ}(c_{1}, c_{2})=1, D_{ c1c2} = 0. For two adjacent contour lines which are not geometrically proximal, their degree of adjacency can be computed when deriving full set of directional adjacent relation by properties of last section. 5 Conclusions We extend our previous research and propose that directional adjacent relation of contour lines can help distinguishing every configuration of contour lines. The properties are also analyzed to facilitate further applications. This new model enriches meaning of contour tree. Test work has been implemented and showed more robustness in automatic labeling of real contour map. The direction on elevation dimension is also employed in contour threading from regular elevation grid matrix and produce encouraging result on efficiency (Wang, 2006). Future work based on directional adjacency can investigate more quantitative properties in geometric and elevation ordinal aspects. These could help digital terrain analysis such as automatic reasoning, terrain feature extracting and landform classification. Distinct semantics of spatial relations of contour lines is also advantageous in terrain analysis of landforms of planetary as moon or Mars on which craters with variant sizes spread everywhere. References
