Methods and algorithms for creation of structural schemes of rivers
Authors: Fokin Ivan E. , Krylov Sergey A. 
Published: July 2019

Abstract. Along with other types of schematic maps, structural schemes of hydrographic objects displaying information on the hierarchy of rivers can be important for users. They can be used for water tourism, hydrological research, educational purposes, as well as for solving various analytical problems related to water bodies. Despite the inability to convey the geometric features of the river and the terrain, these schemes differ in a variety of representations. Often, they are created at a certain scale, which allows them to be used to assess and compare the length of rivers, the distances from the mouth of the main river to the mouth of the tributaries, the distances between the tributaries. Depending on the type, they can display hydrological posts, lakes, reservoirs, settlements, tourist sites, etc. Apart from rivers and additional objects labels, it is common to label metric characteristics, for example, the distance from the mouth of the main river to the confluence of tributaries. Unlike, for example, subway maps, structure schemes of rivers are of particular importance not as an independent source of information, but as an additional – it is in combination with other methods of visualization of reference information (maps, diagrams, tables, and text blocks), they are really useful and informative. Currently, to create schemes of hydrographic objects, as a rule, graphic editors are used, due to their wide distribution. This approach is characterized by a low speed of creation, as well as the complexity of updating and supplementing schemes with new information. At the same time, the existing algorithms for automating the construction of schemes are often inappropriate to use for these purposes in our opinion. Since the calculation of the position of the graph elements is made in them based primarily on aesthetic considerations and the length of the edges on the resulting image, respectively, is arbitrary, while the transfer of the length of the rivers at a certain scale significantly expands the list of scenarios for the use of such schemes. In this paper, we consider methods and algorithms for creating structural schemes of hydrography, transmitting part of the metric properties of rivers – primarily their length and the distance of the tributaries from each other along the network lines. On the basis of methods and algorithms, a web service for creating river schemes is developed. The authors propose the following stages of creating structural schemes of hydrography: the choice of the type and purpose of the created structural scheme – the choice of the study area – the choice of the source data – the definition of the main object and the main rivers of the structural scheme – the definition of the main parameters of the scheme – the creation of a derived dataset – the formation of the structural schemes of the river. The first step is to select the type and purpose of the structural scheme to be created. In the course of the study, based on the analysis of existing schemes, as well as the study of the possible use cases, the authors identified following main groups of structural schemes of hydrographic objects and given their brief characteristics: overview schemes (for example, for school atlases), tourist schemes (for planning a route along the river and for navigation along the water route), analytical schemes (for example, for hydrological studies; for visualization of the consequences of river floods; for assessing the quality of surface waters, etc.). The authors have developed the approximate content and design of each of these groups of schemes. Thus, by selecting the type of scheme, the user defines a template, the parameters of which he will specify in the next steps. At the second stage, the choice of the study area is carried out, which allows: to limit the list of possible main objects and main rivers, among which it is necessary to choose, only to those that are at least partially located within this territory; to reduce the number of source data sets by those that belong to the region (for example, contain the object located in this region); enter an additional criterion for the selection of objects – other things being equal, priority will be considered objects located in the territory, less priority – objects located within the buffer zone around the territory and the least priority – objects located outside the buffer zone. The third step defines the data sources that will be used in the construction. To ensure the automation of the process of creating structural schemes, it is proposed to use a cartographic database as the main data source, which is due to the initial composition of the database (hydrography, settlements, communication routes and borders), the developed system of classification and coding of geographic objects, a single fixed format for recording digital cartographic information, as well as the possibility of supplementing semantic information about objects from various sources. Thus, to create schemes on the territory of the Russian Federation, it is advisable to use a small-scale cartographic database of scale 1 : 2 500 000. As additional sources, open data are used, usually presented in tabular or structured text format, which allows them to be integrated into geographic information systems. The greatest difficulty in the processing and preparation of information is textual data containing descriptions of tourist water routes. At the fourth stage, the main object and the main rivers of the structural scheme are selected. The main object is the object linking together the content of the scheme – a region, a large body of water or a river. For example, the main object might be the sea if the scheme shows the largest rivers flowing into that sea. The main rivers are considered to be of the smallest order, represented in the scheme by a straight line, occupying a central position and directly related to the main object. For the automated construction of structural schemes of the rivers it is necessary to define their main parameters. The authors highlighted the mandatory parameters and their values, set the order of their tasks. There are calculated or specified parameters (scale and format of the scheme), parameters that require the selection of a unique value (orientation of the main river), and parameters that contain a set of values (for example, general geographic or thematic objects displayed on the scheme). Depending on the type of diagram, the values of each parameter may vary. An important step in the development of structural schemes of rivers is the formation of derived datasets for each element of the content involved in the creation of the scheme, by selecting and processing the selected data. For example, the required tributaries of the river network are selected in accordance with specified criteria. At this stage, in order to assess the selection result and to ensure the readability of the created scheme, the graphical load (the area of all the conventional images present on the scheme) and the graphical load coefficient (the ratio of the graphic load to the total area) of the scheme is calculated. To improve the efficiency of evaluation, the calculation of the graphical load is proposed to be done not only for the whole scheme, but also for individual elements of the content, rows and columns of the scheme. At the last stage, the scheme is built using special algorithms. One of these algorithms, for example, is designed to build schemes in which the tributaries are depicted parallel to the main river and connected to it with the help of additional lines. In this way – when the images of all rivers are parallel to each other – the task of constructing a graph of rivers for the scheme is reduced to the choice of row for each river (between the lines of the standard distance), in which its image is placed entirely without breaks. The construction begins with the inflow of the main river nearest to the source, the image of which is placed in the first line. Then, for each subsequent inflow, an estimate is made – whether it fits entirely in the same line: if yes, it is depicted there, if not, the next line is evaluated, and so on, until a suitable one is found. On the basis of these steps, it is possible to automate the creation of various river schemes (the potential of which, despite their current relative unpopularity, is quite high). The possibility and benefits of using the developed methods and algorithms to create schematic maps of other objects (not hydrographic) have yet to be investigated.