JP5337995B2 - Watershed extraction program and watershed extraction device - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a computer program for extracting a correct watershed even by a user who does not know the watershed in advance. <P>SOLUTION: The watershed extraction program controls a computer. The computer holds altitude data indicating altitudes of a plurality of areas on a map. The areas include a first area. The watershed extraction program causes a processor of the computer to execute: a first procedure of searching for the watershed of water flowing into the first area to the upstream direction based on the altitude data; and a second procedure of deciding whether the area predetermined in the first procedure is correct or not. In the second procedure, when it is decided that the predetermined watershed is not correct, the watershed extraction program causes the processor to execute the first procedure again. <P>COPYRIGHT: (C)2011,JPO&amp;INPIT

Description

  The present invention relates to a method for extracting a watershed using a computer. In particular, the present invention relates to a computer program (basin extraction program) that uses the positions of one or more points as input data and extracts a basin at each point based on a digital terrain model (digital elevation mode, DEM).

  A basin is important information for civil engineering structures that manage water such as rivers or dams. A basin at a certain point is an area where water gathered at that point has flowed. For the construction of a dam, the amount of water expected to enter the dam on average, that is, the average rainfall in the dam basin is indispensable. In order to manage a dam, it is essential to manage the condition of the water source forest of the dam, that is, the forest in the basin. In order to predict the water level of a river, the expected rainfall in the river basin is indispensable. In designing rainwater drainage (sewage) to protect urban functions from torrential rain, the maximum rainfall intensity and basin area that the facility should handle are essential.

  A basin can be determined by reversing the direction of water flow. Actually, there is a computer program (basin extraction program) for extracting a basin by utilizing the characteristics of this flow. The processing procedure of the main watershed extraction program is detailed in Non-Patent Document 1.

  The electronic data used in the basin extraction program is the elevation data of the ground surface. Such electronic data is called DEM (Digital Elevation Model). In DEM, the ground surface of a certain area is divided into small areas called cells, and an altitude value is given to each cell.

  Usually, the direction of water flow coincides with the steepest downward gradient direction at that point. A basin extraction method using this flow property is called a steepest slope method. In this method, a basin of a certain cell is a cell that has passed when the direction of the steepest downward gradient from the cell is reversed. The slope of a cell can be determined from the elevation data of that cell and the 8 cells surrounding that cell.

  In the steepest gradient method, handling of cells having an altitude lower than that of surrounding cells becomes a problem. Such cells are called “flat” or “sink, depression” in the research area of watershed extraction programs. A flat land is a cell having the same elevation as that of one or more surrounding cells, and a depression is a cell having an elevation smaller than the elevations of all surrounding cells. When such a cell exists, a correct watershed cannot be extracted by using the steepest gradient method. However, there are many flats and depressions in a normal DEM. Therefore, a correct watershed cannot be extracted only by the steepest gradient method.

  FIG. 18 is a diagram for explaining a depression. A graph 1800 is a diagram in which the water flow direction determined by the steepest gradient method is superimposed on the vertical cross-sectional view of the DEM. Cell 1801 is an estuary and has the lowest elevation. Cell 1804 is slightly lower in elevation than adjacent cells (1803 and 1805). The direction of water flow determined by the steepest gradient method is indicated by an arrow. The basin cell of the cell 1801 is a range obtained by tracing this arrow in reverse from the cell 1801 and becomes cells 1802 to 1803. But this result is incorrect. If it is an expert, the basin cell of the cell 1801 will be the cells 1802-1809.

  The most common solution to this problem is the sink filling method, which ignores the gradient and determines the direction of water flow based on the altitude placement. The depression filling method uses altitude data of more cells than the steepest gradient method. Non-Patent Document 2 and Non-Patent Document 3 explain in detail the watershed extraction program that uses the depression filling method.

  In the depression filling method, the depression is first changed to a flat ground. That is, the altitude of the depression is set to the minimum elevation among the surrounding cells. In FIG. 18, the altitude of the depression cell 1804 is set to be the same as that of the cell 1805. Next, the outlet of the flat ground is determined. Specifically, a cell having an altitude lower than that of the flat land adjacent to the flat land is determined as the outlet. If there is no outlet, expand the cell to level.

  In FIG. 18, there is no outlet for cells 1804 and 1805. Therefore, the cells to be flattened are expanded from cells 1803 to 1805. A state after the expansion is shown in a graph 1820.

  Cells 1821-1829 of graph 1820 correspond to cells 1801-1809 of graph 1800, respectively.

  Referring to graph 1820, it can be seen that the elevations of cells 1823 to 1825 are equal and these cells are flat. In this case, the outlet is the cell 1822. Finally, the direction in which the water in the flatland flows is determined so that the flow in the flatland is directed toward the outlet. The direction in which the water in the flat cells 1823 to 1825 flows is determined so as to go to the cell 1822 that is the outlet. The direction of water flow for each cell is indicated by an arrow in graph 1820. If this arrow is traced back from the cell 1821, the cell 1829 is traced. When the result of the steepest gradient method is corrected by the depression filling method, the correct result that the basin cells of the cell 1821 are the cells 1822 to 1829 is obtained.

  “Method for flow analysis utilizing cell elevation topography” disclosed in Patent Document 1 can be cited as a mounting method for increasing the processing efficiency of the depression filling method. In this method, the interior of the area is divided into a plurality of major cells in advance, and the interior of the major cell is further divided into at least three minor cells in the horizontal direction and the vertical direction. Then, when calculating the gradient in a certain minor cell, the depression filling method is applied to the major cell including the minor cell and the major cell adjacent to the major cell. Thereafter, the gradient is calculated again for the minor cells contained in these major cells. In the method disclosed in Non-Patent Document 1, it is necessary to apply the depression filling method to the entire area to be processed. However, in the method disclosed in Patent Document 1, a plurality of areas to be processed are included. It becomes possible to divide and apply the depression filling method for each divided area.

  Regardless of the method, the watershed is extracted by the following procedure. First, the direction of water flow is determined only from the gradient (the steepest gradient method). Next, with respect to the flat cell and the depression cell from which water does not flow, the direction of the water flow of the cell is determined based on the arrangement of the altitude (the depression filling method). Finally, the direction of water flow is reversed from the cell specified by the user. The cell passed at that time is the basin cell.

US Patent Application Publication No. 2005/0049802

Costa-Cabral, M. C., and S. J. Burges (1994), Digital elevation model networks (DEMON): A model of flow over hillslopes for computation of contributing and dispersal areas, Water Resource Research, 30 (6), 1681-1692. O'Callaghan, J. F., and D. M. Mark: The extraction of drainage networks from digital elevation data, Computer Vision, Graphics, and Image Processing, 28 (3), 323-344, 1984. Jenson, S. K., and J. O. Domingue: Extracting topographic structure from digital elevation data for geographic information system analysis, Photogrammetric Engineering and Remote Sensing, 54 (11), 1593-1600, 1988.

  In the conventional watershed extraction program, the watershed is extracted after the direction of water flow is determined. Therefore, before extracting the basin, it is necessary to give the program a range that determines the direction of water flow. If the range that determines the direction of water flow is smaller than the basin, the correct basin cannot be extracted. Therefore, in order to extract a correct basin, the user of the program needs to know in advance the basin to be extracted. However, users who know the basin need not use the basin extraction program. For this reason, the conventional watershed extraction program has been applied only for limited purposes.

  The present invention has been made in view of this problem. The objective of this invention is providing the program computer program which can extract a basin even if it is a user who does not know a basin beforehand.

  A representative invention disclosed in the present application is a basin extraction program for controlling a computer, wherein the computer stores a memory in which the basin extraction program is stored, and a processor that executes the basin extraction program stored in the memory. And holding elevation data indicating elevations of a plurality of areas on a map, the plurality of areas including a first area, and the basin extraction program includes a basin of water flowing into the first area, In the second procedure, the processor executes a first procedure for searching in the upstream direction based on the elevation data and a second procedure for determining whether or not the basin specified by the first procedure is correct. When it is determined that the specified basin is not correct, the processor is caused to execute the first procedure again.

  According to an embodiment of the present invention, it is possible to provide a computer program for extracting a basin from a DEM. By this program, even a user who does not know the basin in advance can extract the basin.

