JPH11341004A - Network tracking data creation device, network tracking device, network tracking data creation method, network tracking method, and recording medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To efficiently perform upstream and downstream tracking work from data of vertices and edges in a network having a direction composed of vertices and edges. SOLUTION: Manhole data 35 and pipe data 45
, Vertex data 51 and edge data 55 are created.
The vertex data 51 is similarly created for the upstream vertex and the downstream vertex of the pipe as virtual manholes. By searching for the duplication of a true manhole and a virtual manhole,
Clarify the inflow / outflow relationship of edges in the network.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a network tracking data creation device, a network tracking device, a network tracking data creation method, a network tracking method, and a recording medium for a network having a direction such as a sewer mapping system. It is.

[0002]

2. Description of the Related Art Generally, in order to manage a network having a flow direction, such as a sewer system, a drawing such as a pipe of a sewer pipe and a sewage pipe diagram (manhole pipe graph) in which a flow direction of the sewage is displayed. Is used.

[0003] In managing sewerage, for example, if harmful hazardous substances or contaminants are found, the inflow point or the source of pollution is quickly identified on the upstream side of the discovery point, and the effect on the downstream side is predicted. Must-have. Such upstream tracing and downstream tracing have been performed manually by a skilled technician while visually observing the sewage piping diagram.

In recent years, a sewage mapping system using a computer has been used. In the sewage mapping system, for example, a sewage database in which pipe positions and flow directions of sewage sewers, manhole positions, and other data are arranged is provided, and a sewage piping diagram and the like are also output to a computer.

[0005]

However, at present, pipes for sewer pipes are increasing and becoming more complicated, and the number of skilled technicians who handle sewage pipe diagrams is decreasing. Therefore, it is difficult to quickly track the upstream side and the downstream side by visual inspection of the sewage piping drawing and manually.

In computer processing, when tracing up / downstream, a large number of sides and vertices are searched in order to check the vertical relationship and continuity of the sides and vertices, and coordinates are compared. Need to process large amounts of data,
It took an enormous amount of time.

In order to handle an enormous amount of data, an area may be divided into meshes such as rectangles and data may be divided for each mesh. In such a case, when a mesh boundary overlaps with a side or a vertex, Had to perform special processing.

The present invention has been made in view of such a problem, and an object of the present invention is to enable efficient upstream / downstream tracking based on data of edges and vertices of a network such as a sewer. An object of the present invention is to provide a network recording device, a network recording method, and a recording medium that can construct a network database.

[0009]

According to a first aspect of the present invention, there is provided a network in which a plurality of vertices are connected by an edge, and at least data indicating the coordinates of both ends of the edge and a flow direction is provided. Having edge data and vertex data having the coordinates of the vertices,
Means for creating a vertex list indicating link information to an edge connected to each of the vertices; means for creating an edge list indicating link information to an upstream or downstream vertex of each of the edges; Means for adding to the list, and if one end on the upstream or downstream side of the edge data added to the vertex list matches the vertex, link information of the edge connected to this vertex is regarded as the relevant edge, and Means for using link information to an upstream vertex or a downstream vertex as the relevant vertex.

A second aspect of the present invention is a network tracking device for tracking a network using data created by the network tracking data creating device. (A) When a certain vertex is specified, an outflow edge of a vertex list is designated. The outflow edge for this vertex is calculated with reference to the link information to
(B) For the calculated outflow side, the downstream vertex for this side is calculated with reference to the link information to the downstream vertex in the side list, and (c) (a) to (b) are repeated to obtain the downstream side. A network tracking device that performs tracking.

A third invention is a network in which a plurality of vertices are connected by an edge, wherein the edge data has at least data indicating coordinates of both ends of the edge and a flow direction;
A database having vertex data having coordinates of the vertices, a step of creating a vertex list indicating link information to edges connected to the vertices, and indicating link information to upstream or downstream vertices of each edge. Creating an edge list, adding both ends of the edge data to the vertex list, and, if the vertex matches one end on the upstream or downstream side of the edge data added to the vertex list, Setting the link information of the side connected to the vertex to the relevant side, and setting the link information to the upstream vertex or the downstream vertex of the side to the relevant vertex.

A fourth invention is a network tracking method for tracking a network using data created by the network tracking data creation method. (A) When a certain vertex is specified, an outflow edge of the vertex list is specified. The outflow edge for this vertex is calculated with reference to the link information to
(B) For the calculated outflow side, the downstream vertex for this side is calculated with reference to the link information to the downstream vertex in the side list, and (c) (a) to (b) are repeated to obtain the downstream side. A network tracking method characterized by performing tracking.

According to a fifth aspect of the present invention, there is provided a network in which a plurality of vertices are connected by an edge, the edge data having at least data indicating coordinates of both ends of the edge and a flow direction;
A database having vertex data having the coordinates of the vertices, means for creating a vertex list indicating link information to edges connected to the vertices, and link information to upstream or downstream vertices of each edge. Means for creating an edge list, means for adding both ends of the edge data to the vertex list, and if the vertex matches one end on the upstream or downstream side of the edge data added to the vertex list, Means for setting the link information of the side connected to the vertex as the pertinent side, and using the link information to the upstream vertex or the downstream vertex of this side as the pertinent vertex. Is a recording medium on which is recorded.

[0014]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS The first embodiment of the present invention will be described below in detail with reference to the drawings, from the creation of network data to the tracking of upstream and downstream, taking sewage as an example. FIG. 1 is a diagram showing a device configuration of a network search system 1 according to an embodiment of the present invention, and FIG. 2 is a schematic diagram of a sewage pipe diagram (manhole pipe graph) 31.

As shown in FIG. 1, the network search system 1 includes a host computer 3, a terminal computer 5, a database 7, and a CD-ROM 15. A search command or the like is input from the terminal-side computer 5 to the host computer 3, and the host computer 3 reads out various data stored in the database 7 and performs a search process.

