Back to EveryPatent.com



United States Patent 5,150,295
Mattingly September 22, 1992
Computerized system for joining individual maps into a single map product

Abstract

An improved method of making a larger map from individual 7.5 minute digital line graph (DLG) data is described herein. The process is fully automated and performed by a computer with minimal human interaction required. This eliminates errors and produces a more accurate final map product. The method includes conversion of the raw DLG data files into ARC/INFO format, locating the border arcs of each individual data set, edgematching the individual map data sets, and joining the data sets into a single, large map coverage. Any node along the border arc which cannot be automatically edgematched is noted in a special error file. A geographer then matches the unmatched edges which contain an error in the input data. A large map product is available as the product of the process.

Inventors: Mattingly; William (Huntsville, AL)
Assignee: Teledyne Industries, Inc. (Los Angeles, CA)
Appl. No.: 526144
Filed: May 22, 1990

Current U.S. Class: 702/5
Intern'l Class: G06F 015/62
Field of Search: 434/130,147 364/449,521,420 73/178 R 340/990,995,998,993

References Cited

Attorney, Agent or Firm: Beveridge, DeGrandi & Weilacher
Claims


I claim:

1. A computerized method of producing a map from a plurality of small map sections, said small map sections being in digital line graph format, the method comprising:

(a) receiving data corresponding to geographical features on the earth's surface as raw map data, said raw map data relating to small sections of the earth's surface in digital line graph format;

(b) locating the north, south, east and west border arcs in said raw map data, wherein said border arcs include nodes along the border arc;

(c) converting said raw map data into a format which identifies the latitude and longitudinal coordinates, and a type of map coverage;

(d) edgematching each node along the border arc of one map section to its adjacent map sections by matching the nodes along the border arc with the most closely corresponding node along an adjacent border arc, within a predetermined tolerance distance;

(e) snapping said node of said one map section to said most closely corresponding node along said adjacent border arc;

(f) repeating steps (b), (c), (d), and (e) for each border of said one map section, with its corresponding adjacent border on the adjacent map section;

(g) repeating steps (b) through (f) until all of the edges of the small map sections are matched;

(h) joining said small map sections at the matched edges; and

(i) producing a final map product from the joined small map sections.

2. A method of producing a map according to claim 1, wherein the edgematching in step (d) includes the following steps:

(d)(1) edgematching each node along the border arc of one map section to its adjacent map sections by matching the nodes with the most closely corresponding node, within a predetermined range and the predetermined tolerance distance:

(d)(2) if no match for a node is found within the predetermined range and within the predetermined tolerance distance, edgematching the unmatched nodes along the border arc with the nodes having the most closely corresponding node, within said predetermined range, along the adjacent border arc within an expanded tolerance distance; and

(d)(3) if no match for a node is found within the predetermined range and within the expanded tolerance distance, indicate a matching error.

3. A method of producing a map according to claim 1, wherein said type of map coverages are chosen from the group consisting of: hydrology coverage, road coverage, railroad coverage, and miscellaneous transportation coverage.

4. A method of producing a map according to claim 3, wherein said final map product includes at least two of said map coverages, one superimposed over the other.

5. A method of producing a map according to claim 2, wherein the expanded tolerance distance is five times the predetermined tolerance distance.

6. A method of producing a map according to claim 1, wherein the converted data of step (c) is put into the following format:

AwwBxyyyCzD,

wherein:

A represents a coverage type and is selected from the group consisting of H, R, T, or M, which stand for Hydrology, Roads, Trains or Miscellaneous transportation, respectively;

ww represents a number from 0 to 90 which stands for the number of degrees latitude from the equator of a southeastern corner of the small map sections;

B represents a direction selected from the group consisting of N or S, which stand for North or South of the equator, respectively;

x represents a decimal degree selected from the group of 0, 1, 2, 3, 5, 6, 7, or 8, which stand for 0.0 degrees, 0.125 degrees, 0.25 degrees, 0.375 degrees, 0.5 degrees, 0.625 degrees, 0.75 degrees and 0.875 degrees, respectively;

yyy represents a number from 0 to 180 which stands for the number of degrees longitude from the prime meridian in Greenwich of the southeastern corner of the small map sections;

C represents a direction selected from the group consisting of W or E, which stand for West or East of the prime meridian in Greenwich, respectively;

z represents a decimal degree selected from the group of 0, 1, 2, 3, 5, 6, 7, or 8, which stand for 0.0 degrees, 0.125 degrees, 0.25 degrees, 0.375 degrees, 0.5 degrees, 0.625 degrees, 0.75 degrees and 0.875 degrees, respectively; and

D represents a type of data to be converted into and is selected from the group consisting of A, P, or N, which stand for Area, Points or Nodes, respectively.

7. A computerized method for producing a map from a plurality of small map sections, said small map sections being in digital line graph format, the method comprising:

(a) inputting data into a computer corresponding to geographical features on the earth's surface as raw map data, said raw map data relating to small sections of the earth's surface in digital line graph format;

(b) locating border arcs in said raw map data, wherein said border arcs include nodes along the border arc;

(c) converting said raw map data into a format which identifies the latitude and longitudinal coordinates, and a type of map coverage;

(d) edgematching each node along the border arc of one map section to its adjacent map sections by matching the nodes along the border arc with the most closely corresponding node along an adjacent border arc, within a predetermined range and a predetermined tolerance distance;

(e) using the computer, repeating steps (b)., (c), and (d), for each border of said one map section, with its corresponding adjacent border on the adjacent map section;

(f) using the computer, repeating steps (b) through (e) until all of the edges of the small map sections are matched;

(g) joining said small map sections at the matched edges; and

(h) producing a map product from the joined small map sections.

8. A method of producing a map according to claim 7, wherein the edgematching in step (d) includes the following steps:

(d) 1) edgematching each node along the border arc of one map section to its adjacent map sections by matching the nodes with the most closely corresponding node, within the predetermined range and the predetermined tolerance distance;

(d) (2) if no match for a node is found within the predetermined range and within the predetermined tolerance distance, edgematching the unmatched nodes along the border arc with the nodes having the most closely corresponding node, within said predetermined range, along the adjacent border arc within an expanded tolerance distance; and

(d) (3) if no match for a node is found within the predetermined range and within the expanded tolerance distance, indicate a matching error.

9. A method of producing a map according to claim 8, wherein the expanded tolerance distance is five times the predetermined tolerance distance.

10. A method of producing a map according to claim 7, wherein said type of map coverages are chosen from the group consisting of: hydrology coverage, road coverage, railroad coverage, and miscellaneous transportation coverage.

11. A method of producing a map according to claim 10, wherein said final map product includes at least two of said map coverages, one superimposed over the other.

12. A method of producing a map according to claim 7, wherein the converted data of step (c) is put into the following format:

AwwBxyyyCzD,

wherein:

A represents a coverage type and is selected from the group consisting of H, R, T, or M, which stand for Hydrology, Roads, Trains or Miscellaneous transportation, respectively;

ww represents a number form 0 to 90 which stands for the number of degrees latitude from the equator of a southeastern corner of the small map sections;

B represents a direction selected from the group consisting of N or S, which stand for North or South of the equator, respectively;

x represents a decimal degree selected from the group of 0, 1, 2, 3, 5, 6, 7, or 8, which stand for 0.0 degrees, 0.125 degrees, 0.25 degrees, 0.375 degrees, 0.5 degrees, 0.625 degrees, 0.75 degrees and 0.875 degrees, respectively;

yyy represents a number form 0 to 180 which stands for the number of degrees longitudinal from the prime meridian in Greenwich of the southeastern corner of the small map sections;

C represents a direction selected from the group consisting of W or E, which stand for West or East of the prime meridian in Greenwich, respectively;

z represents a decimal degree selected from the group of 0, 1, 2, 3, 5, 6, 7, or 8, which stand for 0.0 degrees, 0.125 degrees, 0.25 degrees, 0.375 degrees, 0.5 degrees, 0.625 degrees, 0.75 degrees and 0.875 degrees, respectively; and

D represents a type of data to be converted into and is selected from the group consisting of A, P, or N, which stand for Area, Points or Nodes, respectively.
Description


BACKGROUND OF THE INVENTION

The invention relates to the art of map making. Geographic information is available in a variety of forms, and numerous Geographic Information Systems (GIS) have been implemented and are used throughout the world. These information systems allow organizations to display, manipulate and analyze geographical data.

The United States Geological Survey (USGS) is one of the major sources of raw geographical data at the present time. USGS transforms a hard copy of a map into a digital form. This is called a digital map. The digital data is stored on tape and sold to users in an ASCII format known as digital line graph (DLG) format (defined by USGS as Digital Line Graphs from 1:100,000 Scale Maps by the Data User Guide 2, available from USGS). This data is in a vector format. USGS provides DLG tapes on various topographical coverages including hydrology, roads, railroads, and miscellaneous transportation. Miscellaneous transportation may include data such as power lines, pipes, air strips, ski lifts, tramways and the like.

USGS provides DLG data blocks in map sections which cover a 7.5 minute by 7.5 minute area of the earth's surface (7.5 minute map). This area is equivalent to one-eighth of a degree longitude by one-eighth of a degree latitude. The area encompassed by a 7.5 minute map varies, depending upon the location on the earth's surface. Within the Continental United States, the area is typically about 10-11 km east to west by about 19 km north to south. More than 50,000 of USGS's 7.5 minute maps are required to completely cover the Continental United States (CONUS) for each type of coverage (i.e. 50,000 maps for roads, 50,000 maps for railroads, etc.). As a further example, the State of Kentucky requires 765 of the 7.5 minute maps to completely cover its borders.