It is a schematic block diagram which shows the structure of the computer system in the 1st Embodiment of this invention. It is a sequence diagram which shows the process performed by PC of embodiment of this invention. It is explanatory drawing which shows the state of waiting for the input of GUI which the basin extraction program of embodiment of this invention provides. It is explanatory drawing which shows the state of the analysis end of GUI which the basin extraction program of embodiment of this invention provides. It is a flowchart which shows the detail of the basin extraction process of embodiment of this invention. It is a flowchart which shows the detail of the upstream search process of embodiment of this invention. It is explanatory drawing which shows the progress of the upstream search process of GUI which the basin extraction program of embodiment of this invention provides. It is explanatory drawing which shows the progress of the cell basin cell extraction process of GUI which the basin extraction program of embodiment of this invention provides. It is a flowchart which shows the detail of the downstream search process of embodiment of this invention. It is explanatory drawing which shows the progress of the downstream search process of GUI which the basin extraction program of embodiment of this invention provides. It is explanatory drawing which shows the cell and partial area | region of embodiment of this invention. It is explanatory drawing which shows the data structure of the partial area | region of embodiment of this invention. It is explanatory drawing which shows the data structure of the cell of embodiment of this invention. It is explanatory drawing about the cell gradient of embodiment of this invention. It is a figure for demonstrating the value of the flag corresponding to the direction through which water flows in embodiment of this invention. It is explanatory drawing which shows the data structure of the hollow of embodiment of this invention. It is a flowchart which shows the detail of the depression filling process of embodiment of this invention. It is a figure for demonstrating a hollow.

  First, the outline of the present invention will be described.

  The present invention is based on the following three discoveries.

  1. The area, volume, shape, etc. of the depression and flat land are not known in advance.

  2. If depressions and flats are adjacent to the basin obtained by the program, the basin obtained by the program may be incorrect.

  3. The most upstream of the basin is not obvious, while the most downstream of the basin is obvious.

  Discovery 1 and 2 were discovered in the process of verifying the invention (Japanese Patent Application No. 2008-002284, basin estimation program) previously filed by the inventors by changing DEM data and cell size in various basins. . The outline of the invention shown in Japanese Patent Application No. 2008-002284 will be described below.

  The invention shown in Japanese Patent Application No. 2008-002284 is based on the discovery that any cell can be proved not to be a depression below an area. The maximum length that can be taken by a depression or flat land having a certain area (that is, consisting of a certain number of cells) is the length when the cells are arranged in a straight line. If the depression filling method is applied to a cell closer than this length from a certain cell, at least the cell at the center is not a depression or flat area of a certain area or less. Therefore, in the invention shown in Japanese Patent Application No. 2008-002284, a parameter called “maximum area of depressions” is introduced, and depressions and flat areas with areas smaller than this are filled. The present invention further utilizes the concept of “partial region” of another invention (Japanese Patent Laid-Open No. 2007-034373, space simulation program and apparatus) filed earlier.

  Examples of the invention shown in Japanese Patent Application No. 2008-002284 are as follows. Define the maximum area of the depression beforehand. Further, a partial area composed of a plurality of adjacent cells is defined in advance, and all the cells are associated with the partial areas. When the user designates the start cell, the program sets the start cell as the target cell (step 1). Subsequently, the partial area including the target cell is set as the target partial area (step 2). A depression filling process is performed for a partial area whose distance from the target partial area is closer than the maximum length that the largest depression can take (step 3). By this process, a depression having a predetermined area or less is removed from the target partial region. Subsequently, the downstream direction (that is, the flow direction of water flowing out from each cell) is calculated for the eight cells adjacent to the target cell (step 4). The downstream direction is the steepest downward gradient direction. The cell having the target cell in the downstream direction is set as the next target cell (step 5). If the next target cell exists, the process returns to step 2 (step 6).

  On the other hand, the present invention utilizes discoveries different from the previous invention. That is, the present invention is based on the discoveries 1 to 3 described above. The present invention eliminates the parameter “maximum area of depression” that was necessary in the previous invention. The basin extraction program of the present invention devised by the inventors comprises the following steps 1 and 2.

  Step 1: Search the upstream cell of the cell specified by the user.

  The direction of water flow may be determined by the steepest gradient method, the method described in Japanese Patent Application No. 2008-002284, or the like. As a result, a basin having a cell designated by the user as a downstream end is extracted. However, the basin obtained by step 1 may be incorrect. This is because if there is a depression adjacent to the basin outside the obtained basin, the obtained basin may be incorrect (Discovery 2) and it cannot be guaranteed that such a depression does not exist. (Discovery 1). The most upstream is not obvious (discovery 3). That is, for example, there is no mark indicating the most upstream on the map or on the site, so it cannot be guaranteed that the basin obtained in step 1 is correct.

  Step 2: Determine the authenticity of the basin extracted in Step 1.

  For this determination, a pair of basin definitions is used. That is, if there is a non-basin cell downstream of a non-basin cell, the basin is correct. According to Discovery 3, the most downstream is obvious. In other words, the most downstream of the river is the sea. (To be precise, the most downstream is the area where there is no water outlet, and depending on the region, the lake, desert, etc. where there is no water outlet may be the downstream. Hereinafter, an area where there is no water outlet is referred to as an “invalid area”, and a cell included in the area is referred to as an “invalid cell”). However, in the program, the most downstream area may not be an invalid area. That is, the most downstream is a depression. Therefore, after determining the direction of water flow in the vicinity of the cell by the depression filling method, the downstream search is performed again. In this way, a cell other than the basin extracted in step 1 is set as a start cell, and a downstream search is performed to an invalid cell. If the cell specified by the user is not included in the downstream cells thus obtained, it is determined that the basin extracted in step 1 is true. In the program processing, the downstream search may be terminated based on an index such as an altitude value.

  If the result of determination in step 2 is false, the process returns to step 1. In that case, cells other than the basin extracted in step 1 exist upstream of the cell designated by the user. Therefore, the watershed obtained in step 1 executed again is different from the watershed obtained in the previous step 1.

  Note that the cells used as the start cells for the downstream search in step 2 may be limited to cells other than the basin extracted in step 1 and adjacent to the basin cell extracted in step 1. This is because these cells are always searched downstream when the basin is determined to be false.

  Hereinafter, embodiments of the present invention will be described with reference to the accompanying drawings.

  FIG. 1 is a schematic block diagram showing the configuration of a computer system according to an embodiment of the present invention.

  The computer system of this embodiment is configured by a PC (Personal Computer) 100. The PC 100 includes an input / output unit 110. The input / output unit 110 includes an input unit including a keyboard 111 and a mouse 112, and an output unit including a display 113. The user can input a command from the input unit and check the result using the output unit.

  The PC 100 further includes a memory 120 and a CPU (Central Processing Unit) 130. A basin extraction program 141 is developed in the memory 120. This basin extraction program 141 is configured by an instruction to the CPU 130. The CPU 130 performs calculations according to instructions of the basin extraction program 141, accesses an HDD (Hard Disk Drive) 190, exchanges information with the input / output unit 110, and the like. In the following description, the processing executed by the basin extraction program 141 is actually executed by the CPU 130 according to instructions described in the basin extraction program 141.

  The HDD 190 stores map data 191, altitude data 192, and sea area data 193, and the basin extraction program can read these data. The HDD 190 may be incorporated in the PC 100, connected to the outside of the PC 100, or connected to another device that can be accessed from the PC 100 via a network.

  The map data 191 may be information that allows the user to understand the location. Information suitable as the map data 191 includes place names, administrative boundaries, roads, railways, satellite images, contour lines, coastlines, and the like. In the present embodiment, at least a contour line and a coastline are used. Furthermore, information indicating the position of the water surface, such as a valley line, a river channel line, a coastline, a lake surface, and the sea surface, and information indicating the position of the watershed such as a basin boundary line may be used as necessary.

  The elevation data 192 is data generally called a digital elevation model (DEM). That is, information describing the position of the cell and the altitude of the ground surface in the cell. A typical DEM is an elevation value in square grids arranged at equal intervals on the ground surface.

  The sea area data 193 is data indicating a water area having no outlet. In other words, in addition to the sea area, the data can identify a closed lake area (a lake without a water outlet). In many cases, this data is the same as the data indicating the sea area, and the sea area can be determined based on the altitude data 192. That is, in normal altitude data, an altitude value is stored in the land area, and a value indicating the sea area is stored in the sea area. In that case, this sea area data 193 is unnecessary, and only the altitude data 192 is sufficient.

  FIG. 2 is a sequence diagram illustrating processing executed by the PC 100 according to the embodiment of this invention.

  Hereinafter, the processing sequence of the system will be described with reference to FIG.

  The basin extraction program 141 is activated on the PC 100. The basin extraction program 141 reads the map data 191 from the HDD 190 (step 201). The basin extraction program 141 that has read the data outputs a GUI (Graphical User Interface) composed of the window 300 to the display 113 (step 202).

  FIG. 3 is an explanatory diagram showing a waiting state for GUI input provided by the basin extraction program 141 according to the embodiment of this invention.

  3 includes a window 300 displayed in a predetermined area of the display 113, and receives input from the keyboard 111 and the mouse 112. The window 300 displays at least a map 310. The user can display a map 310 of an area required by the user by a predetermined operation. The scale of the map 310 is preferably about the same as the spatial scale of the outflow phenomenon. Therefore, for typical spill events, a scale of 1 / 25,000 or coarser is appropriate. The map 310 of the present embodiment includes information on the contour line 311 and the coastline 312.

  Further, the window 300 has at least a function for the user to designate one or more points and a function for the user to confirm the designation. As will be described later, the mouse pointer 301 is used to designate one or more points, and the analysis button 303 is used to confirm the designation.

  Using this GUI, the user designates an analysis target (step 203). In the present embodiment, when the user moves the mouse 112, the mouse pointer 301 is moved on the map 310, and by clicking the mouse 112, an arbitrary point is designated as the downstream end. Note that it is desirable to display the icon 302 at a designated point in order to convey the user operation result to the user in an easy-to-understand manner.

  FIG. 3 shows a state in which the user designates two very close points near the estuary as downstream ends. In this case, the basin extraction program 141 will analyze these basins with these two points as downstream ends. The user clicks the analysis button 303 after inputting the analysis target. When the analysis button 303 is clicked, the basin extraction program 141 designates the cell corresponding to the input point as the “start cell”.

  Note that it is not necessary to limit the analysis target input in step 203 to a point. Any information may be input as long as the information can be converted into a cell. Typical information other than the point includes a line or a surface. The input point, line or surface information can be converted into cells using the basic known techniques of geographic information systems. Such techniques are described, for example, by Masao Iri, Takeshi Koshizuka (1993), Computer Science and Geographic Information Processing 2nd Edition, Kyoritsu Publishing Co., Ltd., ISBN 4320026365.

  When a river channel line (a river center line) is input as a line, it is possible to extract a basin in consideration of a fine water channel that is difficult to express by DEM. When a coastline is input as a line, it is possible to extract the basin of the coastline, which is convenient when extracting the basin of the bay, for example. When a lake surface is input as a surface, it is possible to extract a basin for that lake.

  Alternatively, these pieces of information may be taken from the map data 191 instead of being input by the user. For example, since river channel lines, coastlines, lake surfaces, etc. are generally distributed as geographic information data, they can be used.

  In this embodiment, the user can select an input method by operating the radio button 332 of the sub window 330. For example, when the user designates “mouse designation” and “point” of the radio button 332, the user can input the downstream end point using the mouse 112. Alternatively, when the user designates “open” of the radio button 332, the user can input information included in the map data 191 (for example, a river channel line).

  Further, in step 203, the user may additionally input points, lines, surfaces, etc. outside the basin. In this case, the user inputs a point, line, surface, etc. outside the basin in addition to points, lines, surfaces, etc. in the basin, and then clicks the analysis button 303. When the analysis button 303 is clicked, the basin extraction program 141 designates a cell corresponding to a point, line, surface, or the like input as outside the basin as an “invalid cell”. Therefore, one or more cells are designated as start cells, and other zero or more cells are designated as invalid cells. When information outside the basin is input, the downstream search process (step 504) described later can be greatly shortened. In the present embodiment, by operating the radio button 331 of the sub window 330, it is possible to select whether the input point or the like is inside or outside the basin.

  Further, at 203, the user may define a method for determining out-of-basin cells (or invalid cells) based on elevation data. Generally, only a point having an elevation higher than that point exists upstream of the point. By using this knowledge, a cell whose elevation is lower than that of the start cell can be regarded as an out-of-basin cell (or an invalid cell). Therefore, the basin extraction program 141 may consider a cell whose elevation is lower than that of the start cell as a cell outside the basin (or an invalid cell). Alternatively, the basin extraction program 141 may consider a cell having an altitude smaller than a certain value as a cell outside the basin (or an invalid cell) in consideration of a case where there is an error in the altitude data.

  Next, the basin extraction program 141 repeatedly performs the basin extraction process (step 204). This step 204 includes altitude data and sea area data reading processing (step 205) and progress display processing (step 206). In step 205, the basin extraction program 141 reads the altitude data 192 from the HDD 190. In step 206, the basin extraction program 141 displays a symbol indicating progress on the window 300. Step 206 is not essential and may be omitted. Details of step 204 will be described with reference to FIGS.

  Finally, the basin extraction program 141 displays the basin as a processing result on the window 300 (step 207).

  FIG. 4 is an explanatory diagram illustrating a state where the analysis of the GUI provided by the basin extraction program 141 according to the embodiment of this invention is completed.

  In FIG. 4, two kinds of symbols indicating the basin are displayed. The first symbol is a line segment 401 indicating the direction in which water flows. Water flows down along this line. The second symbol is a line segment 402 indicating a water divide. The water inside the diversion basin flows down to one of the two points 302 designated in FIG. On the other hand, the water outside the diversion tank does not flow down to any of the two points 302 designated in FIG.

  Next, details of the basin extraction process (step 204) will be described.

  FIG. 5 is a flowchart showing details of the basin extraction process (step 204) according to the embodiment of the present invention.

  In step 501, the basin extraction program 141 sets the start cell as a “basin cell”. Specifically, the basin extraction program 141 changes a variable indicating the cell type included in the data of the start cell to “basin”. The cell data will be described later (see FIG. 13). The start cell is a cell corresponding to the point, line, surface or the like input as an analysis target in step 203. As described above, the basic technology of the geographic information system is used for the point-cell, line-cell, or area-cell conversion.

  In step 502, the watershed extraction program 141 searches upstream of the start cell. Here, the upstream search process executed in step 502 will be described with reference to FIGS.

  FIG. 6 is a flowchart showing details of the upstream search processing (step 502) according to the embodiment of this invention. Details of FIG. 6 will be described later.

  FIG. 7 is an explanatory diagram showing progress of the GUI upstream search processing (step 502) provided by the basin extraction program 141 according to the embodiment of this invention.

  The cell designated as the target cell in step 602 of FIG. 6 is shown as a point 701 in FIG. As the upstream search process progresses, the target cell advances from the start cell one cell at a time in the upstream direction, and the point 701 advances one cell at a time in the upstream direction. Further, the partial area read in step 603 is shown as a rectangle 702 in FIG. This rectangle is also added in the upstream direction as the upstream search process progresses. In FIG. 7, four rectangles are drawn. This indicates that four partial areas have already been read. From these points and the movement of the rectangle, the user can know that the upstream search process is currently being executed, and can intuitively grasp the progress of the process. Through the processing in step 502, the basin of the start cell is extracted as a “basin cell”.

  In step 503, the basin extraction program 141 extracts out-of-basin cells. By this process, not the basin cell extracted in step 502 but a cell adjacent to the basin cell is extracted. The extracted cell is referred to as an out-basin cell.

  FIG. 8 is an explanatory diagram showing the progress of the GUI outside basin cell extraction process (step 503) provided by the basin extraction program 141 according to the embodiment of this invention.

  The out-of-basin cell extracted in step 503 is shown as point 801 in FIG. When it is determined that the basin is correct by the basin authenticity determination performed after step 504, these points 801 become watersheds. A user who knows in advance where the watershed is located can predict the result of true / false judgment made from these points, and can estimate the time required for the remaining processing.

  In step 504, the basin extraction program 141 searches downstream of the cell extracted in step 503.

  FIG. 9 is a flowchart illustrating details of the downstream search process (step 504) according to the embodiment of this invention. Details of FIG. 9 will be described later.

  FIG. 10 is an explanatory diagram showing the progress of the GUI downstream search processing (step 504) provided by the basin extraction program 141 according to the embodiment of this invention.

  The cell designated as the target cell in step 902 in FIG. 9 is shown as a point 1001 in FIG. As the downstream search process progresses, the target cell advances one cell at a time from the out-basin cell extracted in step 503 toward the downstream direction. For this reason, the movement of the point 1001 allows the user to know that the downstream search process is currently being executed, and to intuitively grasp the progress of the process. Through the downstream search process, a cell downstream of the cell outside the basin extracted in step 503 is extracted as the “cell outside the basin”.

  In step 505, the basin extraction program 141 determines the value of the redo flag (described later with reference to FIG. 9). If it is determined that the value of the redo flag is true, the previous upstream search process in step 502 (if the loop from step 502 to 505 has been executed a plurality of times so far, the upstream search process executed last) The obtained basin is incorrect. In other words, the true basin extends further outside the basin obtained by the previous upstream search process. In this case, the process returns to step 502. Then, the basin extraction program 141 executes the upstream search for the start cell again. When the depression filling process is executed in the previous downstream search process, the downstream direction of the cell in the depression is determined as will be described later. In this case, the result of the current upstream search process is different from the result of the previous upstream search process.

  If it is determined in step 505 that the value of the redo flag is false, the basin obtained by the previous upstream search process is correct. Therefore, the basin extraction program 141 ends the basin extraction process.

  The overall processing flow of the present embodiment has been described above. Hereinafter, individual processes and data structures for realizing the processes will be described in detail.

  FIG. 11 is an explanatory diagram showing cells and partial areas according to the embodiment of the present invention.

  In this embodiment, a two-dimensional orthogonal coordinate system is used in which the east-west direction of the space is the x-axis (1101) and the north-south direction is the y-axis (1102). Furthermore, this space is divided at intervals of dx (1103) in the x-axis direction and dy (1104) in the y-axis direction to generate cells. The cell (i, j) at the point (x, y) is obtained by the following equation (1).