The database 7 stores terrain data 11 and network data 13. The network data 13 includes manhole data 35 and pipe data 45. The CD-ROM 15 stores a program for causing the host computer 3 to perform a search process, and can further store the terrain data 11 and the network data 13.

The sewage piping shown in FIG. 2 shows a part of the sewage equipment, but the sewage equipment is provided with sewers k1, k2,
.. And manholes m1, m2,. Note that k1, k2,... May be a pipe, a pipeline, an open channel, an underdrain, or the like. Also, in the manhole,
In addition to ordinary manholes for connecting and managing multiple sewers, there are downstream end facilities such as the most upstream end point and sewage treatment plant.

The manhole data 35 shown in FIG. 1 exists in the sewage facilities, and the manholes m1, m2,.
This is data on ... Figure 3 shows manhole data 35
Shows the format. The manhole data 35 includes a vertex number 71, coordinates 305, and attributes 307.

Here, the vertex number 71 is a serial number assigned to identify all the manholes mi, and the coordinates 305 indicate the position coordinates of the manhole mi when the sewage equipment is photographed on the xy plane. Attribute 307 is manhole mi
Of construction year, repair company, type, material, etc.

The pipe data 45 shown in FIG. 1 is data relating to the pipes k1, k2,... Shown in FIG. 2, and FIG. 4 shows the format of the pipe data 45. Pipe data 45
Is composed of a side number 81, an upstream vertex coordinate 405, a downstream vertex coordinate 407, an attribute 409, and an intermediate coordinate sequence 411.

Here, the side number 81 is a serial number assigned to identify all the sewers ki. The upstream vertex coordinates 405 and the downstream vertex coordinates 407 are the coordinates of the upstream end point and the downstream end point of the sewer ki, and the attribute 409 indicates the pipe type, diameter, and length of the sewer.

The intermediate coordinate sequence 411 is the coordinates of the starting point and the ending point of the sewer, and the coordinates of a curved point when the sewer is bent. In the tube data 45, the upstream vertex coordinates 405 and the downstream vertex coordinates 407 match the coordinates of the start point or the end point of the intermediate coordinate sequence 411.

Next, a method for clarifying the connection relationship between the upstream side and the downstream side of the sewer ki and the manhole mi shown in the example of the sewage piping diagram 31 in FIG. 2 will be described. FIG. 5 is a flowchart of a process for obtaining the connection relationship between the manhole mi and the sewer ki from the manhole data 35 and the pipe data 45.

The manhole data 35 of the manhole mi is read in an arbitrary order, and an ordered vertex record 51 and a vertex list 53 are created (step 501). Next, the pipe data of the sewer ki is read in an arbitrary order, and the ordered side record 55 and the side list 57 are created (step 502).

A vertex record 51 is created for the upstream vertex and the downstream vertex of the sewer ki, and added to the vertex list 53 (step 503), and the upstream vertex and the downstream vertex and the sewer ki in the side list 57 are identified. (Step 504).

Next, each manhole m in the vertex list 53
When i and the upstream vertex or the downstream vertex are overlapped, they are integrated into the manhole mi and the outflow / inflow data in the vertex list 53 and the edge list 57 are readjusted. (Step 5
05) Hereinafter, the processing of each step shown in FIG. 5 will be described in detail.

[0027] Step 501 FIG. 6 is a diagram showing the format of the vertex record 51, Fig. 7 is a diagram illustrating a vertex list 53. The vertex record 51 and the vertex list 53 are created based on the manhole data 35, and FIG. 8 is a flowchart showing a method of creating the vertex list 53.

The file of the manhole data 35 is opened (step 801), and the top address of the vertex list is confirmed (step 802). Here, the head address of the vertex list 53 is assumed to be LML. Next, the first manhole data 35 is read (step 803), and the vertex record 51 and the vertex list 53 are created (step 80).
4).

The vertex record 51 shown in FIG. 6 has a vertex number 71, coordinates 305, attribute 511, dummy flag 513,
It consists of a pointer 514 and an extraction flag 79. Vertex number 71, coordinates 305, attribute 511 in vertex record 51
, The necessary data of the vertex number 71, the coordinates 305, and the attribute 307 in the manhole data 35 are read and stored. In the vertex record 51, the attribute data 511 may be omitted.

The dummy flag 513 is for distinguishing between a true manhole and a virtual manhole described later. The vertex record 51 created from the manhole data 35 is a real true manhole m.
Since the data is related to i, the dummy flag 513 is set to “0”, for example.

In the pointer 514, the first outflow side 73 is the first of the drain pipes flowing out of the manhole, and the first inflow side 75 is the first of the drain pipes flowing into the manhole. Are indicated by the head address where the data exists. At this stage, the first
Since the outflow side 73 and the first inflow side 75 are unknown, they are respectively set to “null”.

A series of vertex numbers 71 are assigned to the true manholes m1, m2,... Next input vertex 77
Is the head address of the vertex record 51 of the vertex number 71 next to the vertex. That is, assuming that the data length of the vertex record 51 is LM, the “next input vertex 77i” in the i-th vertex record 51 is the head address of the (i + 1) -th vertex, and is “LML + iLM”.

Next, the vertex, that is, the i-th vertex record 51 is stored in the address "LML + (i-1) LM" (step 805), and i is stored as the true manhole number nM (step 806). It is determined whether or not the manhole data 35 ends (step 807). If the manhole data 35 exists, i is incremented by one (step 80).
9) The processing from step 804 to step 807 is repeated. When there is no more manhole data 35 to be read, nM is stored as the true manhole number (step 808).

With the above processing, the vertex record 5
1 and the vertex list 53 shown in FIG. 7 are created. For example, in the sewage piping diagram 31 shown in FIG.
Assuming that the creation of the vertex record 51 starts from 1, the top address 703 of the vertex record 51a is “LML”. In FIG. 7, the head address 703 is shown for convenience, and the top address 70
3 is not included.