It is often desirable to have a single map which covers a larger area than the 7.5 minute map. Also, it is often necessary to create a map which includes more than one topographical feature, for example, a map with both roads and railroads may be desired.

The Environmental Science Research Institute (ESRI) has developed a software package called ARC/INFO which is used for processing the data from DLG files. The DLG data files are not directly compatible with the ARC/INFO system. Before ARC/INFO can be used, the DLG data files must be converted into ARC/INFO format.

ARC/INFO includes a program which allows the user to convert the raw DLG data files into ARC/INFO format. This conversion program requires periodic human interfacing with the program. Thus an operator must be present throughout the conversion process to input the proper parameters to the computer at various stages in the conversion. The operator loads the tape, and the program prompts the operator for additional information. The system prompts the user for the DLG file name, the number of files to process and the name of the directory in which to store the data in. This is a long, time consuming operation which is subject to error because of the constant human interaction.

The second step in producing a larger map from the 7.5 minute map sections is an edgematching procedure, wherein the edge features of one map are matched to the corresponding features on the four surrounding maps. This process is completed in the prior art systems by a manual edgematching process. This process will be described in more detail below.

As shown in FIG. 1, a larger map 10 is often desired as opposed to the individual 7.5 minute maps 12. An enlarged version of the 7.5 minute map labelled A is shown in FIG. 2. Map A is shown to contain various arcs which represent topographical features (i.e. roads, waterways, etc.). It will be appreciated by those skilled in the art that an actual 7.5 minute map may contain hundreds or even thousands of these arcs.

As mentioned above, the edgematching process of the prior art systems requires a manual edgematching step. To match the edges, the two adjacent data sets representing the edges to be matched are called up onto a computer screen. The computer screen typically places these edges approximately one inch apart. For every node along an edge (16 and 26, for example), the operator must locate the corresponding node on the adjacent data set. The operator selects the end node of one of the edges, looks over at the adjacent edge,.makes an interpretation of which feature on this edge he believes that the first end node should be joined to, and he selects this feature. The operator then enters a command on his keyboard that joins these two features together. This is called "snapping" the two features together. This manual matching process must be performed on every node along the edge, along every edge on the 7.5 minute map, and around every map that is to be joined. As mentioned above, there are more than 50,000 7.5 minute maps per coverage (i.e. hydrology, roads, etc.) to cover the Continental United States.

Those skilled in the art recognize the time consuming and tedious nature of this edgematching procedure. Furthermore, matching of every node requires a judgment on the part of the operator; hence, this process is highly error prone. The operators become tired and bored, nodes are completely missed, mismatched, and many other human errors may be involved. It is also a very time consuming process; therefore, it is also very costly in terms of man hours and money. Additionally, this process requires a graphic terminal to match the edges on.

Furthermore, the final product is also full of errors. It is virtually impossible to obtain an error free final map product.

The final steps in creating the map product are to correct the attribute files and to clean up any coverage which does not have the correct topology. Then, the various individual coverages (7.5 minute maps) desired in the final product are combined into a single map layer.

In the prior ar& systems, the user again was required to manually interface with the computer, this time to assure that the attribute files for each map matched up. The attribute file of each individual file (7.5 minute data file) had to be looked at individually to determine how many attributes were missing. The correct number of attributes cannot be determined until all of the files are inspected. After inspecting all of the attribute files, the operator then needed to determine the correct number of attributes, and enter any missing attributes into each individual file by means of a program routine called ADDITEM. ADDITEM is a routine that is a standard command in the ARC/INFO package which allows the user to enter attributes. The operator is required to enter the ADDITEM command over and over on the terminal. This process is also extremely time consuming and tedious.

The procedure for joining the individual maps into a single coverage was relatively simple for the user in the prior art systems. The user only needed to enter all of the individual file names for the maps that were to be joined. ARC/INFO would join these files into one map layer. This is also a very tedious chore in situations where hundreds or thousands of individual data files are being joined.

As noted above, the process of the prior art requires a large investment of time and money. Shown in Table I are the approximate times requires to process 256 DLS files using the prior art manual processing methods. 

                  TABLE I
    ______________________________________
    Process                Time
    ______________________________________
    1.   Convert DLG files into ARC/INFO,
                               100 man hours
         building topology, projecting,
         reading tapes, etc.
    2.   Edgematching (correcting map
                               100 man hours
         features to meet at the map
         borders).
    3.   Attribute correction and combining
                                32 man hours
         of individual maps into a single
         layer.
         TOTAL                 232 man hours
    ______________________________________


Since this data is processed manually, there are typically numerous errors which are present in the processed data.

SUMMARY OF THE INVENTION

It is an object of this invention to provide a procedure for processing DLG data files in a more efficient and less costly manner.

