KR20010056264A - Method of calculating optimum path in link oriented - Google Patents

Abstract

1. TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method for calculating a link center optimal path and a computer readable recording medium having recorded thereon a program for realizing the method.

2. The technical problem to be solved by the invention

The present invention is optimized by constructing optimized metadata by minimizing the amount of computation and data size by applying the link-centric operation method unlike the node-centric path operation method in consideration of the reality of the geographic information system data in the geographic information system (GIS). To provide a method for calculating a link center optimal path for calculating a path of a computer and a computer readable recording medium storing a program for realizing the method.

3. Summary of Solution to Invention

According to an aspect of the present invention, there is provided a method for calculating an optimal path in a geographic information system, comprising: a first step of distinguishing among roads among nodes linking a node and a next node to move from a node to a next node; A second step of minimizing the size of meta data for path calculation by assigning a common key to each node and a vertex of the link; And a third step of automatically finding a next connection link through an endpoint constituting the link based on the metadata whose size is minimized to calculate an optimal path.

4. Important uses of the invention

The present invention is used to calculate the optimal path in geographic information system.

Description

Method of calculating optimum path in link oriented}

According to the present invention, unlike the node-based path calculation method, the link-based operation method is applied in consideration of the reality of the geographic information system data in the geographic information system (GIS), thereby minimizing the amount of computation and the data size and constructing optimized metadata. The present invention relates to a method for calculating an optimal path at a link center capable of calculating an optimal path through a computer, and a computer readable recording medium storing a program for realizing the method.

As shown in Figs. 1A and 1B, the conventional optimal (shortest) path computation algorithm is centered at each node. In order to move from a certain point to an arbitrary point around these nodes, it is necessary to first determine whether it is possible to move to neighboring points.

Here, "1" is a node, "2" is a link connecting a node and a node, "3" is a bidirectional link to a node that can be connected around Node A, and "4" is B, C, and D. , E-nodes show bidirectional links that can be connected between nodes.

Here, the first stage of general optimal route calculation using a node is shown. This shows the process for creating links to randomly evicted nodes. And, it shows that there are several links that can reach the rest of the points at any point.

FIG. 2 shows the implementation of a linked list on computer memory for the link operation determined in FIGS. 1A and 1B.

As shown in FIG. 2, in order not to move to an unwanted node, an operation process for generating additional data and a link is required. Also, as the amount of data increases, the amount of time required for this operation increases.

FIG. 3 illustrates the remaining processes of finding an optimal path using the ones determined by FIGS. 1A and 1B and FIG. 2. In this process, since the link constructed as a node does not properly represent the position on the road, it is necessary to refer to separate data or this node key to get all vertices of the path from one node to another node. This indicates that the node is not suitable as a primary key.

As shown in FIG. 3. The connection between each node is composed of a certain data table, and matrix operation is performed through this. However, as the size of data increases in this operation, the operation increases exponentially in proportion to the square. In addition, the required amount of memory also increases proportionally. This means that it is not suitable for places that use atypical large data such as geographic information system.

Figure 4 shows that C is selected from among several paths C, D, and E that can now go from point B along the trunk once constructed. In particular, in the link method, when a link is selected, the next connection link is automatically determined, but in the case of a node, a connection point must be selected through individual nodes connected to a specific node each time.

In general, an optimal path calculation algorithm widely used is calculated based on a node. As the amount of data increases, a computational time increases rapidly. Therefore, various algorithms are being developed according to geometric elements and purpose of use. Especially in the case of geographic information systems, the data is very large and the structure of the data has many nonlinear elements, which makes it difficult to abstract the data. Falls and comes with realistic constraints.

Conventional node-centric algorithms are generated based on the graph theory of mathematics rather than the application of geographic information systems, and start from a one-dimensional point. However, in order to apply it in the field of geographic information systems, mathematical modeling from different angles is required.

By the way, in geospatial information system, the topological relationship can be determined not only by the node data indicating the position but also by one link model connecting two nodes. Assuming two units as minimum link, this is a two-dimensional mathematical model. Follow the links faithfully.