In the vertex record 51a, the vertex number 7
1a is “m1”, the first outflow side 73a and the first inflow side 75a are “null”, and if the next vertex number is manhole m2, the next input vertex 77a is manhole m
The top address “LML + LM” in which the vertex record 51b for No. 2 is stored. In the following description,
For example, “m” is input to the input vertex 77a as pointer data.
When "2" is entered, it indicates the address at which the vertex record for the manhole m2 is stored.

Next, a vertex record 51b relating to the manhole m2 is similarly created and stored at the address "LML + LM". Hereinafter, vertex records 51 for manholes m3,.
3 is created. Therefore, when there are nM true manholes, the vertex record 51nM has the address “LML”.
+ (NM-1) LM ".

Steps 502, 503, and
Flop 504 then creates an edge records 55 from the tube data 45, further, a method for creating a virtual vertex record 51. FIG. 9 is a diagram showing the side record 55, and FIG.
Is a flowchart showing a method for creating the edge record 55 and the vertex record 51 for the virtual manhole.

The file storing the pipe data 45 is opened (step 1001), and the file of the vertex list 53 is opened (step 1002). Next, the start address of the side list 57 is confirmed. Hereinafter, description will be made assuming that the head address of the side list is “LLL”. Substitute 1 for i (step 1004), and read out the i-th tube data 45 (step 1005). Data necessary for creating the side data 55 is extracted from the tube data 45 (step 100).
6), create an edge record 55 (step 100)
7).

As shown in FIG. 9, the side record 55 includes a side number 81, an upstream vertex coordinate 405, and a downstream vertex coordinate 40.
7, an attribute 409, a pointer 410, and an extraction flag 99. Among them, the data of the side number 81, the upstream vertex coordinates 405, the downstream vertex coordinates 407, and the attribute 409 are data common to the pipe data 45. In the side record 55, the data of the attribute 409 may be omitted.

The pointer 410 indicates the start address where the data of the next inflow side 85, the next outflow side 83, the next input side 87, the upstream vertex 89, and the downstream vertex 91 are stored. Assuming that the data length of the side record 55 is “LL”, the next outflow side 83 and the next inflow side 85 are “null”, the next input side 87 is “LLL + iLL”, and the upstream vertex 89 is “LML + (nM−1 + 2i). -1) LM ”, and the downstream vertex 91 is“ LML + (nM−1 + 2i) LM ”. The side record thus created, that is, the i-th side record 55 is stored at the address “LLL + (i−1) LL”.

Next, the vertex on the upstream side of the side is regarded as a virtual manhole, a vertex record 51 is created, and the created vertex record 51 is stored in the address “LML +
(NM-1 + 2i-1) LM "(step 1
008).

At this time, the side corresponds to the first outflow side for the upstream vertex. Therefore, in the pointer of the vertex record 51, the first outflow side 73 has the address “LLL + (i−
1) LL ". Further, the first inflow side 75 is “null
l ", the next input vertex 77 has the address" LML + (nM-
1 + 2i) LM ". In the vertex record 51 created for the virtual manhole, the dummy flag 50
3 is set to, for example, “1” to distinguish it from a true manhole.

Next, the downstream vertex of the side is also regarded as a virtual manhole, a vertex record 51 is created, and the created vertex record 51 is stored in the address “LM” of the vertex list 53.
L + (nM-1 + 2i) LM "(step 1
009).

At this time, for the downstream vertex, this side corresponds to the first inflow side, so that the first inflow side 75 in the pointer of the vertex record 51 has the address “LLL + (i
-1) LL ”. Further, the first outflow side 73 is “null
l ", the next input vertex 77 has the address" LML + (nM-
1 + 2i + 1) LM ".

Next, it is determined whether or not the pipe data 45 has ended (step 1010). If the pipe data 45 still exists, i is incremented by one (step 1011), and the pipe data 4
Steps 1005 to 10 until 5 is exhausted.
Repeat the work up to 10.

FIG. 11 is a schematic diagram of the sewage piping diagram 31.
As shown in FIG. 11, the upstream vertices of the sewers k1, k2, ... are ku1, ku2, ..., and the downstream vertices are k.
.., and the vertices are regarded as virtual manholes, and an edge list 57 and an additional vertex list 53 are created. FIG. 12 is a diagram showing the contents of the side list 57 and the vertex list 53 created according to the sewage piping diagram 31 shown in FIG.

According to the flowchart of FIG.
To read the pipe data 45 of the pipe k1. According to step 1007 in FIG. 10, a side record 55a relating to the sewer k1 is created. Hereinafter, a side number or a vertex number is written in the pointer of the side record 55a for convenience, and the written side number or vertex number indicates an address where the record is stored.

As shown in FIG. 12, in the side record 55a, the side number 81a is "k1", the next inflow side 83a and the next outflow side 85a are "null", and the next input side 87a.
Is "k2", the upstream vertex 89a is "ku1", and the downstream vertex 91a is "kd1". Edge record 5 created
In 5a, the head address 705 is stored in “LLL”.
In FIG. 12, "null" is indicated by a blank. The head address 705 is shown for convenience, and is not included in the side record 55.

Next, according to step 1008 in FIG. 10, a vertex record 51d relating to the upstream vertex ku1 of the sewer k1 is created. In the vertex record 51d, the first
Outflow side 73d becomes “k1”, and the first inflow side 75d
Is “null”, and the next input vertex 77d is “kd1”. The created vertex record 51d has the start address “LML + (nM−1 + 2i−1) LM”, that is, the address “LM” if the number of true manholes nM = 3 and i = 1.
L + 3LM ".