Another object of this invention is to provide a surface area map product with dimensions larger than 7.5 minutes, wherein the map is error free.

Another object of the invention is to provide a fully automated process for converting DLG data files into ARC/INFO format. It is desired to totally eliminate human interaction in the DLG data files into ARC/INFO conversion process.

Another object of the invention is to provide a fully automated edgematching procedure that eliminates human interaction and errors while edge matching the smaller map sections into a larger map area.

Another object of the invention is to provide a fully automated procedure for creating maps which contain a plurality of topographical coverages.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other advantageous features of the invention will become evident from the following detailed description, the attached computer programs, and the attached figures,, wherein:

FIG. 1 shows a diagram of 32 7.5 minute maps in their edgematched and joined format;

FIG. 2 shows an enlarged diagram of one 7.5 minute map section before edgematching, along with the four adjacent map coverages;

FIG. 3 is a flow chart of the overall process;

FIG. 4 is a flow diagram of the DLG-CONVERSION process;

FIG. 5 is a flow diagram of the DLGLINK.AML process; and

FIG. 6 is a flow diagram of the FIX-JOIN process.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The invention is a computerized system which eliminates the need for human interaction in the map producing process. An overview of the process is shown in FIG. 3. The preferred embodiment of the invention uses FORTRAN programs, in particular, FORTRAN 77. In particular, the AUTO-LINK.FOR program was written in FORTRAN 77 on a VAX computer. The programs ending with the ".AML" portion are the interface to the ARC/INFO codes to drive the programs. The process initially receives the raw DLG data as input. A first computer program (DLG-CONVERSION) converts the raw DLG data for each 7.5 minute map into ARC/INFO format. ARC/INFO coverages are generated using the following data set naming convention:

H48N8103WOA

wherein

H--the coverage type for hydrology. The different types of coverages are named as follows:

[H]ydrology,

[R]oads,

[T]rains (Railroads), and

[M]isc. Transportation (trails, etc.)

48 N8--represents the latitude of the Southeastern corner of the 7.5 minute map. 48 represents degrees, N means north of the equator, 8 represents 0.875 degrees. Since each coverage is one-eighth of a degree square, only the tenth of the degree is needed for identification purposes.

103 WO--103 degrees west longitude of the Southeastern corner, plus 0.00 degrees

A--this refers to the ARC/INFO type of data to be converted to, labelled according to the following convention:

[A]rea (polygons and lines),

[P]oints, and

[N]odes.

This procedure is fully automated. The raw DLG data is generated from map products, such as existing hard copy map products. These map products are put into a digital form and placed on a tape. The tape or digital map is available from USGS. This data is in a vector format. The DLG data tapes are loaded into the computer, the first and last DLG files to be processed are entered, the type of topographical coverage is entered, and the program is run. No additional user interaction is required.

The next step is the automated edgematching procedure. This was the most difficult and challenging aspect of perfecting the invention. The main program is called DLGLINK.AML. The computer matches each node on the border arc with the most closely matched node on the other map's border arc within the edit distance. The edit distance is preferably set to the smallest discernable distance that can be digitized on a map of that scale. A distance of 30 meters on 1:100,000 scale data is preferred. Often the DLG data which is obtained from USGS contains errors, because USGS uses manual processes in producing the DLG files. If an error is present in the raw DLG data, the computer will not be able to match the node. A match is searched for over a distance of five times the edit distance. If none is found, the program notes this node failure and its location in a separate error file. This error file is called the DLGLINK.LOG file, or the "Log File" in the programs. These unmatched nodes must be manually checked by a geographer after the remaining edges are matched. This edgematching process will be described in more detail below.

The final procedure step is the correction of the attribute files for the coverage and the correction of any coverage which lacks correct topology. The desired coverages are joined into a single output coverage, and a map is the final product. The program for the last procedural steps is called Fix-Join.

The "Fix" part of this program assures that the files have the correct topology and the correct number of attributes. Each 7.5 minute map data set includes a coverage attribute file. To join the 7.5 minute map sections, the coverage attribute files must match exactly. This attribute file contains a record for each arc in the coverage, and details on what the arc is (e.g. read type, HWY 101, HSY 20, US 64, etc.). This program determines the number of attributes required in all of the individual 7.5 minute maps and adds the correct attributes to each individual file for any that are missing. This assures that the coverage attribute files in the adjacent map sections match up exactly, which, in turn, allows these map sections to be joined together into a single coverage. This process is fully automated, thus the need for human interaction is eliminated.

The "Join" part of this program also saves time for the operator. This is the part of the system which joins all the individual maps into one map. The operator need only put in the file name for one of the files to be joined. Recall that the prior art system previously required the operator to enter every file name to be joined together. In the system in accordance with the invention, the computer will automatically generate the remaining file names based on the latitude and longitude coordinates of a single data file. This feature saves a substantial amount of time, especially if hundreds or thousands of individual coverage maps are involved.