Therefore, by seeing these links as the most basic unit and approaching the alarm calculation problem, through the effective data abstraction and link-oriented algorithms, the problems of the existing methods are improved more effectively, and the cost reduction in constructing the road information data of the GIS system is induced. At the same time, a method for enabling a high speed algorithm is required.

In order to solve the problems described above, the present invention, in consideration of the reality of geographic information system data in a geographic information system (GIS) by applying a link-centric operation method unlike the node-based path operation method, the amount of calculation and data size It is an object of the present invention to provide a link-centered optimal path calculation method for calculating an optimal path through the construction of optimized metadata by minimizing the optimized data, and a computer-readable recording medium recording a program for realizing the method.

1A and 1B are explanatory diagrams showing a conventional node-centric path calculation method.

2 to 4 are explanatory diagrams showing problems of the conventional node-centric path calculation method.

5 is an exemplary configuration diagram of a hardware system to which the present invention is applied.

6 is an exemplary explanatory diagram of a method for calculating an optimal path using the characteristics of a topological structure and an object structure according to an embodiment of the present invention.

7 is a basic node and link configuration diagram for a node-centric path calculation algorithm used in the present invention.

8 is a diagram illustrating an embodiment of a metadata construction process required for a memory in a node-centric path calculation algorithm in an optimal path calculation method according to the present invention;

9 is a diagram illustrating an embodiment of a method for calculating a link center optimal path according to the present invention;

10 is a comparative explanatory diagram showing a difference between a link center optimal path calculating method and a node center path calculating optimal path calculating method according to an embodiment of the present invention;

* Explanation of symbols for the main parts of the drawings

11: central processing unit (CPU) 12: main memory

13: auxiliary memory device 14: output device

15: input device 16: register

In order to achieve the above object, the present invention relates to a method for calculating an optimal path in a geographic information system, wherein a node corresponds to a road among the links connecting the node and the next node to move from one node to the next. A first step of dividing; A second step of minimizing the size of meta data for path calculation by assigning a common key to each node and a vertex of the link; And a third step of automatically finding a next connection link through an endpoint constituting the link based on the minimized size of the metadata and calculating an optimal path.

In addition, the present invention provides a geographic information system having a processor, comprising: a function for distinguishing among roads among nodes linking a node and a next node to move from a node to a next node; Providing a common key to individual nodes and vertices constituting the link to minimize the size of meta data for path computation; And a computer-readable recording medium having recorded thereon a program for realizing a function of automatically finding the next link and calculating an optimal path through an end point constituting the link based on the metadata whose size is minimized. .

The present invention aims to minimize the data size and computation time required for the calculation of the optimal path by fully utilizing the characteristics of the geographic database system (DB).

To this end, the present invention provides a data abstraction and link-centric path calculation method, which improves the problems of the existing node-centric method, induces a cost reduction effect when constructing road data of a geographic information system, and at the same time, provides fast operation. Enable the algorithm. The cost reduction effect through the improvement of these algorithms is particularly suitable for various application fields that want to produce fast results. Especially, since these parts are provided in the form of independent modules, they can be easily combined with other applications. Can be.

As described above, the present invention is to improve the classical node-centric algorithm for calculating the optimal path by using the characteristics of the geographic information system road DB, it can bring a lot of time saving effect in calculating the optimal path through the link-centric algorithm.

Classical algorithms work through abstraction and mathematical modeling of data, which results in completely different results and execution times. In addition, when calculating the optimal path by applying classical techniques based on geographic information system data, it is a waste of a lot of time and money due to the problem of having to build additional information.

In general, each algorithm starts from the problem of finding a link connecting nodes (points), and in the GIS road DB, the link must mean a road that exists.

The present invention addresses these problems by using a two-dimensional link without using a one-dimensional node, and proposes an effective alternative using the features of the geographic information system DB, and implements it as a program. Thus, the present invention can be used to minimize the amount of meter data for path calculation to the abstraction and link center of data in order to extract the path when performing the optimal path calculation function based on a large amount of geographic information system DB.

The above objects, features and advantages will become more apparent from the following detailed description taken in conjunction with the accompanying drawings. Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