Next, according to step 1009 in FIG. 10, a vertex record 51e relating to the downstream vertex kd1 of the pipe k1 is created. In the vertex record 51e, the first
Of the first inflow side 7e becomes “null”.
5e is “k1” and the next input vertex 77e is “ku2”. The created vertex record 51e has the start address "LML + (nM-1 + 2i) LM", that is, if the number of true manholes nM = 3 and i = 1, the address "LML +
4LM ".

As described above, the sewers k2, k2 shown in FIG.
.., K10, the side records 55b, 55c,
, 55j and the upstream and downstream vertices of the sewers k2, k3,..., K10
f,..., 51w are similarly created and stored. Thus, the side list 57 and the vertex list 53 shown in FIG. 12 are created.

Step 505 Next, a description will be given of a method of obtaining the outflow / inflow relationship of the sewer based on the created vertex list 53 and the side list 57. FIG.
3, FIG. 14 and FIG. 15 are flow charts showing a method of obtaining the inflow / outflow relationship of a sewer by searching for an overlap between a true manhole and a virtual manhole. FIG. 16 is a diagram showing the side list 57 and the vertex list 53 of the sewage piping diagram 31 in which the outflow / inflow relationship is clarified according to the flows of FIGS. Hereinafter, the processing will be described using the sewage piping diagram shown in FIG. 11 as an example.

The files of the vertex list 53 and the side list 57 are opened (steps 1301 and 1302). i
= 1 (step 1303), and the coordinates (Xi, Yi) are extracted from the i-th vertex record 51 of the vertex list 53 (step 1304).

Next, the true manhole number nM is substituted for ii (step 1305), and the coordinates (X, Y) of the ii-th, ie, the last vertex of the true manhole, are extracted (step 1306), and the coordinates ( X, Y) and coordinates (Xi,
Yi) is determined (step 130).
7). That is, it is checked whether the i-th vertex is the last true manhole.

If it is determined in step 1307 that the coordinates of the vertices do not match, ii + 1 is substituted for ii (step 1313), and it is determined whether or not the next vertex record 51 ends (step 1314). If there is a vertex record in the first step 1314, that is, there are vertex records related to virtual manholes in addition to nM true manholes.

Therefore, returning to step 1306, the coordinates of the virtual manhole are extracted, and the coordinates of the i-th true manhole and the coordinates of the ii-th virtual manhole are compared (step 1307). Proceeding to 1313, it is determined whether or not the vertex record 51 of the next ii-th virtual manhole exists (step 1314). Thus, in step 1307, i
The i-th vertex coordinate is the coordinate of the i-th true manhole (X
i, Yi) until the operation is repeated.

For example, in the vertex list 53 of FIG. 12, the coordinates are extracted from the vertex record 51a of the vertex m1 with i = 1. Further, since the true manhole number nM is "3", the vertex coordinates are extracted from the vertex record 51c of the vertex m3, which is the third vertex, and compared with the coordinates of the vertex m1.

Naturally, since the coordinates of the vertex m3 and the vertex m1 are different, the coordinates are extracted from the vertex record 51d of the fourth vertex ku1 as ii = 4 and compared with the coordinates of the vertex m1. Since the coordinates of vertex ku1 and vertex m1 are different, i
The vertex record 51e of the fifth vertex kd1 with i = 5
Is extracted from the coordinates and compared with the vertex m1. As can be seen from FIG. 11, the coordinates of the vertex kd1 and the vertex m1 match.

If it is determined in step 1307 that the coordinates of the true manhole and the virtual manhole coincide, the first outflow side 73 in the ii-th vertex data 51 is determined.
It is determined whether or not there is data in the first inflow side 75 (step 1308).

For example, since the coordinates of the vertex kd1 and the vertex m1 coincide, it is determined which of the first outflow side 73e and the first inflow side 75e of the vertex record 51e of the vertex kd1 has data. In this case, the data is the first outflow side 75
e.

In step 1308, the first outflow side 73
, It is determined whether the i-th first outflow side 73 is “null” (step 1309). In step 1309, the first outflow side 7
If 3 is not “null”, the process proceeds to step 1501 in FIG. 15 as described later.

Next, when the first outflow side 73 is "null" data, the data of the ii-th first outflow side 73 is put into the i-th first outflow side 73, and further the first outflow side 73 is set. 7
The upstream vertex 89 of the side record 55 corresponding to the data (sewer ki) held in No. 3 is set as the i-th vertex (step 1310). That is, the address at which the vertex record of the i-th vertex is held is entered in the upstream vertex 89 of the side record 55 of the sewer ki.

If it is determined in step 1308 that there is data on the first inflow side 75, it is determined whether the i-th first inflow side 75 is "null" (step 1312). If the first inflow side 75 is not “null” in step 1311, the process proceeds to step 1401 in FIG. 14 as described later.

Next, when the first inflow side 75 is "null" data, the data of the ii-th first inflow side 75 is put into the i-th first inflow side 75, and the first inflow side is further entered. 7
The downstream vertex 91 of the side record 55 corresponding to the data (conduit ki) held in No. 5 is set as the i-th vertex (step 1312). That is, the downstream vertex 91 of the side record 55 of the sewer ki contains the address at which the vertex record of the i-th vertex is held.

Therefore, in the case of the vertex kd1, the first outflow side 7
5e has data "k1" and the first outflow side 75a of the vertex record 51a of the vertex m1 is "null".
As shown in FIG. 16, the first outflow side 73a of the vertex m1 is defined as "k1". Further, the downstream vertex 91a is changed to “m1” in the side record 55a of “k1”.

Next, ii + 1 is substituted for ii (step 1313), and it is determined whether the vertex record 51 in the vertex list 53 is the end (step 1314). If the vertex record 51 still exists, , Step 1
Returning to 306, the above operation is repeated. That is, it is determined whether or not the coordinates of the i-th vertex and the coordinates of all the virtual manholes added to the vertex list are the same, and if they match, the above integration processing is performed.