Other quantitative data may be obtained from the data, such as the miles of railroad within the area, percentage of the surface over a certain elevation within the area and the like. Also, other topographical map features may be overlaid or superimposed over this map. Buildings, military installation locations, or other geographical features may be included in the map after the larger map has been completed.

For purposes of comparison, Table II shows the employee time and computer time required to process the DLG data into a finalized map product. By a finalized map product in this specification, the inventor is referring to hard copy map products, map products stored on tape or in other computer generated and readable forms, or maps displayed on a computer screen. Hard copy map products may be generated by any ARC/INFO supported plotter, this equipment being known to those skilled in the art. The final map product may be used for a wide variety of purposes. The maps may be used to create a library of maps which document the construction and/or development of a geographical region. Environmental conditions in a region can be monitored over a time period. Various types of geographic analysis may be performed on the map data. For example, the miles of roadways or railroads over a region may be ascertained. The surface area of a region covered by water or over a certain elevation may be determined. The maps generated may be overlaid with other topographical features, such as the location of particular buildings or other landmarks, military base locations and other items of interest to the user. These additional topographical features may be digitized into the map or superimposed over the final map produce.

As in Table I, 256 DLG files were processed using the procedures in accordance with the invention. 

                  TABLE II
    ______________________________________
    Process           Computer Time
                                  Man Time
    ______________________________________
    1.  Convert DLG files into
                          8 hrs.      0.1 man hours
        ARC/INFO, building
        topology, projecting, reading
        tapes, etc.
    2.  Edgematching (correcting
                          8 hrs.      0.1 man hours
        map features to meet at map
        borders).
    3.  Attribute correction and
                          2 hrs.      0.1 man hours
        combining of individual
        maps into a single map
        layer.
        TOTAL             18 hrs.     0.3 man hours
    ______________________________________


Note the dramatic time savings that is realized when utilizing the process of the invention, as opposed to the human interfacing process of the prior art. A further advantage to the process of the invention is the fact that errors are virtually eliminated. Any edge which the computer cannot match is noted in an error file as mentioned above. These edges must be matched manually by a geographer.

Since the process is fully automated, the process may be completed by the computer in the evenings or over weekends. This keeps the computer available for normal business purposes during working hours.

Returning to FIGS. 1 and 2, the edgematching process, performed by the program DLGLINK.AML, will be described in more detail. When creating a large map 10 from the 7.5 minute maps 12, it has been found that the automated edgematching process is the most difficult and technically challenging aspect of the procedure.

It is preferred that the edges of the various maps be matched by a checkerboard method. The edgematching process will be described with particular reference to the 7.5 minute map designated A in FIGS. 1 and 2.

The 7.5 minute map A shown in FIG. 2 contains several arcs. An arc is comprised of nodes and vertices, wherein the nodes are the endpoints of the arcs. Reference numbers 14 and 16 are nodes, and these nodes define an arc. Vertices are represented by numbers 18 and 20. In actual map data, a 7.5 minute map may contain hundreds or thousands of arcs. Using the checkerboard method, the arcs of map A are adjusted to line up with the arcs of maps B, C, D and E. This method of edgematching is called the checkerboard method because only the maps marked by an "X" in FIG. 1 are allowed to be adjusted by electronically "shifting" the map edge. The maps which are not marked by an "X" are not electronically adjusted.

Each 7.5 minute map also contains four arcs which are not part of a map feature at all. These arcs are the border arcs which define the outer edges of the map. One of the border arcs for map A is shown between points 22 and 24 in FIG. 2. The USGS codes these otherwise useless border arcs as -9999 in the attribute file.

By using nodes which exist along the border arcs, the process for edgematching becomes much less complicated and less time consuming. Matches of internal arcs are eliminated. Furthermore, using only nodes from the border arcs prevents arcs from being drawn into the border and collapsing the arc. The edgematching process between maps A and C along border arc 22-24 will be described.

Each map has four border arcs, namely, East, West, North and South. The nodes and locations of the nodes for map A are stored in four different arrays, one array for each border. The same storage process is completed with map C. Because map A is being matched to map C, only the North nodes of map A need to be tested against the South nodes of Map C. This process prevents a possible erroneous match of node 28 to node 30. If all of the nodes along the North border of map A have a corresponding match with the nodes on the South border of map C, then the edge has been successfully edgematched. If a node fails to have a match, the location of the failure is logged into a file, as described above. These unmatched nodes must be manually checked by a geographer however, in the overwhelming majority of cases the map edges are successfully matched.

The edgematching process is completed for all four borders of map A. If an edge coverage is missing, such as on an outside piece of the larger map (see 7.5 minute map 32 in FIG. 1), the value "NONE" is passed, and the edge is assumed to be matched.