5 is an exemplary configuration diagram of a hardware system to which the present invention is applied and shows a basic hardware configuration of a general computer or a medium-large mainframe.

As shown in FIG. 5, in the hardware system to which the present invention is applied, a central processing unit 11 that controls and manages the overall operation of a computer, and a program to be executed in the central processing unit 11 are stored and executed. It is connected to the register 16, which is a temporary storage for caching the data of the highest priority among various kinds of data used, and the main memory 12, which stores it. A secondary storage device 13 to be placed or permanently stored, an input device (keyboard, mouse) 15 which basically inputs a user's request, and an output device (monitor, etc.) 14 to display results.

However, since the computer hardware environment having the configuration as described above is only a technique well known in the art, detailed description thereof will be omitted herein. However, the computing environment to which the present invention is applied in general computers and medium and large mainframes will be described in more detail. The general environment is as shown in (Table 1).

CPU Pentium II300 HDD 10.1G (UDMA 33), 7,2000 RPM Memory 512 Mbyte O / S Windows NT 4.0

By default, the CPU 11 uses a "Pentium II Core", so the hardware requires at least Pentium II.

The auxiliary memory device (HDD) 13 requires 7,200 RPM or more.

The main memory 12 varies depending on the size of the GIS DB, but requires at least 256 MB.

The operating system (OS) basically requires "Windows NT 4.0" or higher.

By adhering to the regulations of "ANSI", compatibility with UNIX and Source Level is considered.

Finally, the results are shown in Table 2 below, and the keyboard (input device) and the monitor (output device).

CPU Pentium II Deschutes 300 and above Memory SDRAM 256M for PC-100 Main board BX or higher (UDMA support) HDD AGP Support Card VGA Windows NT 4.0 + Service Pack 6.0 or later O / S Linux Kernel 2.3 or later (Change can be applied) Solaris 2.5.1 or later for x86

6 is an explanatory diagram showing a method for calculating an optimal path using the features of a topological structure and an object structure according to an embodiment of the present invention.

As shown in FIG. 6, the method for calculating an optimal path using the characteristics of the topological structure and the object structure includes a process of constructing meta-data (201) and an edge construction process using edges ( 202), the optimal path calculation process 203 may be divided.

As shown in FIG. 6, in the metadata construction process 201, meta data is generated using characteristics of specific data of interest in the entire database in order to process an operation on a road edge among a large amount of GIS data. Build the data.

Here, edge data is extracted from the generated GIS data by using a meta-data builder using various GIS tools or various independent modules. At this time, the extracted data is constructed in accordance with the sequential ASCII standard in consideration of compatibility, capacity, processing time, and the like, according to a certain law.

In this case, the intermediate output is considered to facilitate the access and application of other applications. ASCII files, in the form of this intermediate output, are provided in the same format that can be used regardless of operating system or platform. For this reason, it was chosen as the intermediate format.

An example of one module that controls this intermediate format, a module of the type pursued by the present invention is a Connected Node Builder. This accepts the fundamental concept of "Mil-STD-2047" but is completely different in form, application and application. Here, the derived result is applied to verify and guarantee the connectivity of the road data and at the same time, to provide the maximum convenience in the calculation of the optimal route, and the like.

A typical optimal path calculation involves obtaining a link between points (that is, building edges using edges) (202). Once passing through the data abstraction module, a link between a vector coordinate and a vector coordinate is called a link. The data abstraction is done in the form, which reflects the reality of GIS data. This reduces the number of entities of the entire target data, thereby improving speed and pre-processing the problem of having to evict the actual road, thereby providing flexibility in applying the optimal route calculation algorithm.

In addition, various weights can be imposed through this process, and the result of the imposed form is managed through an object called a linked list manager, which is designed to facilitate various applications and accesses through copying and creating objects. The preserved linked list can be directly used or applied later for the calculation of the optimal route.

The result of passing through the data abstraction module and the linked list manager is rearranged into an entire list through the edge list creator and stored as a result, so that the virtual road connection state is mounted in the virtual memory. Is complete.