For example, in the example of FIG.
The vertex record 51f of the sixth vertex ku2 with i = 6
Are extracted from the coordinates and compared with the coordinates of the vertex m1. Since the coordinates of the vertex m1 and the vertex ku2 match and the data “k2” exists on the first outflow side 73f of the vertex record 55f of the vertex ku2, the process proceeds to step 1309.

At this time, since the first outflow side 73a of the vertex record 51a of the vertex m1 is "null", the first outflow side 73a of the vertex m1 is set to "k2" as shown in FIG. Is changed to "m1" in the upstream vertex 89b in the side record 55b of "."

Next, in step 1311, if the i-th first inflow side 75 is not "null", the processing is performed according to the flowchart shown in FIG. That is, the processing shown in FIG. 14 is performed when there are a plurality of inflow sides at the i-th vertex. The side record 55 corresponding to the i-th first inflow side 75 is taken out (step 140).
1). Next, the side record number 81 of the ii-th first inflow side 75 is stored (step 1402).

The next inflow side 83 of the i-th side record 55
Determines whether it is "null" (step 14).
03), if it is “null”, step 1 is added to the next inflow side 83 of the side record 55 read in step 1401.
The side record number 81 stored in 402 is input and stored (step 1405). Further, the i-th vertex, that is, the true manhole mi is input to the downstream vertex 91 in the side record 55 of the ii-th first inflow side 75 and stored (step 1406).

In step 1403, if the next inflow side 83 of the i-th side record 55 is not “null”, the side record 55 of the side written therein is extracted (step 1404), and the process returns to step 1402. After storing the edge records in step 1406, FIG.
The process returns to step 1313 shown in FIG.

For example, the process shown in FIG. 13 is continued in the vertex list 53 shown in FIG. 12, and the vertex kd3 is extracted as the ii-th vertex. The coordinates of the vertex m1 and the vertex kd3 match, and data is present on the first inflow side 75j of the vertex kd3 (step 1308).
Since the data “k1” also exists in “a” as described above, the process proceeds to the processing in FIG.

At step 1401, the first vertex m1
The edge record 55a of the data “k1” of the inflow side 75a is extracted, and the data “k” of the first inflow side 75j of the vertex kd3 is extracted.
Since the next inflow side 83a of the side record 55 of "k1" is "null", the data "k3" stored earlier is input and stored therein. Further, in the side record 55c of the side “k3”, the downstream vertex 91c
Is changed to “m1” and stored. Thereafter, the process returns to step 1313 shown in FIG.

Next, in step 1309, if the i-th first outflow side 73 is not "null", processing is performed according to the flowchart shown in FIG. That is, the process shown in FIG. 15 is performed when a plurality of outflow edges exist at the i-th vertex. The edge record 55 corresponding to the i-th first outflow edge 73 is extracted (step 150).
1). Next, the side record number 81 of the ii-th first outflow side 73 is stored (step 1502).

Outflow side 85 next to i-th side record 55
Is "null" (step 15)
03), if it is “null”, the next outflow side 85 of the side record 55 read out in step 1501
The side record number 81 stored in 502 is input and stored (step 1505). Further, the i-th vertex, that is, the true manhole mi is input to the upstream vertex 89 in the edge record 55 of the ii-th first outflow side 73 and stored (step 1506).

In step 1503, if the outflow side 85 next to the i-th side record 55 is not "null", the side record 55 of the side described therein is taken out (step 1504), and the process returns to step 1502. After storing the edge records in step 1506, FIG.
The process returns to step 1313 shown in FIG.

For example, the processing described above is further continued according to FIG. 13, and the vertex ku4 is extracted as the ii-th vertex. The coordinates of the vertex m1 and the vertex ku4 match, and the vertex ku4
There is data on the first outflow side 73k (step 130).
8) Since the data “k2” already exists in the first outflow side 73a of the vertex m1 as shown in FIG.
In, the process proceeds to the process of FIG.

In step 1501, the first vertex m1
The edge record 55b of the data “k2” of the outflow edge 73a is extracted. Next, the data “k4” of the first outflow side 73k of the vertex ku4 is stored, and the next inflow side 83a of the side record 55b of “k2” is “null”. Enter “k4” and save.
Further, in the side record 55d of the side "k4", the upstream vertex 89d is changed to "m1" and stored. Then, FIG.
The process returns to step 1313 shown in FIG.

The operation described above is repeated until i becomes equal to the true manhole number nM. That is, the coordinates of the true manhole and the coordinates of the virtual manhole are compared, and the inflow / outflow relationship of the sewer is clarified by integrating the duplicate manholes, and the side list 57 and the vertex list 53 as shown in FIG. 16 are obtained.

Using the side list 57 and the vertex list 53 shown in FIG. 16, for example, the outflow / inflow relationship of a pipe connected to the manhole m1 is confirmed. Vertex data 5 of manhole m1
1a, the first outflow side 73a of the manhole m1 is “k
2 "that the first inflow side 75a is" k1 ".

Next, the outflow side 85b next to the side record 55b of the sewer "k2" is "k4", and the sewer "k2"
The next inflow side 83a of the side record 55a of "1" is "k3".
It turns out that it is. Thus, in the manhole m1, the sewers "k1" and "k3" flow in, and the sewers "k2",
It is required that “k4” flows out.

Next, an edge list 57 as shown in FIG.
A method of performing upstream / downstream tracing using the vertex list 53 will be described. For example, a case will be described as an example in which foreign matter is mixed into the manhole m1 of the sewage piping diagram 31 shown in FIG.

FIG. 17 is a flowchart showing downstream tracking processing. The files of the side list 57 and the vertex list 53 are opened (step 1701). Therefore, FIG.
The files of the side list 57 and the vertex list 53 shown in FIG. A side or a vertex serving as a base point of tracking is designated and input (step 1702). A side or a vertex is input by a vertex number, a side number, coordinates, or by pointing a position on a computer display with a mouse or the like. For example, the terminal computer 3 shown in FIG. 1 inputs that the manhole m1 is the starting point.