i = floor (x / dx), j = floor (y / dy) ......... (1)

However, floor () is a function that makes an integer by truncating the decimal part.

  The partial area is an area composed of a plurality of cells. The partial area is assumed to be composed of cells of si (1105) in the x-axis direction and sj (1106) in the y-axis direction. However, si and sj are integers of 2 or more (in FIG. 11, an example of si = 10 and sj = 10 is shown, but in FIGS. 7, 8 and 10, si = 28 and sj = 28. Example). Therefore, one cell is included in one partial area. The partial region (bi, bj) including the cell (i, j) is obtained by the following equation (2).

bi = floor (i / si), bj = floor (j / sj) ......... (2)

  FIG. 12 is an explanatory diagram illustrating a data structure of a partial area according to the embodiment of this invention.

  In the following description regarding the data structure, an implementation method suitable for an object-oriented language such as C ++ is shown. Table 1200 shows partial area type data. At the time of implementation, the type of the class name CellUnit having these data as member variables may be used.

  CellUnit is a class having three member variables: Id, Cells, and Targets.

  Id is an integer type, and holds a value uniquely generated from bi and bj shown in the above formula (2) (line 1201). Id may be created, for example, by setting bi and bj as 32-bit integers and Id as 64-bit integers, storing the value of bi from 0 to 31 bits and the value of bj from 32 to 63 bits, respectively. .

  Cells is a fixed-length array that stores the cell types described in FIG. 13 (line 1202). The length of the array is the number of cells included in one partial area, that is, si * sj.

  Targets is a variable length array that stores cell types (row 1203). The initial value of this variable is empty, that is, an array with no stored elements.

  FIG. 13 is an explanatory diagram illustrating a data structure of a cell according to the embodiment of this invention.

  Table 1300 shows cell type data. The cell type (class name Cell) is a class having three member variables Glev, Kind, and DownDir.

  Glev is a real type and holds the altitude (line 1301).

  Kind is an enumerated type and is a flag indicating whether it is undecided (0), basin (1), out of basin (2), or invalid (3) (line 1302). Undecided (0) indicates that the cell is a valid cell, but it is not yet determined whether it is a basin cell or an out-of-basin cell. The basin (1) indicates that the cell is an effective cell and is a basin cell. Outside the basin (2) indicates that the cell is an effective cell and is a cell outside the basin (in other words, a basin cell belonging to another basin). Invalid (3) indicates that the cell is an invalid cell. The initial value of Kind is undecided (0).

  DownDir is an enumerated type, and is a flag indicating the direction in which water flows (that is, the direction of an adjacent downstream cell) (line 1303). A specific value of DownDir will be described with reference to FIGS. The initial value of DownDir is 0 indicating that there is no adjacent downstream cell. In order to determine the direction in which water flows, it is necessary to determine the cell gradient.

  FIG. 14 is an explanatory diagram of the cell gradient according to the embodiment of this invention.

  FIG. 14 shows three cells in the i-axis direction and three cells in the j-axis direction centering on the cell 1400. The gradient in the cell (i, j) is a value obtained by dividing the difference between the elevation value of the cell (i, j) and the elevation value in the cell adjacent to the grid by the distance between the cells. Eight cells are adjacent to one cell. Accordingly, gradients in eight directions in the cell (i, j) are calculated. The direction of the gradient is indicated by arrows 1401 to 1408, respectively. The gradients corresponding to the arrows 1401 to 1408 are named Grad1 to Grad8, respectively. The formula for obtaining the values of the variables Grad1 to Grad8 is as follows.

