Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-03-17
2001-06-12
Vu, Kim (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C340S990000, C340S995190, C340S989000, C434S152000, C701S207000, C701S208000
Reexamination Certificate
active
06247019
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to object-oriented, geographic information systems (GIS), and more particularly, to an object-based geographical information system capable of displaying a topological region in real time, a geographical information system using a virtual blackboard for scrolling in real time, and a method of building an object-based database of topological features.
BACKGROUND OF THE INVENTION
Geographic information systems (GIS) store, retrieve and display topological information. The topological information is obtained from a topology which is a topographic study of a geographic region. The topographic study may be a map having features of the geographic region including rivers, lakes, etc. and canals, bridges, roads, etc.
In the prior art, a topology can be the numerical description of the relationships between geographic features, as encoded by adjacency, linkage, inclusion, or proximity. Thus a point can be inside a region, an arc can connect to other arcs, and a region can have neighboring or adjacent regions. Many GIS systems are constructed using object oriented programming systems and database managers. These object oriented programs and database managers are topologically based and rely on topological data structures.
A typical prior art object-oriented topology-based data structure for a GIS system is depicted in FIG.
1
. In these prior art systems, topological information is classified by feature objects using geometrical primitives to reconstruct a topological feature.
In this type of data structure, depicted in
FIG. 1
, the regions, polygons, arcs and vertices are known as geometrical primitives. Geometrical primitives are classes used to reconstruct a region or object. This topological based system requires that links be maintained between each of the primitives to reconstruct a region. These systems are referred to as topological based systems having topologically based data structures because topological information is classified by topological feature objects using geometrical primitives to reconstruct each topological feature. For example, a topological feature (region) could be the United States, and there would be a polygon file linked to the United States region file. The polygon file defining the boundary of the United States is linked to arc files. The arc files are then linked to vertice files. Each primitive is linked to another primitive.
In the language of object oriented programming, in this example, the United States region is an object and the polygons, arcs and vertices are classes. The United States region inherits or receives attributes from ancestors (polygons, arcs and vertices). The United States region is also known as an instance. An instance is used to denote the creation of an object from one or more classes.
In the prior art, in another example, an individual state can also be a region and an object. For example, the state of Utah can be an instance and would inherit attributes from ancestors (polygons, arcs and vertices).
A more complex but still relatively simple topological data structure can be explained with reference to
FIG. 2
a
.
FIG. 2
a
is a prior art arc
ode diagram of a polygon depicting the outline of the state of Utah. The boundary of Utah is defined by four arcs A, B, C, D and nodes 1, 2, 3, 4, 5, 6. Each arc has a set of points ordered from node to node in a sequence. In
FIG. 2
b
, a polygon file contains an entry for the area of the polygon, an entry for the attributes of the polygon and an entry listing the arcs defining the polygon. In the simple example for the boundary of Utah, the polygon file lists the arcs A, B, C, D forming the boundary. In
FIG. 2
c
, an arcs file lists the vertices for each arc. For example, vertices 1, 2, 3, 4 are the vertices for arc A. In
FIG. 2
d
, a vertices file lists the coordinates for each of the points forming vertices on the state boundary. The vertices are then connected to each other in sequence. Curves would be defined by many straight short arcs.
A more powerful topological data structure uses the arc as the basis for data storage. This can be explained with reference to
FIGS. 3
a
and
3
b
in which the arcs file includes information not only about the particular arc but also includes information about the neighbors of each arc.
FIG. 3
a
depicts a skeleton of two adjacent polygons A and B. Polygon A has a plurality of arcs but for purposes of explanation, only arcs 4 and 5 will be explained here. Arc 4 has end nodes n1 and n2 and arc 5 has end nodes n2 and n3. Polygon B also has a plurality of arcs of which arc 4 is shared with polygon A.
For simplicity, only topological arc files are depicted for arcs 4 and 5 in
FIG. 3
b
. The arc file for arc 4 identifies the end points of the arc (n1, n2) and lists the x and y coordinates for the end points or nodes (n1, n2) of the arc as described above. The arc file also includes information for the polygon which lays to the left and right of the arc (polygon left (PL) is A and polygon right (PR) is B). Information can also be included on the arc number of the other arcs connected to the end nodes. The arc file for arc 5 identifies the end points of the arc (n2, n3) and lists the x and y coordinates for the end points (n2, n3) of the arc. The arc file also includes information for the polygon number which lays to the left and right of the arc (polygon left (PL) is A and polygon right (PR) is C).
A polygon can be reconstructed by extracting all of the arcs that a specific polygon has as a neighbor. For example, polygon A can be reconstructed by extracting arcs 4 and 5 because arc 4 has polygon A (PL is A) as a neighbor and arc 5 has polygon A (PL is A) as a neighbor. The other arcs of polygon A would be similarly extracted from the topological arcs file.
In all of the prior art examples discussed above, to display a topological region, the region has to be assembled from the most primitive components stored in the database. In the system, the whole process of assembling and computing the topology of the region and the object from its primitives means that the prior art GIS systems are very slow.
Mission-critical applications require the display of topological information in real time. The requirement for real time is that in certain applications a driver or pilot needs to make decisions and perform course corrections within a certain amount of time or it would be too late and the vehicle, airplane or ship would crash. In the GIS environment, real time means applications where there is a need to be able to draw a map or topological region in five seconds or less. These prior art GIS systems are not capable of displaying in real time and, thus, in mission-critical applications, these topological-based data structures are not capable of providing real time information. The prior art systems can take several minutes or even longer to display a topological region.
Mission-critical environments include takeoff and landings of airplanes at high speeds or ship control in tight navigational sea environments such as entering or exiting harbors where water conditions and obstructions in the water change daily. In the takeoff and landings of airplanes, a plane might be approaching Denver International airport at about 300 miles per hour (about 500 feet per second) with mountains in the distance. Should the airplane be off course and the GIS system crash, thereby causing the GIS system to take several minutes to recover, the pilot would be unable to recover. In this situation, about five seconds is considered adequate. In the navigational environment, it can take a large ship a long time to change course and so this is also a mission-critical application.
Another major disadvantage of the prior art topological data structures is that these are very expensive data structures to assemble because of all the relationships needed between each of the primitives such as adjacency, linkage, inclusion or proximity. The topological data structure is also expensive to maintain. Modification of a region, e
Corrielus Jean M.
Lowe Hauptman & Gilman & Berner LLP
PRC Public Sector, Inc.
Vu Kim
LandOfFree
Object-based geographic information system (GIS) does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Object-based geographic information system (GIS), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Object-based geographic information system (GIS) will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441482