In determining which node to match to the corresponding node in the other map, the node is matched to the node with closest value within a predetermined range and within the edit distance. The edit distance is input by the system user. It is preferred that the edit distance be set to the smallest discernible distance that can be digitized on a map at the scale being used. As noted above, a 30 meter edit distance is preferred on 1:100,000 scale data. If a match is found, the two nodes are snapped together. If a node needs to be electronically moved, the node alone is not moved. Rather, the entire coverage, including all of the arcs, is moved proportionally. This type is movement is called "rubbersheeting".

If all of the four borders are matched with the surrounding borders automatically, there is no need for manual inspection of the geographic data. The matching process is more accurate than the prior art systems, because there is no human interaction, thus, errors are eliminated.

The process of the invention is used to output a final map product in hard copy form. Other topographical features may be overlaid or superimposed onto the map, such as military installations, buildings or other geographic features. Other geographic analyses may be performed on the finalized map data, such as the number of miles of roads or railroads, the percentage of the surface area that is covered by water, the percentage of the area above a certain elevation etc. Other types of geographic analysis will be apparent to those skilled in the art.

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

COMPUTER PROGRAM

An algorithm of the various computer programs used will be described in conjunction with FIGS. 3-6 and the attached computer codes.

FIG. 3 shows the Process Overview. The system begins by receiving the individual DLG data files as input, as shown at 30. The first part of the process, called DLG-CONVERSION 32, transforms the raw DLG data files into ARC/INFO format.

After the data is in ARC/INFO format, the information is processed by a program called DLGLINK.AML 34. DLGLINK.AML is used to edgematch the individual DLG data files to the surrounding data files. The DLGLINK.AML recursively calls a program called AUTO-LINK.FOR 36. DLGLINK.AML sends the necessary information to AUTO-LINK.FOR, and AUTO-LINK.FOR is the program which actually matches the adjoining edges. The matched results are sent back to DLGLINK.AML, which stores this data and sends the next data sets to be matched to AUTO-LINK.FOR.

After all of the edges are matched, the information is processed by a program called Fix-Join 38. Fix-Join cleans any topology with mistakes and adds any necessary data to the attribute files. The attribute files of the data sets must match exactly before the individual maps may be joined. After the data sets are fixed, the individual map sections are joined into a single map layer. A hard copy may be made. Various map layers, such as a railroad layer and a road layer, may be added together to get a more detailed map. Other map features may also be added, or other geographic analysis may be run on the data as discussed above.

The DLG-CONVERSION program is shown diagrammatically in FIG. 4. This program is to convert the raw DLG data files into ARC/INFO format. The program, first prompts the operator for the parameters of the run. The input parameters are the base names of the DLG file to convert, the first DLG file to process and the last DLG file to process. The program double checks with the user that all of the input data was correct. The program also prompts the user for the pathnames of the coverages, for example, hydrology, roads, railroads or miscellaneous transportation coverages. Their is also a double check feature on this data input step. Each type of layer is stored in a separate workspace, thus enhancing performance.

The main program calls a Routine named READ-DLG-HEADER. This routine calls the DLG file to determine the type of layer, UTM zone, and latitude and longitude coordinates of the southeast corner of the 7.5 minute map. This information is used to generate the map name in ARC/INFO format. This format was described above. The DLG-FILE name generated by READ-DLG-HEADER includes the map scale (which is used to set the tolerances and edit distance), the UTM zone (for use in projection, UTM stands for Universal Transverse Mercator, a standard map projection known to those skilled in the art), the latitude and longitude coordinates, and the coverage type. The READ-DLG-HEADER opens the appropriate DLG file and obtains the necessary information to name the coverage, UTM zone for projection, tolerences and coverage type. The coverage name is in the following format: [.HYDRO]H103W036N2A([.HYDRO] refers to a computer directory; H corresponds to a hydrology coverage: 103WO corresponds to 103.00 degrees west longitude; 36N2 corresponds to 36.25 degrees north latitude; and A represents an Area ARC/INFO coverage). This coverage name is returned to the main program, DLG-CONVERSION.

DLG-CONVERSION checks the input data for polygon topology. Polygon data is coded A at the end of the ARC/INFO format convention. If polygon data exists, then a topology is built with the polygon option (BUILD is a standard ARC/INFO command). The polygon topologies for all of the data files are joined by JOINITEM (a standard ARC/INFO command).

The presence of a Line topology is checked next, in the same manner as the polygon topology, and a topology with the line option is built. Similar operations take place on the Point topology and the Node topology.

If the coverage is a hydrology coverage and it includes a polygon topology but no line topology, it is a situation where the entire map area is a large lake or sea. In this case, the line topology must be built in and coded as -9999 to indicate that the lines are border arcs.

The temporary DLG attribute files are deleted. The coverages for the various types of topology (area, points, and nodes) are projected to the user output projection system and stored under the appropriate ARC/INFO naming convention. A routine called PROJECT-COVERAGE projects the coverages to the user's base projection system. Various base projection systems may be used, for example, state plane, ALBERS, Lambert, or others. The choice of projection system depends on what projection is used by the user in his normal mapping process. This choice is deemed to be within the level of normal skill in the art.