Grad1 = (Glev [i, j] -Glev [i-1, j + 1]) / hypot (dx, dy) ......... (3-1)
Grad2 = (Glev [i, j] -Glev [i, j + 1]) / dy ......... (3-2)
Grad3 = (Glev [i, j] -Glev [i + 1, j + 1]) / hypot (dx, dy) ......... (3-3)
Grad4 = (Glev [i, j] -Glev [i-1, j]) / dx ......... (3-4)
Grad5 = (Glev [i, j] -Glev [i + 1, j]) / dx ......... (3-5)
Grad6 = (Glev [i, j] -Glev [i-1, j-1]) / hypot (dx, dy) ......... (3-6)
Grad7 = (Glev [i, j] -Glev [i, j-1]) / dy ......... (3-7)
Grad8 = (Glev [i, j] -Glev [i + 1, j-1]) / hypot (dx, dy) ......... (3-8)

However, Glev [i, j] is a function that returns the altitude in cell (i, j), and hypot (x, y) is a function that returns the distance between the origin (0,0) and point (x, y). In this embodiment, 8 neighbors (that is, 8 adjacent cells) are used as adjacent cells. This is because more accurate results can be expected as the number of adjacent cells increases. However, as the adjacent cells, not four neighbors but four neighbors (that is, four neighboring cells) may be used. In that case, it is sufficient to use only Grad2, Grad4, Grad5, and Grad7 among the gradients in the above eight directions.

  An adjacent downstream cell of a cell (i, j) is obtained from the gradients Grad1 to Grad8 of the cell (i, j). Specifically, an adjacent downstream cell of a certain cell (i, j) is an adjacent cell in the steepest downward gradient direction of the cell. The steepest downward gradient is the maximum value of the gradients Grad1 to Grad8, and the steepest downward gradient direction is the direction of the maximum value of the gradients Grad1 to Grad8. This steepest downward gradient direction can be classified into the following three cases (a) to (c).