The optimal path calculation process 203 is the same as the classical graph theory, but the object means the topology structure of the GIS.

In GIS, the definition of phase relationship is the most important.

If classical graph theory is to generate a graph by randomly connecting a certain node of a road, it must have a topological relationship to a two-dimensional structure along several connecting edges of actual road. One road edge has a topological structure of the relationship between adjacent roads.

By the way, in the data construction, this topological structure is constructed to pass only the already determined path. This is due to the reality of the GIS DB built on real world objects. This reality does not need to be taken into account since the answer to the question of where to go in the classical theory is already determined. This unique feature of GIS DB makes it easy to make judgments or conditions for other abstractions and various topological queries, and to create multidimensional other topological results.

In classical theory, the result of passing this question becomes a constant link or edge. This is an important motif in the present invention. For the data that has already been determined and constructed, it provides a new answer to whether it is possible to omit the algorithmic procedure to answer these questions.

The answer is in the current process of building GIS road data, indicating that there is no need to find a new route. Then, if the unit of operation is not a node but only a link order between a predetermined set of vectors, or if you create an abstraction algorithm containing geometric elements to look for (using the topology structure of the GIS), the time and cost of this problem can be reduced. You can reduce it considerably.

After all this, the output of the final optimal route calculation is output.

Now, the link center optimal path calculation method is as follows.

First, an algorithm using a link and an algorithm using an existing node will be described with reference to FIG. 7.

7 is a basic node and link configuration diagram for the node-centric path calculation algorithm used in the present invention. As shown in FIG. That is, in the case of the node method, it is developed by finding B in A, adding a link <1>, finding C again in B, and adding a link <2>. At this time, the added link <1>, <2> ... becomes the primary key, and with this key, the vertex group of the link determined between the two nodes must be obtained. In other words, after computing around the node, the path key is determined.

In the link method, as soon as the link <1> is selected, the link <2> is found. Already, links <1> and <2> are primary keys representing roads, so there is no need to determine the key of the route.

The database established for the geographic information system determines the route from the specific point to the point when constructing the map. Therefore, it has a realistic precondition of operating on road data that has already been constructed. Due to these characteristics, we propose realistic methods that can improve the existing node-centric optimal path algorithm in a more effective way.

In FIG. 7, four link informations are required in the case of a link to pass through five node points, and there is no need for a calculation for a path that already reaches the point. This is because the path is already established as a link in the geographic information system DB.

However, when using a node, it consists of at least five node pairs for five points, and since the connection between these node pairs does not represent a real road, the link corresponding to the real road among all paths from one node to another node. Operation is required to find.

In addition, a separate additional operation takes place to obtain vertices for the various links connecting the nodes. Essentially, nodes and vertices are in the form of points separated by single coordinates of X and Y. For this reason, there is a need for a method of distinguishing between these and additional operations or attribute data to process them (see FIGS. 1A / 1B and FIG. 2 above).

This extra data is needed to see if it is over a given link, which would be a huge waste of computation time as the size of the data increases. Also, even if additional data is built up, it is necessary to retrieve relevant information from a large amount of data each time for computation.

FIG. 8 is a diagram illustrating an embodiment of a metadata construction process required for a memory in a node-centric path calculation algorithm in an optimal path calculation method according to the present invention. Show if it has been improved.

As shown in FIG. 8, one link includes two nodes and several vertices (5).

Here, we show the limitations of the node method on the geographic information system road DB. There are numerous vertices between two node points. Nodes and vertices have the same x and y coordinates for a particular point. There is a disadvantage in that a separate node table must be constructed by distinguishing nodes from vertices on numerous vertices in order to distinguish the dual nodes.

As shown in FIG. 8, in constructing metadata, a node corresponding to a road among the links connecting the node and the next node must be distinguished among the nodes in order to move from one node to the next node. In addition to the large amount of computation for this, a separate data table is required for reference.

FIG. 9 is a diagram illustrating an embodiment of a method for calculating a link center optimal path according to the present invention, and shows the meaning of a link on a geographic information system DB.

Here, one link means one road, which is the most important topological concept of GIS DB. That is, one link is the most basic key value representing the start and end nodes and all the vertices listed between them (6).