If a polygon topology coverage exists, it must be rebuilt after projecting it. The tolerance levels are set to the default values and the topology is copied into the user's work space with the ARC/INFO naming conventions described above.

The above procedures are performed on every DLG data file which is input into the system. After all the data files are in ARC/INFO format, the process for edgematching the data files begins.

The program which is used to edgematch the maps is called DLGLINK.AML, shown as a flow diagram in FIG. 5. This program recursively calls the program AUTO-LINK.FOR (AUTOLINK in FIG. 5), which in turn matches each map with the surrounding four map coverage sections(AUTO-LINK.FOR may also be referred to as DLGLINK in some of the program codes, flow diagrams and algorithms.)

DLGLINK.AML accepts the user's parameters, which include: the name of the Southeast coverage, the horizontal coverage size in decimal degrees, the vertical coverage size in decimal degrees, the number of horizontal coverages and the number of vertical coverages. The coverage name, which is generated by the routine COV.sub.-- NAME. enables the system to ascertain the location of the southeast most corner and the type of coverage (roads, etc.). This name is generated in the standard naming format for the coverage name described above. The latitudinal and longitudinal coverages are determined from the input data. DLGLINK.AML also creates the error file called DLGLINK.LOG, Any coverage that is unable to be matched automatically is noted in this file. After all of the automatic matching is complete, the locations of the edges which were not matched are disclosed to the operator. These locations must be checked manually by a geographer before the maps can be joined.

From the input data, the checkerboard pattern described above is generated. The coverages for the east, west, north and south directions are determined for the first map section to be matched. Only every other map in the horizontal and vertical directions are actually adjusted by the computer, thus creating the "checkerboard pattern". The fatal error file "FATAL.ERROR" is created, after any previously created FATAL.ERROR file is deleted. If this file is not deleted at the time when the AUTO-LINK.FOR program completes the edgematching process for this map, then a fatal error was encountered when matching the map section. The location of the error is stored in DLGLINK.LOG.

After the error file is created, the AUTO-LINK.FOR program is called. For each map section which needs to be matched, DLGLINK.AML recursively calls the AUTO-LINK.FOR program. This program will be discussed in more detail below.

After all of the edges for the first map section are matched, the east, west, north and south tables for the next map section are generated. Any existing FATAL ERROR file is deleted and a new FATAL ERROR file is generated. AUTOLINK.FOR is called again. This process repeats itself for every map section in the checkerboard which needs to be matched.

DLGLINK.AML also calls a routine called GET-COVS. This routine checks the input north, east, west, and south coverages of the 7.5 minute maps to determine when the data is at the edge of the final map. When at the edge, the value "NONE" is passed, to tell the system that it is at the map edge, and the edge is assumed to be matched as it is. GET-COVS further calls the routine COV-NAME, which generates the proper latitude and longitude coordinates which are used by GET-COVS to determine if the data is from an edge location.

As mentioned above, DLGLINK.AML calls the program AUTO-LINK.FOR for each map section which must be matched. This program takes advantage of the fact that DLG data codes the border arcs as -9999. If all of the nodes along the edge are matched to the adjacent coverage nodes, these nodes are snapped together, and the edge has been automatically edgematched. If any edge fails at only one node, the error file is created and the location is noted, as described above. The following criteria are used to generate the links,

A) Only nodes on border arcs coded -9999 are considered;

B) Only one edge of coverage is compared to the corresponding edge of the adjacent coverage (i.e. north edge of one map compared to the south edge of the adjacent coverage map);

C) Nodes are matched to the closest node within the edit distance to create the link;

D) Only one link is allowed per node;

E) If all the border nodes (snapcover nodes) are linked, the edge is linked; and

F) If all the edges are linked, the coverage is linked.

AUTO-LINK.FOR first initializes a variety of ARC/INFO subsystems by calling the following interface routines which are available to all ARC/INFO users: TTINIT, LUNINI, AMLINI, VINIT, GETINT, MINIT, MESINI, MESIAM, and AMLTTY. These routines set up the environment to receive parameters from DLG-LINK.AML. These are generic routines for interfacing with the ARC/INFO. The user parameters are read in, which include the edit coverage, the east border coverage, the west border coverage, the north border coverage and the south border coverage. The edit distance is set to 30. Next the error file and the output files are created.

The subroutine PROC-COV is used to open and read in the data of the attribute file of the map to be matched. If the arc is coded less than zero, this program recognizes this as a border arc. If it is a border arc, the nodes are recorded. If the slope of the line between the nodes is between -45 degrees and +45 degrees, the nodes are placed in a north/south table. If the slope is not in that range, the data is stored in an east/west table. The midpoint is then located at half way between the minimum and maximum node location entries. Horizontal lines have nodes on either the east or west sides and vertical lines have nodes on either the north or south sides. The two east/west and north/south tables are divided into the four coordinate directions (east, west, north and south) by comparing to the midpoint.