(A) The steepest downward slope is greater than 0 and is in one direction. In this case, the steepest downward gradient direction is the direction in which water flows.

(B) When the steepest descending slope is greater than 0 and more than one direction. In this case, one direction is selected according to a predetermined direction priority from the steepest downward gradient direction. In the present embodiment, the priority is set in the order of the following formula (4).

Grad2> Grad5> Grad7> Grad4> Grad1> Grad3> Grad8> Grad6 ......... (4)

  For example, if the values of Grad2 and Grad3 are the same, and these are the steepest downward gradient directions, the priority of Grad2 is higher than that of Grad3, so the cell (i, j + 1) in the direction 1402 corresponding to Grad2 ) Is an adjacent downstream cell.

(C) When the steepest descending slope is 0 or less. In this case, there is no direction in which water flows, and it is determined that there is no adjacent downstream cell. In this embodiment, since the altitude of the invalid cell is treated as negative infinity as will be described later, the cell in which the steepest downward gradient direction is determined to be 0 or less is a depression or a flat ground.

  FIG. 15 is a diagram for explaining the direction in which water flows and the flag values corresponding thereto in the embodiment of the present invention.

  In the implementation, the member variable DownDir of the cell type Cell holds the value shown in FIG. When the steepest downward gradient direction is (a) or (b), DownDir has a value of 1, 2, 4, 8, 16, 32, 64, or 128. For example, if the direction in which the water in the cell (i, j) flows is the direction 1405 in FIG. 14 (that is, the adjacent downstream cell of the cell (i, j) is the cell (i + 1, j)), the value of DownDir Becomes 1. When the steepest downward gradient direction is (c) (that is, when there is no adjacent downstream cell), DownDir has a value 0 indicating undetermined.

  Next, details of the upstream search process (step 502) will be described with reference to FIG.

  The basin extraction program 141 repeats the processing from step 601 to step 612 for each basin cell. In the description of FIG. 6, the processing target cell of this loop is referred to as cell1. In the implementation, in step 501, the start cell is stored in the member variable Targets of the partial region class CellUnit, and this loop is executed for each element of Targets.

  In step 602, the basin extraction program 141 designates cell1 as the “target cell”.

  In step 603, the basin extraction program 141 reads a partial region including the target cell (cell1). Thereby, the altitude data 192 and the sea area data 193 are read. The basin extraction program 141 designates a cell determined as a sea area based on the sea area data 193 as an invalid cell. Furthermore, when an invalid cell or a non-basin cell is designated in step 203, the basin extraction program 141 designates the cell as an invalid cell or a non-basin cell. Then, the basin extraction program 141 makes the altitude of the invalid cell negative infinity.

  In the implementation, for example, the following procedure is executed. First, the basin extraction program 141 generates an instance of the partial region class CellUnit in the memory 120. The instance of the partial region class CellUnit stores the ID generated from bi and bj in the variable Id, and holds si * sj instances of the cell class Cell in the variable Cells. The member variables Kind and DownDir of the cell class Cell are initialized to the initial values shown in Table 1300.

  The following values are stored in the member variables Glev and Kind. When it is determined that the cell is an invalid cell based on the sea area data 193 or the designation in step 203, negative infinity is stored in the member variable Glev as an elevation value, and invalid (3 ) Is stored. When it is determined that the cell is a valid cell, the altitude data 192 read from the HDD 191 is stored as the altitude value in the member variable Glev, and undetermined (0) is stored in the member variable Kind. However, when it is determined that the cell is a cell outside the basin, the outside of the basin (2) is stored in the member variable Kind.

  Next, the basin extraction program 141 repeats the processing from step 604 to step 611 for each adjacent cell of the target cell (cell1). In the description of FIG. 6, a cell to be processed in this loop (that is, each of a plurality of cells adjacent to cell1) is referred to as cell2.

  In step 605, the basin extraction program 141 determines whether the adjacent downstream cell of cell2 is the target cell (cell1). If the result of this determination is true, the process proceeds to step 606, and if it is false, the process proceeds to step 611.

  The adjacent downstream cell of cell2 is obtained by the steepest gradient method as described with reference to FIG. However, as described later, when the downstream direction of cell2 is determined by the depression filling process, the adjacent downstream cell of cell2 is obtained based on the downstream direction.

  In the implementation, a value indicating the direction in which water flows is stored in the member variable DownDir of cell2 by this step.

  In step 606, the basin extraction program 141 determines the type of cell2. Specifically, the basin extraction program 141 refers to the value of the member variable Kind of the cell class Cell relating to cell2, and determines whether cell2 is a basin cell, a non-basin cell, an invalid cell, or an undetermined cell.

  According to the definition of the basin, if cell2 is a valid cell, the cell adjacent to cell2 is cell1, and cell1 is a basin cell, cell2 is necessarily a basin cell. In order to match this, the basin extraction program 141 updates the value of the member variable Kind of the cell class Cell relating to cell2 (steps 607 to 610).

  If the value of the member variable Kind of the cell class Cell relating to cell2 is the basin (1), cell2 is already handled as a basin cell. In this case, since it is not necessary to update the value of the member variable Kind, the basin extraction program 141 proceeds to step 611 without updating the value of the member variable Kind (step 607).

  If the value of the member variable Kind is outside the basin (2), cell2 is a basin outside cell. This means that cell2 has already been determined to be a basin cell belonging to another basin. In this case, the basin extraction program 141 proceeds to step 611 without updating the value of the member variable Kind (step 608). However, according to the definition of the basin, if it is determined in step 606 that cell2 is a valid cell, cell2 is necessarily a basin cell. For this reason, as long as the upstream search is normally executed, it is impossible to determine that cell2 is a cell outside the basin in step 606.

  If the value of the member variable Kind is invalid (3), cell2 is an invalid cell. In this case, since cell2 cannot be a basin cell, the basin extraction program 141 proceeds to step 611 without updating the value of the member variable Kind (step 609).

  When the value of the member variable Kind is undetermined (0), cell2 is an undetermined cell. As described above, according to the definition of the basin, if it is determined in step 606 that cell2 is a valid cell, cell2 is necessarily a basin cell. Therefore, the basin extraction program 141 changes cell2 to a basin cell (step 610), and proceeds to step 611. Specifically, the basin extraction program 141 updates the value of the member variable Kind of the cell class Cell relating to cell2 to the basin (1). Furthermore, the basin extraction program 141 adds cell2 to the member variable Targets of the partial region class CellUnit. As a result, cell2 becomes a new target cell.

  In step 611, the process returns to the loop in step 604. This loop is repeatedly executed until the loop of steps 604 to 611 is completed for all cell2 adjacent to cell1.

  In step 612, the process returns to the loop of step 601. This loop is repeatedly executed until the loop of steps 601 to 612 is completed for all the target cells.

  Next, details of the downstream search process (step 504) will be described with reference to FIG.

  The basin extraction program 141 repeats the processing from step 901 to step 912 for each cell outside the basin. In the description of FIG. 9, the processing target cell of this loop is referred to as cell1. In the implementation, in step 503, cells outside the basin are stored in the member variable Targets of the partial region class CellUnit, and this loop is executed for each element of Targets.

  For example, when the plurality of cells 801 shown in FIG. 8 are out-basin cells when step 502 is completed, all these cells 801 are stored in the member variable Targets. Then, the loop of FIG. 9 is repeated for each out-basin cell until the processing is completed for all out-basin cells.

  In the description of FIG. 9, “basin cell” refers to a cell belonging to the basin to which the start cell (cell corresponding to the icon 302 in the example of FIG. 3) belongs, and “other basin” refers to the start cell. A basin different from the basin, and a cell outside the basin mean a cell belonging to another basin (that is, a cell not located upstream of the start cell).

  In step 902, the basin extraction program 141 designates cell1 as the “target cell”.

  In step 903, the basin extraction program 141 reads a partial region including the target cell (cell1). This operation is the same as step 603.

  In step 904, the basin extraction program 141 identifies an adjacent downstream cell of cell1 (described as cell2 in the description of FIG. 9) and determines its type. Specifically, the basin extraction program 141 refers to whether or not cell2 exists, and if so, with reference to the value of the member variable Kind of the cell class Cell related to cell2, cell2 is a basin cell, a basin cell, It is determined whether the cell is an invalid cell or an undetermined cell. The cell adjacent to cell1 is obtained by the steepest gradient method (see FIG. 14). In the implementation, a value indicating the direction in which water flows is stored in the member variable DownDir of cell1.

  Here, the outline of the processing based on the determination result in step 904 will be described.

  According to the definition of the basin, if the cell extracted in step 503 is a cell outside the basin, the downstream effective cell is always a cell outside the basin. In FIG. 9, cell1 is the cell itself extracted in step 503 or a cell downstream thereof, and cell2 is a cell further downstream thereof. Therefore, when cell1 is a cell outside the basin, the downstream cell adjacent to cell1 is cell2, and cell2 is an effective cell, cell2 is always a cell outside the basin. In order to match this, the basin extraction program 141 updates the value of the member variable Kind of the cell class Cell relating to cell2.

  In such a process, it is determined that cell2 is a basin cell even though cell1 is a non-basin cell, indicating that the cell extracted in step 503 is actually a basin cell. This means that the basin acquired by the immediately upstream search process is incorrect, that is, the upstream search process needs to be redone. In this case, the basin extraction program 141 updates the value of the redo flag.

  The redo flag indicates whether the upstream search process needs to be redo. Specifically, the value of the redo flag being true indicates that the upstream search process needs to be redo. The redo flag is, for example, a Boolean global variable Failed having an initial value of false.

  Next, details of the above processing will be described.

  If the value of the member variable Kind of the cell class Cell relating to cell2 is the basin (1), cell2 is a basin cell. This contradicts that cell1 is a cell outside the basin. That is, this means that cell 1 that has already been determined to be an out-basin cell and all of its upstream cells are actually basin cells. In other words, the result of the previous upstream search process (step 502) is incorrect. Means that Therefore, the basin extraction program 141 updates the value of the redo flag to true (step 905), and proceeds to step 912.

  If the value of the member variable Kind is outside the basin (2), cell2 is a basin outside cell. This is consistent with cell1 being a basin cell. In other words, this confirmed that cell2 and all the cells upstream of it were out-basin cells. For this reason, the basin extraction program 141 proceeds to step 912 without updating the redo flag and the value of the member variable Kind (step 906). In this case, since it is not necessary to search further downstream of cell2, cell2 is not selected as a new target cell.

  Note that whether or not cell2 is a cell outside the basin may be determined by any method. For example, when it is determined that cell2 belongs to another basin by another basin extraction process executed in the past, the value of the member variable Kind related to cell2 is outside the basin (2). It is determined that cell2 is a cell outside the basin, and the process proceeds to step 906. The same applies when the user designates a range outside the basin in advance. Alternatively, if it is determined that the altitude of cell2 is lower than a predetermined altitude (for example, the altitude of the start cell) regardless of the value of the member variable Kind, it is determined that cell2 is an out-basin cell, and the process is performed in step 906. You may proceed to. Alternatively, when the start cell is a cell on the river and cell2 is determined to be a cell on a different river from the one to which the start cell belongs, it is determined that cell2 is a cell outside the basin, and the processing is performed. Proceed to step 906. It can be determined based on the map data 191 which river each cell is on.

  If the value of the member variable Kind is invalid (3), cell2 is an invalid cell. This is consistent with cell1 being a basin cell. In other words, this confirmed that cell1 and all the cells upstream of it were out-basin cells. For this reason, the basin extraction program 141 proceeds to step 912 without updating the redo flag and the value of the member variable Kind (step 907). Also in this case, since it is not necessary to search further downstream of cell2, cell2 is not selected as a new target cell.

  When the value of the member variable Kind is undetermined (0), cell2 is an undetermined cell. According to the definition of the basin, if it is determined in step 904 that cell2 is a valid cell, cell2 is always a cell outside the basin. Therefore, the basin extraction program 141 changes cell2 to a cell outside the basin (step 908), and proceeds to step 912. Specifically, the basin extraction program 141 updates the value of the member variable Kind of the cell class Cell relating to cell2 to outside the basin (2). Furthermore, the basin extraction program 141 adds cell2 to the member variable Targets of the partial region class CellUnit. As a result, cell2 becomes a new target cell.

  When the altitude of all cells adjacent to cell1 is equal to or higher than the altitude of cell1 (that is, when cell1 corresponds to the case (c) described in FIG. 14), according to the steepest gradient method, the downstream direction of cell1 is Does not exist (in other words, water does not flow out of cell1). For this reason, in step 904, it is determined that cell2 does not exist. In this case, the basin extraction program 141 executes processing for determining the downstream direction of the cell 1 based on the arrangement of the altitudes of a plurality of cells around the cell 1 instead of the steepest gradient method.

  Specifically, the basin extraction program 141 changes cell1 to a depression cell (step 909), and executes depression filling processing (step 910). The processing executed in steps 909 and 910 will be described later (see FIGS. 16 and 17). When the depression filling process ends, the basin extraction program 141 changes the depression cell to a cell outside the basin (step 911), and proceeds to step 912.

  When the loop from step 901 to step 912 is completed for all cells outside the basin, the basin extraction program 141 ends the downstream search process.

  Next, details of the depression filling process (step 910) will be described with reference to FIGS.

  FIG. 16 is an explanatory diagram illustrating a data structure of a depression according to the embodiment of this invention.

  Table 1600 shows depression type data. At the time of implementation, the type of the class name Sink that has these data as member variables may be used.

  Sink is a class that has four member variables: Cells, Outlets, Wlev, and Finished. Cells and Outlets are variable length arrays that store cell types (lines 1601 and 1602). Cells and Outlets store depression cells and outlet cells described in FIG. The initial value of Cells and Outlets is empty. Step 909 of FIG. 9 is performed by adding cell1 to the member variable Cells. Wlev is a real number type and stores the adjacent minimum elevation described with reference to FIG. 17 (line 1603). Finished is a Boolean type and stores an end flag (line 1604). The initial value of Finished is false.

  FIG. 17 is a flowchart showing details of the depression filling process (step 910) according to the embodiment of the present invention.

  In step 1701, the basin extraction program 141 calculates “adjacent minimum elevation”. The adjacent minimum altitude is the minimum altitude of the altitudes of the cells adjacent to the depression cell. At the start of the depression filling process, the depression cells are only those obtained in step 909. Therefore, the adjacent minimum elevation at that time is the minimum value of the elevation of 8 cells adjacent to each depression cell obtained in step 909, and the value is equal to or more than the elevation of the depression cell obtained in step 909. Is also big.

  In the implementation, at the end of step 909, only one depression cell acquired in step 909 is stored in the member variable Cells of the depression type sink. Furthermore, in this step 1701, the minimum value of the altitude of the cell adjacent to the member variable Cells is stored in the member variable Wlev.

  The basin extraction program 141 repeats the processing from Step 1702 to Step 1710 for each depression cell. In the description of FIG. 17, the cell to be processed in this loop is referred to as cell1. The implementation executes this loop for each element of the member variable Cells.

  The basin extraction program 141 repeats the processing from step 1703 to step 1709 for each adjacent cell of cell1. In the description of FIG. 17, the processing target cell of this loop is referred to as cell2.

  In step 1704, the basin extraction program 141 reads a partial region including cell2. This operation is the same as step 603.

  In step 1705, the watershed extraction program 141 compares the adjacent minimum elevation Wlev with the elevation of cell2. If Wlev is equal to the altitude of cell2, the process proceeds to step 1706; otherwise, the process proceeds to step 1707.

  If Wlev and cell2 are equal in elevation, cell2 is part of a depression. For this reason, in step 1706, the basin extraction program 141 changes cell2 to a hollow cell. In the implementation, cell2 is added to the member variable Cells. When step 1706 is executed, the processing from step 1702 to step 1710 for processing the added cell2 will be executed later.

  When step 1706 is executed, the altitude of cell2 is equal to the value of member variable Wlev, and the altitude value is the largest among the depression cells. For this reason, in the description of FIG. 17, the member variable Wlev is also described as the maximum depression height.

  In step 1707, the basin extraction program 141 compares the maximum depression elevation Wlev with the elevation of cell2. If Wlev is greater than cell2's elevation, cell2 is not part of the depression. Furthermore, in this case, cell2 is an outlet for water that has flowed into the depression containing cell1. In this case, the basin extraction program 141 proceeds to step 1708. On the other hand, if Wlev is less than cell2's elevation, cell2 may be part of a depression, but it may not. In this case, the basin extraction program 141 proceeds to step 1709 without executing step 1708. In implementation, the basin extraction program 141 adds cell2 to the member variable Outlets before proceeding to step 1708.

  In step 1708, the basin extraction program 141 updates the end flag Finished to true. Note that the initial value of the end flag is false. That is, the end flag Finished is false until step 1708 is executed for the first time.

  If there is a neighboring cell that has not yet been processed in step 1709, the process returns to the loop of step 1703.

  If there is a depression cell that has not yet been processed in step 1710, the process returns to the loop of step 1702.

  In step 1711, the end flag Finished is checked for authenticity. If the end flag is true, the outlet of the water that has flowed into the depression has already been identified. This means that the range of the depression has been specified. That is, the range of the depression cell at this time is the specified depression range. In this case, the process proceeds to Step 1712. On the other hand, when the end flag is false, the outlet of the water that has flowed into the depression has not yet been identified. In this case, since the range of the depression has not been specified yet, the process returns to Step 1701.

  In step 1712, the basin extraction program 141 changes the altitude of all the depression cells to the adjacent minimum elevation Wlev. It should be noted that the adjacent minimum elevation Wlev used in this step is the value obtained in the previous step 1701 and does not newly calculate the adjacent minimum elevation based on the depression cell at the time of step 1712. By this processing, the altitude of all the depression cells becomes equal. In the following description, a hollow cell whose elevation has been changed as described above is referred to as a flat cell. In the implementation, the altitude of all the cells stored in the member variable Cells is changed to Wlev.

  In step 1713, the basin extraction program 141 determines the downstream direction of all flat cells. Specifically, the watershed extraction program 141 selects a cell adjacent to the flat cell and having an altitude lower than that of the flat cell (in the example of FIG. 17, cell 2 when determined to be True in step 1707). The outlet cell. And the direction (namely, downstream direction) in which the water in a flat ground flows is determined so that the flow in a flat ground may go to an outlet cell.

  First, the basin extraction program 141 determines a downstream direction of a cell that is adjacent to the outlet cell and in which the direction of water flow is not determined among the flat cells, as a direction toward the outlet cell. When a plurality of outlet cells are adjacent to one flat cell, the downstream direction is determined according to the direction priority described above. Subsequently, the basin extraction program 141 regards the cell whose downstream direction has been determined as described above as an outflow cell, and executes the above-described processing for the new outflow cell. In this way, the same processing is repeated until the direction in which the water in all the flat cells flows is determined. In the implementation, all cells stored in the member variable Outlets are defined as outlet cells.

  The method for determining the downstream direction as described above is merely an example. The downstream direction may be determined in any way as long as it is determined that the water flowing into the depression flows out from the outlet cell. By specifying the downstream direction in this way, all the depression cells are upstream of the outlet cell of the depression, in other words, all the depression cells are the same basin to which the outlet cell of the depression belongs. Belonging to.

  The downstream direction determined as described above is used in the upstream search process (step 502) executed thereafter. Specifically, when the cell for which the downstream direction has been determined as described above is selected as cell2 of the processing in FIG. 6, the determination in step 605 is executed based on the determined downstream direction.

  Thus, in this embodiment, when the user inputs information from the input screen shown in FIG. 3, the program presents the progress screen shown in FIGS. A result display screen can be presented.

  In the present embodiment, the implementation method when the partial area is used has been described. However, the present invention can also be implemented without using partial areas. In this case, the target partial area reading process (steps 603, 903, and 1704) is deleted. Then, immediately after step 203, the following processing is added. The basin extraction program 141 first causes the user to specify the analysis target area. Next, the altitude data 192 and the sea area data 193 of the designated area are read. Next, the cell determined as the sea area by the sea area data 193 is designated as an invalid cell. Furthermore, if an invalid cell is specified in step 203, that cell is also designated as an invalid cell. Then, the elevation of the invalid cell is set to negative infinity.

  As described above, according to the present invention, a basin extraction computer program that does not require prior knowledge about a basin can be provided. By using this program, a user who can use a computer can extract a basin with the same quality as an expert.