Next, it is determined whether the starting point is a side or a vertex (step 1703). If the starting point is a vertex, the edge record 55 of the first outflow side 73 of the vertex is extracted (step 1704), and the data of the outflow side 85 following the first outflow side 73 is “null”. It is determined whether or not it is (step 1705). If the starting point is a side in step 1703, the process directly proceeds to step 1705. The processing after step 1703 is performed on the host computer 3 shown in FIG.

For example, the manhole m input as the starting point
Since 1 is a vertex, the side record 55b of the data "k2" of the first outflow side 73a of the vertex m1 is taken out, and it is determined whether or not the data of the next outflow side 85b is "null".

If the data of the next outflow side 85 is not "null" in step 1705, the data of the next outflow side 85 is stored in the stacker (step 1706), and the extraction flag of the side is set to "on". (Step 1707).
Here, the stacker is an internal memory or the like. Step 1
If the data of the next outflow side 85 is “null” in 705, the process directly proceeds to step 1707.

For example, the manhole m input as the starting point
Since 1 is a vertex, the side record 55b of the data “k2” of the first outflow side 73a of the vertex m1 is extracted, and the data “k4” exists in the next outflow side 85b.
Is stored in the stacker, and the extraction flag 99 of the relevant side “k2” is set to “ON”, for example, “1”.

Next, the record of the vertex on the downstream side of the side is extracted (step 1708), and the extraction flag of the vertex is turned on (step 1709). Then, the data of the first outflow side 73 of the vertex is extracted (step 171).
0), it is determined whether or not the data of the first outflow side 73 is “null” (step 1711).

If the data of the first outflow side 73 is "null", it is determined whether or not there is data in the stacker (step 1712). If there is data in the stacker, the edge data is taken out (step 1713),
It returns to step 1705. If the data of the first outflow side 73 is “null”, the process ends.

For example, the extraction flag of the side “k2” is set to “1”, the data “m2” of the downstream vertex 91b of “k2” is extracted, and the extraction flag 79 is set to “1” in the vertex record 51b. , It is confirmed that the data of the first outflow side 73b is not “null” and the data “k6” exists.

Next, returning to step 1705, "k6"
Of the outflow side 85f is stored in the stacker, and the corresponding side "k7"
The extraction flag of “6” is set to “1”. Since the data of the downstream vertex 91f of “k6” is “null”, the data of the first outflow side 73 in step 1711 is also “null”.
1 ", and the same processing is performed on the data stored in the stacker.

At this time, "k4" and "k
7 is stored, and each extraction flag is set to “1”. Note that the downstream vertex 9 of “k4” and “k7”
Since the data of 1 and the next outflow side 73 at the vertex are both “null”, the processing is terminated. Thus, according to the downstream tracking flow, when foreign matter enters the vertex m1, the sides k2, k4, k6, k7 and the vertex m2 are extracted.

The upstream tracking is almost the same as in FIG. That is, steps 1704 and 171
“First inflow side 75” instead of “first outflow side 73” at “0”, and “next inflow side 83” instead of “next outflow side 85” at steps 1705 and 1706.
If it is changed, it will be a method of upstream tracking.

The sides and vertices extracted by the upstream / downstream tracing as described above are presented to the worker at a glance by changing the color on the display of the host computer 3 or the terminal side computer 5 shown in FIG. Is possible.

According to the present embodiment, when the starting point is designated by the terminal-side computer 5 shown in FIG. 1, all the work and tracking work shown in FIG. 5 are performed in the host computer 3, but at this time, the work is performed by the host computer. The tracking work is performed very quickly because it is performed on the memory of No. 3. Therefore, the host computer 3 only needs to hold the manhole data 35 and the tube data 45.

Further, in step 503 shown in FIG. 5, by considering the vertices on the upstream side and the downstream side with respect to all pipes as virtual manholes, a search can be performed even if there is a manhole that is not registered in the true manhole. It is possible.

Further, according to the present embodiment, when there is a change or addition in the sewer or manhole, it is only necessary to change or add the pipe data 45 or manhole data 35 stored in the database 7. Easy to manage. Further, even if the terrain data 11 shown in FIG. 1 is divided and managed for each area, the effect of the present embodiment does not change.

In this embodiment, after the vertex list 53 and the side list 57 including the manholes m1, m2,... And the sewers k1, k2,. ……… and the top vertex ku
1, ku2,..., Downstream vertex kd1, kd2,.
And the sewers k1, k2, ...
.. May be performed each time data is created.

In this embodiment, the vertex data 51a, 51b,... Of the manholes m1, m2,.
The data of the next input vertices 77a, 77b,... Of the manhole data 35 is the same as that of the manhole data 35. However, another order may be determined. Sewer k1, k2, ...
The same applies to...

Also, in the present embodiment, the manhole data 35 and the pipe data 45 have been described as being already stored in the database. However, the connection relation is sequentially input along with the vertex number or the side number from a network diagram or the like. The vertex list 53 and the edge list 57 may be created.

[0101]

As described above in detail, according to the present invention, in a network having a direction composed of vertices and sides such as water supply and sewage, the upstream and downstream tracing work can be efficiently performed from the data of vertices and sides. It can be performed.

[Brief description of the drawings]

FIG. 1 is a diagram showing a network search system 1 according to an embodiment of the present invention.

FIG. 2 is a schematic diagram of a sewage piping diagram (manhole sewer graph) 31.

FIG. 3 is a diagram showing a data format of manhole data 35;

FIG. 4 is a diagram showing a data format of tube data 45;

FIG. 5 is a flowchart showing a method for obtaining a connection relationship of a sewer.

FIG. 6 is a diagram showing a data format of a vertex record 51;

FIG. 7 is a diagram showing a vertex list 53;

FIG. 8 is a flowchart showing a method of creating a vertex list 53 from manhole data 35;