After the nodes for the map to be matched are placed in the proper coordinate tables, the nodes in each table are then sorted and placed in X,Y order. The X and Y coordinate values depend on the map projection. For UTM, typical coordinate values would be (650,000, 4,170,330). The EDITCOV nodes (i.e. the nodes being adjusted to match the four adjacent coverages) are also sorted into X,Y order by a "bubble sort".

Each edge is processed, unless the edge has been labelled "NONE", which corresponds to a large map edge piece. A logic variable called BAD-EDGE is set to "false"; if BAD-EDGE becomes "true", the coverage cannot be autolinked.

The programs are designed with the commands that are needed to interface with the ARC/INFO system. The commands needed are: arcedit, set edit feature, editcover, coordinate keyboard, and add. To process a cover, the nodes of the adjacent maps are separated into the north, south, east and west edges for the cover. This sorting is done by the PROC-COV routine also. First the west edge of the map is matched to the east edge of the "cover" map (the adjacent map). The location of each node in the adjust map is compared to the cover nodes within the edit distance, and the closest cover node within the edit distance is returned. Once a matching node is found, the ARC/INFO ASCII command to add the link is executed. The links are later added by the ARCEDIT command.

First, the closest match is sought within the edit distance. A subroutine called FIND-CLOSEST is used for matching. If no match within the tolerance limits is found within the edit distance, the distance is expanded to five times the original distance. If no match is found in this range, an error is noted by the computer, and the logical variable BAD-EDGE is changed to "true". If a match within the tolerance limit is located in the wider range, this match is snapped using the ARC/INFO commands, for example, ARCEDIT and ADD.

This method of finding the closest match is repeated for the east, south, and north edges of the map to be matched. If no bad edge is found around all four edges of the map to be matched (i.e. BAD-EDGE=.FALSE. at the end of the matching steps), then the map is adjusted and saved. If a failure is noted, the error is noted in the error file.

The subroutine FIND-CLOSEST is used to find the closest node match within the edit distance. If a match within the tolerance limit is found, the closest match is located by a binary search, and the location of the successful cover node is passed back to the main program.

The final steps in the matching process are completed by a program called FIX-JOIN, shown in FIG. 6. As discussed above, in order to snap to individual maps together, the attribute files must match each other exactly. Fix-Join receives as input: the name of the southeast coverage, the horizontal size in decimal degrees, the vertical size in decimal degrees, the number of horizontal coverages and the number of vertical coverages. Default numbers of attributes are preset in two files called "MINOR" and "MAJOR". The following steps are repeated until every attribute file has the same number of MAJOR and MINOR code pairs.

First the latitude and longitude of the southeast corner are used to generate the coverage name. These coordinates are incremented during the successive loops. When lines are shifted during the edge matching process, the lengths of lines, the areas of polygons, and the location of nodes are changed. When this occurs, the coverage is said to not be "clean". If the coverage is a network coverage (Area) and it is not clean, the coverage is first cleaned with the polygon option. If the coverage lacks line topology, "topology" referring to the relationship of map features to one another, the topology is cleaned with the line option. "Clean" and "Build" are ARC/INFO procedures which are used to re-establish the topology after a shift during edge matching. To determine the number of PAT (Polygon Attribute Table) files, subtract 16 from the number of attribute files and divide the result by 12. To determine the AAT(ARC Attribute Table) file number, subtract 28 from the number of attribute bytes. This provides the number of MAJOR and MINOR codes for the coverage.

If the number of attributes in the PAT and AAT files do not match the maximum number of attributes in PAT-MAX and AAT-MAX, a single item is added for all missing attribute pairs. The items are added with the ARC/INFO ADDITEM command discussed above. Preferably, a single ADDITEM command is used to reduce the input/output overhead.

If any file has more attributes than the default amount or the previous PAT-MAX or AAT-MAX amount, the values in PAT-MAX or AAT-MAX are increased to correspond to the higher value.

The final step is to append or join the multiple 7.5 minute maps which have been matched into a single output coverage. From the coordinates of the southeast corner, the coverages are appended together as the latitude and longitude coordinates are incremented. If the coverage has been matched, the coverage is appended to the surrounding coverages. A large map product is produced as the final product. Several map layers may be added together and superimposed onto a single map.

A copy of the program codes described above are attached to the end of this specification, along with flow diagrams and algorithms of these codes. This material will be understood by those skilled in the art. All codes, flow diagrams and algorithms referred to herein and attached to this specification are relied on and incorporated by reference.

While the invention has been described in conjunction with particular embodiments, various modification may be made without departing from the invention, as defined in the claims. ##SPC1##

Top