100 PC
310 Map 302 Downstream end 401 Line segment indicating the direction of water flow 402 Line segment indicating a watershed 701 Point 702 indicating a cell to be processed in the upstream search process Rectangle 1001 indicating a partial area in which the altitude data 192 and the like are read into the memory Indicates the cell to be processed in

Claims (14)

A basin extraction program for controlling a computer,
The computer
A memory for storing the basin extraction program; and a processor for executing the basin extraction program stored in the memory;
Holds elevation data showing the elevation of multiple areas on the map,
The plurality of regions include a first region;
The basin extraction program is
A first procedure for searching upstream of a water basin flowing into the first region based on the elevation data;
Causing the processor to execute a second procedure for determining whether or not the watershed identified by the first procedure is correct;
A basin extraction program that causes the processor to execute the first procedure again when it is determined in the second procedure that the specified basin is not correct. The plurality of regions further includes a second region not included in the basin identified by the first procedure,
The basin extraction program further causes the processor to execute a third procedure for identifying the area downstream of the second area based on the elevation data,
In the second procedure, when the region identified as the downstream region of the second region by the third procedure is included in the basin identified by the first procedure, the basin identified by the first procedure is The basin extraction program according to claim 1, comprising a procedure for determining that it is not correct. The third procedure includes
When it is determined that water does not flow out of the area downstream of the second area, based on the altitude data, the range of the depression including the area where the water is determined not to flow out, and the water that has flowed into the depression A fourth procedure for identifying the outlet of
A fifth step of identifying the downstream direction of each region included in the identified depression so that the water flowing into the depression flows out from the identified outlet.
In the first procedure executed after the third procedure is executed, the downstream direction specified by the fifth procedure is used to search for a water basin flowing into the first region. The basin extraction program according to claim 2.   The basin according to claim 3, wherein the second region is a region adjacent to the basin specified by the first procedure among regions not included in the basin specified by the first procedure. Extraction program. The basin extraction program causes the processor to execute a procedure for receiving designation of the first region before the first procedure,
The first procedure includes:
Selecting the first region as a target region;
The downstream direction of the region adjacent to the target region is identified based on the gradient between the region adjacent to the target region and the region further adjacent to the target region calculated from the elevation data. And the steps to
Determining whether or not a region adjacent to the target region is upstream of the target region based on the downstream direction specified based on the gradient or the downstream direction specified by the fifth procedure; ,
When it is determined that the region adjacent to the target region is upstream of the target region, a procedure for specifying the region adjacent to the target region as a region in the basin;
The method includes: selecting a region adjacent to the target region as a new target region when it is determined that the region adjacent to the target region is upstream of the target region. The basin extraction program described in 1. The third procedure further includes:
Selecting the second region as a target region;
A procedure for calculating a gradient between the target region and a region adjacent to the target region based on the elevation data;
Determining whether an area adjacent to the target area is downstream of the target area based on the gradient; and
When it is determined that the area adjacent to the target area is downstream of the target area, the procedure of specifying the area adjacent to the target area as the downstream area of the second area;
When it is determined that the area adjacent to the target area is downstream of the target area, a procedure for specifying the area adjacent to the target area as a new target area;
The method includes a step of determining that water does not flow out of the target area when all the altitudes of a plurality of areas adjacent to the target area are higher than the altitude of the target area. The basin extraction program described in 1. The third procedure further includes a procedure of determining whether an area adjacent to the target area is upstream of the first area,
When it is determined that the region adjacent to the target region is downstream of the target region, and the region adjacent to the target region is determined not to be upstream of the first region, the basin extraction program 7. The basin extraction program according to claim 6, wherein, among the procedures included in the three procedures, the procedure for specifying the region adjacent to the target region as a region downstream of the second region is not executed by the processor.   In the third procedure, the area adjacent to the target area is the sea, the elevation of the area adjacent to the target area is lower than a predetermined value, and the area adjacent to the target area is the first The information processing apparatus includes a step of determining that an area adjacent to the target area is not upstream of the first area in at least one of cases where information indicating that the area is not upstream is input. 7. The watershed extraction program according to 7. The fourth procedure includes
A procedure for identifying an area determined not to flow out of water as an area in the depression,
Selecting one of the areas adjacent to the depression as the target area;
When the altitude of the target area is the same as the lowest value of the altitudes of all areas adjacent to the depression, the procedure of specifying the target area as a new area in the depression;
When the altitude of the area adjacent to the area in the new depression is lower than the altitude of the area in the new depression, the area adjacent to the area in the new depression is the depression. The basin extraction program according to claim 3, further comprising: a procedure for identifying the outlet of water that has flowed into the water. A display device is connected to the computer,
The first procedure further includes a procedure for causing the display device to display information indicating that the first procedure is being executed,
The basin extraction program according to claim 3, wherein the third procedure further includes a procedure for causing the display device to display information indicating that the third procedure is being executed.   10. The basin extraction program further includes a procedure for reading elevation data of a plurality of areas including the selected target area after the target area is selected. A basin extraction program according to any one of the above. A basin extraction device for extracting a water basin,
The basin extraction device comprises:
A memory, and a processor that executes a program stored in the memory,
Holds elevation data showing the elevation of multiple areas on the map,
The plurality of regions include a first region;
The basin extraction device comprises:
Search the water basin flowing into the first region in the upstream direction based on the elevation data,
Determining whether the watershed identified by the upstream search is correct;
If it is determined that the specified basin is not correct, the upstream search is performed again. The plurality of regions further include a second region that is not included in the watershed identified by the upstream search.
The basin extraction device further comprises:
Identifying the region downstream of the second region based on the elevation data;
When the specified downstream area of the second area is included in the basin specified by the upstream search, it is determined that the basin specified by the upstream search is incorrect. The basin extraction device according to claim 12. The basin extraction device further comprises:
When it is determined that water does not flow out of the area downstream of the second area, based on the altitude data, the range of the depression including the area where the water is determined not to flow out, and the water that has flowed into the depression Identify the outlet of the
Identify the downstream direction of each region included in the identified depression so that the water that flows into the depression flows out from the identified outlet.
In the upstream search performed after the downstream direction of each region included in the depression is specified, the specified downstream direction is used to search for a water basin flowing into the first region. The basin extraction apparatus according to claim 13.