FIG. 9 is a diagram showing a data format of an edge record 55;

FIG. 10 is a flowchart showing a method of creating a side list 57;

FIG. 11 Sewage piping diagram (manhole sewer graph) 31
Schematic diagram of

FIG. 12 is a diagram showing contents of a vertex list 53 and a side list 57 including a virtual manhole.

FIG. 13 is a flowchart showing a method of creating a vertex list 53 and a side list 57 that clarify the outflow / inflow relationship of a sewer.

FIG. 14 is a flowchart showing a method of creating a vertex list 53 and an edge list 57 when a plurality of outgoing edges exist.

FIG. 15 is a flowchart illustrating a method of creating a vertex list 53 and an edge list 57 when a plurality of inflow edges exist.

FIG. 16 is a diagram showing the contents of a vertex list 53 and a side list 57 that clarify the outflow / inflow relationship of a sewer.

FIG. 17 is a flowchart showing downstream tracking processing;

[Explanation of symbols]

 1 Network search system 1 3 Host computer 5 Terminal computer 7 Database 15 CD-ROM 35 Manhole data 45 Pipe data 51 Vertex record 53 Vertex list 55 … Side record 57 …… side list

Claims (36)

[Claims] 1. A network in which a plurality of vertices are connected by an edge, a database having edge data having at least data indicating coordinates of both ends of the edge and a flow direction, and vertex data having coordinates of the vertex. Means for creating a vertex list indicating link information to edges connected to the vertices; means for creating an edge list indicating link information to upstream or downstream vertices of each edge; Means for adding to the vertex list; if one end on the upstream or downstream side of the edge data added to the vertex list matches the vertex, link information of a side connected to the vertex is set as the relevant edge; Means for setting link information to an upstream vertex or a downstream vertex as the vertex. 2. A network in which a plurality of vertices are connected by an edge, a database having edge data having at least data indicating coordinates of both ends of the edge and a flow direction, and vertex data having coordinates of the vertex. Means for creating a vertex list indicating link information to the outflow side of each vertex; means for creating a side list indicating link information to the downstream vertex of each side; and a vertex list including both ends of the side data Means for adding, if one end on the upstream side of the edge data added to the vertex list matches the vertex, the link information of the outgoing edge of this vertex is set as the relevant edge, and link information to the upstream vertex of this edge is set. And a means for setting the vertex as the vertex. 3. A network in which a plurality of vertices are connected by an edge, wherein the database has edge data having at least data indicating coordinates of both ends of the edge and a flow direction, and vertex data having coordinates of the vertex. Means for creating a vertex list indicating link information to the inflow side of each vertex; means for creating a side list indicating link information to the upstream vertex of each side; and a vertex list containing both ends of the side data Means for adding, if one end on the downstream side of the edge data added to the vertex list matches the vertex, the link information of the inflow edge of this vertex is set as the relevant edge, and the link information to the downstream vertex of this edge is set. And a means for setting the vertex as the vertex. 4. The network tracking data generation device according to claim 1, further comprising: means for holding the edge list, the vertex list, and the link information. 5. The network tracking data generating apparatus according to claim 2, further comprising: a unit for holding the edge list, the vertex list, and the link information. 6. The network tracking data generating apparatus according to claim 3, further comprising: a unit for holding the edge list, the vertex list, and the link information. 7. A network tracking device for tracking a network using data created by the network tracking data creation device according to claim 2, wherein: (a) when a certain vertex is specified, the outgoing edge of the vertex list (B) For the calculated outflow edge, calculate the downstream vertex for this edge by referring to the link information to the downstream vertex in the edge list. (C) A network tracking device characterized by performing downstream tracking by repeating (a) and (b). 8. A network tracking device for tracking a network using data created by the network tracking data creation device according to claim 3, wherein: (a) when a certain vertex is specified, the data is sent to the inflow edge of the vertex list; (B) For the calculated inflow edge, calculate the upstream vertex for this edge by referring to the link information to the upstream vertex in the edge list. (C) a network tracking device for performing upstream tracking by repeating (a) and (b). 9. The network tracking data creating apparatus according to claim 1, wherein the side includes a pipeline, an open channel, a culvert, an electric wire, and a transport route. 10. The network tracking device according to claim 7, wherein the calculated outgoing edge and the downstream vertex are displayed in different colors. 11. The network tracking apparatus according to claim 8, wherein the calculated inflow side and the upstream vertex are displayed in different colors. 12. The network tracking device according to claim 7, further comprising superimposing and displaying terrain data. 13. A network having a plurality of vertices connected by an edge, comprising: edge data having at least data indicating the coordinates of both ends of the edge and a flow direction; and vertex data having coordinates of the vertex. A step of creating a vertex list indicating link information to an edge connected to each of the vertices; a step of creating an edge list indicating link information to an upstream or downstream vertex of each of the sides; A step of adding to the vertex list, and if one end on the upstream or downstream side of the edge data added to the vertex list matches the vertex, link information of a side connected to the vertex is set as the relevant side; Using the link information to the upstream vertex or the downstream vertex of the network as the relevant vertex. 14. A network in which a plurality of vertices are connected by an edge, a database having edge data having at least data indicating coordinates of both ends of the edge and a flow direction, and vertex data having coordinates of the vertex. A step of creating a vertex list indicating link information to the outflow side of each vertex; a step of creating a side list indicating link information to the downstream vertex of each side; and forming both ends of the side data into a vertex list. The step of adding, if one end on the upstream side of the edge data added to the vertex list matches the vertex, the link information of the outflow edge of this vertex is regarded as the relevant edge, and the link information to the upstream vertex of this edge is set. A method for creating network tracking data, comprising: 15. A network having a plurality of vertices connected by an edge, comprising: edge data having at least data indicating coordinates of both ends of the edge and a flow direction; and a vertex data having coordinates of the vertex. A step of creating a vertex list indicating link information to the inflow side of each vertex; a step of creating a side list indicating link information to the upstream vertex of each side; and a vertex list including both ends of the side data. The step of adding, if one end on the downstream side of the edge data added to the vertex list matches the vertex, the link information of the inflow edge of this vertex is set as the relevant edge, and the link information to the downstream vertex of this edge is set. A method for creating network tracking data, comprising: 16. The network tracking data generating method according to claim 13, further comprising a step of retaining the edge list, the vertex list, and the link information. 17. The network tracking data generation method according to claim 14, further comprising a step of holding the edge list, the vertex list, and the link information. 18. The network tracking data generating method according to claim 15, further comprising a step of holding the edge list, the vertex list, and the link information. 19. A network tracking method for tracking a network using data created by the network tracking data creation method according to claim 14, wherein: (a)
When a certain vertex is designated, the outflow edge for this vertex is calculated by referring to the link information to the outflow edge in the vertex list. (B) For the calculated outflow edge, the link information to the downstream vertex in the edge list (C) calculating a vertex on the downstream side with respect to this side, and performing (c) downstream tracing by repeating (a) and (b). 20. A network tracking method for tracking a network using data created by the network tracking data creation method according to claim 15, wherein: (a)
When a certain vertex is specified, the inflow edge for this vertex is calculated by referring to the link information to the inflow edge of the vertex list. (B) For the calculated inflow edge, the link information to the upstream vertex of the edge list And (c) performing upstream tracking by repeating steps (a) and (b). 21. The side includes a conduit, an open channel, a culvert, an electric wire,
14. The method according to claim 13, further comprising a transportation route.
5. The method for creating network tracking data according to any one of 5. 22. The network tracking method according to claim 19, wherein the calculated outgoing edge and the downstream vertex are displayed in different colors. 23. The network tracking method according to claim 20, wherein the calculated inflow side and upstream vertex are displayed in different colors. 24. The network tracking method according to claim 19, further comprising superimposing and displaying terrain data. 25. A network having a plurality of vertices connected by an edge, comprising: edge data having at least data indicating coordinates of both ends of the edge and a flow direction; and a vertex data having coordinates of the vertex. Means for creating a vertex list indicating link information to edges connected to the vertices; means for creating an edge list indicating link information to upstream or downstream vertices of each edge; Means for adding to the vertex list; if one end on the upstream or downstream side of the edge data added to the vertex list matches the vertex, link information of a side connected to the vertex is set as the relevant edge; Means for setting the link information to the upstream vertex or the downstream vertex to the vertex, and a network tracking data generating device comprising:
A recording medium on which a program for causing a computer to function is recorded. 26. A network in which a plurality of vertices are connected by an edge, a database having edge data having at least data indicating coordinates of both ends of the edge and a flow direction, and vertex data having coordinates of the vertex. Means for creating a vertex list indicating link information to the outflow side of each vertex; means for creating a side list indicating link information to the downstream vertex of each side; and a vertex list including both ends of the side data Means for adding, if one end on the upstream side of the edge data added to the vertex list matches the vertex, the link information of the outgoing edge of this vertex is set as the relevant edge, and link information to the upstream vertex of this edge is set. And a means for defining the vertex as a network tracking data creation device comprising:
A recording medium on which a program for causing a computer to function is recorded. 27. A network in which a plurality of vertices are connected by an edge, wherein the database includes edge data having at least data indicating the coordinates of both ends of the edge and a flow direction, and vertex data having the coordinates of the vertex. Means for creating a vertex list indicating link information to the inflow side of each vertex; means for creating a side list indicating link information to the upstream vertex of each side; and a vertex list containing both ends of the side data Means for adding, if one end on the downstream side of the edge data added to the vertex list matches the vertex, the link information of the inflow edge of this vertex is set as the relevant edge, and the link information to the downstream vertex of this edge is set. And a means for defining the vertex as a network tracking data creation device comprising:
A recording medium on which a program for causing a computer to function is recorded. 28. The recording medium according to claim 25, wherein:
A recording medium storing a program for causing a computer to function as a network tracking data creation device further comprising means for holding the edge list, the vertex list, and the link information. 29. The recording medium according to claim 26,
A recording medium storing a program for causing a computer to function as a network tracking data creation device further comprising means for holding the edge list, the vertex list, and the link information. 30. The recording medium according to claim 27, wherein:
A recording medium storing a program for causing a computer to function as a network tracking data creation device further comprising means for holding the edge list, the vertex list, and the link information. 31. Using the data created by the network tracking data creation device according to claim 26, (a) when a certain vertex is specified, the vertex list is referenced with reference to the link information to the outflow edge in the vertex list. (B) For the calculated outflow edge, calculate the downstream vertex for this edge by referring to the link information to the downstream vertex in the edge list, and (c) (a) to (a). A recording medium on which a program for causing a computer to function so as to perform downstream tracking by repeating b). 32. (a) When a certain vertex is designated by using the data created by the network tracking data creating apparatus according to claim 27, the link information to the inflow side of the vertex list is referred to, and (B) For the calculated inflow edge, with reference to the link information to the upstream vertex in the edge list, calculate the vertex on the upstream side with respect to this edge, and (c) (a) to (a). A recording medium that records a program that causes a computer to perform upstream tracking by repeating b). 33. The side is a conduit, an open channel, an underdrain, an electric wire,
26. The method according to claim 25, further comprising a transportation route.
8. The recording medium according to any one of 7. 34. The recording medium according to claim 31, wherein
A recording medium storing a program for causing a computer to function so as to display the calculated outflow side and downstream vertex in different colors. 35. The recording medium according to claim 32,
A recording medium on which a program for causing a computer to function is displayed so that the calculated inflow side and upstream vertex are displayed in different colors. 36. A storage medium according to claim 31, wherein a program for causing a computer to function so as to further display the terrain data is displayed.