In FIG. 9, since the lines for the start point, the end point node, and the roads passing between the lines are pre-established as vertex groups, the path is already determined from the start point to the end point without further calculation.

Unlike on a node, the characteristics on the link mean that each of the links means a road, and the start and end points included in the link mean individual nodes. Thus, the next node predetermined for the link actually means the road to travel on. This is a feature on geographic information system road data, and this embodiment intends to utilize this feature.

This Abstract Data Type (ADT) is an application of geometric elements (use of points and lines) and geographic information system road data.

Looking at the extended details of the node B and node C of Figure 9, in order to determine the road from the node B to the node C, it is necessary to build a road continued from point B to the remaining three points. This means that the classical node-centric algorithm has to solve the problem of determining the next node to connect to.

The problem for deriving the optimal path is computed through several optimal path calculation algorithms once these links are established.

In order to solve a given problem, GIS can use two methods of processing by operation and constructing related property separately. In the link method, the next node to be arrived is determined to be one of the two end points of the link, so that the link is created in advance.

If the amount of data is small, the link can be created by manual operation or a separate calculation process.However, in the case of geographic information system data, the larger the amount of data and the larger the data, the computation time required to create the link increases exponentially. It costs. Figure 10 illustrates this difference graphically.

10 is a comparative explanatory diagram showing a difference between a link center optimal path calculation method and a node center path calculation optimal path calculation method according to an embodiment of the present invention. This compares the difference between the optimal path calculation through the link and the existing node method by using the characteristics of the geographic information system DB. In the link method, step 1 is omitted, and in step 2, data size and computation amount are minimized. have.

In the present invention, it is assumed that the GIS road data has already abstracted the process of creating a link at the node by reflecting the reality, and by using such realistic constraints, the problems of the existing node-centric algorithm are improved. In other words, the link-oriented algorithm has a significant time and memory effect by automatically establishing the endpoint information and key information of the link.

In order to utilize the information already built on the map DB, the information on the link is transferred in memory using the characteristics of dynamic objects when real-time processing is required, and an ASCII-type file for easy application to other applications. Support structure. In this case, the use of metadata alone is sufficient. In other words, using metadata can provide more flexibility for different needs, changes, and updates from users. This offers several advantages in geographic information systems.

First, since most of the map DB construction is done by hand, the effort to construct additional attribute data and the size of the entire DB are reduced.

Second, by automating human error troubleshooting, the data is more reliable.

Third, by reducing the required requirements in the application, it is possible to reduce the load on the entire application, thereby increasing the processing speed and relatively improving the performance of the hardware.

The present invention described above is capable of various substitutions, modifications, and changes without departing from the spirit of the present invention for those skilled in the art to which the present invention pertains, and the above-described embodiments and accompanying It is not limited to the drawing.

The present invention as described above, by providing a data abstraction and link-centric path calculation method, improves the problems of the existing node-centric method, and at the same time induces a cost reduction effect when constructing road data of geographic information system It is suitable for application to various application fields that want to get quick results through this, and in particular, since these parts are provided in the form of independent modules, it is easy to integrate with other applications.

Claims (3)

In the optimal path calculation method in geographic information system, A first step of distinguishing among roads among the links connecting the node and the next node to move from the node to the next node; A second step of minimizing the size of meta data for path calculation by assigning a common key to each node and a vertex of the link; And A third step of automatically finding the next connection link through an endpoint constituting the link based on the minimized size metadata and calculating an optimal path; Optimal path calculation method of the link center made, including. The method of claim 1, The link, A method for calculating an optimal path at a link center, characterized in that it is a primary key representing a road point and an end node and a vertex listed therebetween, and a primary key representing a road. In a geographic information system equipped with a processor, A function of distinguishing among roads among the links connecting the node and the next node to move from the node to the next node; Providing a common key to individual nodes and vertices constituting the link to minimize the size of meta data for path computation; And A function for automatically finding the next link through the endpoint forming the link based on the minimized size metadata to calculate the optimal path A computer-readable recording medium having recorded thereon a program for realizing this.