Method for forming graphic database and system utilizing the method5524202Abstract A graphic database system which comprises a memory unit, a mapping unit and a processing unit in which the memory unit stores a file in which graphic data such as map data expressed as an object in terms of a predetermined description based on an object oriented language is registered, the mapping unit maps the contents of the file on a memory space, and the processing unit accesses the mapped memory space to perform operations such as registering, deleting and updating operations over the graphic data of the file. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
______________________________________
class Class Name {
Type Variable Name;
.
.
.
public:
Method Name ( )
.
.
.
} ;
______________________________________
Therefore, for converting map data into an object, when it is desired to make a structure declaration for a coordinate (point), a rectangle, or a string of coordinate points (polygon) with use of the "C++" language; the coordinate point is expressed in such a manner as shown in FIG. 3, the rectangle is expressed as shown in FIG. 4, and the coordinate string is expressed as shown in FIG. 5. That is, a coordinate point is expressed, for example, a program which follows.
______________________________________
// Coordinate
class Point {
double X,
Y ;
public:
.
.
.
} ;
______________________________________
The lines following the above symbol "//" denote comment lines and the above symbol "// Coordinate" represents that a part following the "class Point" is a comment indicative of a structure declaration for the coordinate. With such a structure declaration, a coordinate point "a point" in FIG. 4(a) is expressed as such a map object (X and Y coordinate values) as shown in FIG. 4(b). Such a map object as expressed in this manner is used to express, for example, the position of a target, the position of a symbol "+" indicative of a church, the position of a symbol " " indicative of a post office or so on in a map. A rectangle is expressed by the following program.
______________________________________
// Rectangle
classRectangle {
Point origin, //Left lower coordinate
corner: //Right upper coordinate
public :
.
.
.
} ;
______________________________________
where, the above "//Rectangle" is a comment indicative of the fact that a part following the "classRectangle" is a structure declaration, the above "//Left lower coordinate" is a comment indicative of the fact that the "Point origin" is a left lower coordinate, and the above "//Right upper coordinate" is a comment indicative of the fact that the "Point corner" is a right upper coordinate. With such a structure declaration, the rectangle "a Rect" shown in FIG. 6(a) is expressed as such a map object as shown in FIG. 6(b). In the example shown in FIG. 6(b), more specifically, an "origin" having an X-Y coordinate point or position (X1, Y1) is associated with a "corner" having an X-Y coordinate point or position (X2, Y2) to express the object. Further, a coordinate string (polygon) is expressed by a program which follows.
______________________________________
//Coordinate string (Polygon)
classPath {
Rectangle box ; //Boundary rectangle of
coordinate string
int npts : //Number of apexes
Point ptlist [1] //Variable length
object
public :
.
.
.
} ;
______________________________________
where, the "//Coordinate string (Polygon)" is a comment indicative of the fact that a part following the "classPath" is a structure declaration for the coordinate string (polygon), the "//Boundary rectangle for coordinate string" is a comment indicative of the fact that the "box" is a boundary rectangle for coordinate string, the "//Number of apexes" is a comment indicative of the fact that the "npts" is the number of apexes, and the "//Variable length object" is a comment indicative of the fact that the "ptlist [1]" is a variable length object. With such a structure declaration, the coordinate string "a Path" shown in FIG. 8(a) is expressed as such a map object as shown in FIG. 8(b). In FIG. 8(a), more specifically, the number of apexes is a total of 5, that is, a start point P1 of a line segment L1, a start point P2 of a line segment L2, a start point P3 of a line segment L3, a start point P4 of a line segment L4, and an end point P5 of the line segment L4 (which point P5 is the same as the start point of the line segment L1). In the object example of FIG. 8(b), a boundary rectangle "box" is expressed by an "Origin" having an X-Y coordinate point or position (X1, Y1) and a "Corner" having an X-Y coordinate point or position (X2, Y2); the number "npts" of elements (apexes) of a polygon coordinate string "a Path" is 5; and "ptlist[0]" to "ptlist[3]" corresponding to the start points P1 to P4 have X-Y coordinate values (X1, Y1) to (X4, Y4) respectively and "ptlist[4]" corresponding to the end point P5 has X-Y coordinate values (X5, Y5). Such a map object as expressed in this way is used to express, for example, a street, a building, a road, an administrative area, etc. in a map. Referring next to FIG. 9, there is shown a diagram for explaining the conceptional structure of a memory map file in the aforementioned graphic database system. In FIG. 9, a memory space 91 has such a structure that a code segment 92, a data segment 93 as a head area and a stack segment 94 are allocated in the order sequentially from a lower address to an upper address. An external memory 95 has a map object file 96 stored therein. The map object file 96 in the external memory 95 is assigned to the data segment 93 of the memory space 91 according to a command "attach call". The heading address of a map area 93A then allocated is hereinafter used to calculate a real address on the basis of an offset for the map object file 96. The map object file 96 is divided into a map object table for registering therein such data for management of map objects as the identification data of the map objects, and a map object pool as a memory pool for storing therein actual map objects. An example of the structure of such a map object file is shown in FIG. 10. The map object file 96 shown in FIG. 10, in more detail, is divided into map object tables 1001 and 1003 and map object pools 1002, 1004 and 1005. Each table is set to have a size corresponding to one page, while each pool is set to have a size corresponding to a multiple of one page. Each table performs such an object area managing function 13 (refer to FIG. 1) as mentioned earlier. With the illustrated map object file 96, since the number of map objects exceeds the number of map objects which the map object table 1001 can manage, the map object table 1003 is extended with a size corresponding to one page. Further, since the map object pool 1002 did not have an idle area sufficient to register required map objects, the map object pool 1004 is extended with a size corresponding to a multiple of one page. In the illustrated example, if the number of map objects is in a range manageable by the map object table 1003, but is not able to be registered in the map object pool 1004 because the size (area) of the map object pool 1004 is small, then an additional map object pool 1005 may be extended with a size corresponding to a multiple of one page, as shown by a dotted line in FIG. 10. In the map object table 1001, there is set a pointer to the next map object management table, i.e., in the present example, to the map object table 1003. Similarly, a NIL pointer indicative of the absence of the next map object management table (the last table) is set in the map object table 1003. FIG. 11 shows a further detailed structure of the map object file 96 of FIG. 10. In FIG. 11, the map object table 1001 comprises an entry 1101 for an offset ("node-prey" in FIG. 11) to the previous node (that is, map object table), an entry 1102 for an offset ("node-next" in FIG. 11) to the next node (that is, map object table), an entry 1103 for an offset ("node-free" in FIG. 11) to an idle list, and a fixed length table 1104 of n of preset areas A1, A2 . . . and An having data on respective map objects registered therein on every map object basis. Each of the elements or areas of the fixed length table 1104, for example, the area A1 has an entry 1105 for inherent data "inst-name" in FIG. 11) such as identification data (ID) for discrimination of specific one of map objects, an entry 1106 for an offset ("inst-off" in FIG. 11) to the map object, and an entry 1107 for the length ("inst-size" in FIG. 11) of the map object. When the number of map objects exceeds the number n of manageable map objects, a new map object management table is extendedly generated at the end of the file. The extended map object management table also have substantially the same structure as the map object table 1001. In the case of the structure shown in FIG. 10, for example, an offset value to the map object management table 1003 is set at the entry 1102 (refer to FIG. 11) of the map object management table 1001, while an offset value to the map object management table 1001 is set at the entry 1101 (refer to FIG. 11) of the new map object management table 1003. In this way, the offset to the previous table and the offset to the next table cause the already existing map object management table to be combined with the extended map object management table. On the other hand, the map object pool 1002 is made in the form of blocks, that is, divided into use blocks for storing therein actual map objects and idle blocks which are not used. In the initial state, all the blocks are idle blocks each of which is managed by an idle list having an entry for the size of the idle block and an entry for an offset for the next idle block. In the map object pool 1002 shown in FIG. 11, the actual map objects are stored in a header block 1108. The block 1108 is made up of a use block 1109 for storing therein, for example, such a map object as shown in FIG. 8(b) and an idle block 1110. The size of the use block 1109 is equal to the size of a map object to be registered. The idle block 1110 is managed by an idle list 1111 which has an entry 1111A ("free-next" in FIG. 11) for the size of the idle block and an entry 1111B for an offset ("free-size" in FIG. 11) to the next idle block. In the entry 1111A, there is set a value indicative of the size of the idle area when the map object pool is divided into blocks before registering the map object (in this case, indicative of the size of the block 1108). After the map object is registered, however, a value corresponding to a subtraction of the size of the map object to be registered from the size of the idle area (in this case, indicative of the size of the idle block 1110) is set in the entry 1111A. Further, when the map object registered in the use block 1109 is released, the value indicative of the size of the idle area when blocked is set in the entry 1111A. That is, under control of the idle list, the non-use block is combined with the returned block (which map object so far registered therein is released) for management. Since the other blocked block (which is an idle block in the initial state) following the header block has also the same structure as the aforementioned header block, the similar processing is carried out for the subsequent blocks. The map object pool 1002 having such an arrangement as mentioned above is referenced by an offset from the map object management table 1001. More specifically, each block having an actual map object stored therein is referenced by an offset value set in an entry (having an offset "inst-off" to the map object in the area including en entry in which the ID of the map object is set) for one of the element areas of the fixed length table 1104 corresponding to the entry 1106. Further, only the idle list 1111 of the header block 1108 is referenced by the offset value of the entry 1103 of the map object management table 1001, and the idle list of the other block is referenced by the offset value in an entry (having an offset "free-next" to the next block) corresponding to the entry 1102. However, the value of an entry of the idle list of the last idle block corresponding to the entry 1102 is "nil". In the case where a block is demanded for a new map object, when an idle area is present in the map object pool, the object is transferred therefrom; whereas when no idle area is present, the map object pool is extended at its last to add the object to the idle list and to be transferred therefrom. For example, when an idle area enough to store the new map object is not present in the map object pool 1004 as shown in FIG. 10, a map object pool 1005 is extendedly provided. In this connection, in FIG. 10, the extensive provision of the map object table 1003 is not followed necessarily the extensive provision of the map object pool 1004. That is, in the case of the presence of an idle area (idle block) in the map object pool 1002, when the map object is stored in the idle area and the rest idle area cannot store a new map object to be registered, the map object 1004 is extendedly provided. With such a structure as mentioned above, the processing operation of the map data system under control of the CPU 28 will next be explained by referring to flowcharts of FIGS. 12 to 17. First, a general flow of processing operation will be explained. As shown in FIG. 12, when a command "attach ()" is input, the CPU 28 calls a mapping subroutine in which a "mmap ()" system call is built, and maps, as a pre-processing operation, the map object file 96 on the memory space 91 according to the subroutine (step 1201). The CPU 28 then accesses the mapped memory area, i.e., the mapped area 93A of the memory space 91 to perform main processing operations (including the registration, referencing/updating and deletion for the map object) over the map object file 96, and repeats such main operations until the operations for the file are completed (steps 1202 and 1203). And the CPU 28, when receiving a command "detract()", calls an unmapping subroutine in which a system call "mumap ()" is built, and unmaps, as a post-processing, the map object file 96 and the memory space 91 (step 1204). In the pre-processing step 1201 of FIG. 12, the CPU 28, as shown in FIG. 13, opens the map object file 96 for the map data (points and polygons) according to the aforementioned mapping subroutine (step 1301) and thereafter, maps the map object file 96 on the memory space 91 and defines the leading address of the mapped memory space as a header address (step 1302). Explanation will then be made sequentially as to the main operations of the CPU 28, that is, the registration, referencing/updating and deletion of the map object. In the registering operation, as shown in FIG. 14, the CPU 28 first checks whether or not an idle area is present in the map object management table 1001 (shed 1401), and if the idle area is absent, performs the extending operation of the map object management table (step 1402). The CPU 28, when finding an idle area in the shed 1401 or completing the step 1402, examines the presence or absence of an idle block in the map object pool 1002 (step 1403). The absence of an idle block causes the CPU 28 to perform the extending operation of the map object pool (step 1404). The presence of an idle block in the step 1403 or the completion of the step 1404 causes the CPU 28 to obtain the memory block necessary to store the map object requested by the application from the map object pool on the basis of an idle list starting with the entry 1103 of the header object management table (step 1405). And the ID of the map object to be registered, the offset to the obtained block, and the length (bite number) of the map object to be registered are registered in entries, corresponding to the entries 1105, 1106 and 1107 respectively, of the object management table; and thereafter the offset is converted into a real address which is returned to the application. More specifically, the CPU 28 adds together the header address and an object relative address (offset), defines the addition value as an absolute address (real address), and returns the real address to the application (step 1406). The application copies the map object to be registered at the returned real address (step 1407). The CPU 28, in the referencing/updating operation shown in FIG. 15, then compares the ID of the map object requested by the application with the ID of the map object set in the "inst-name" entry inherent to the map object within the map object management table 1001 to search the same ID (step 1501). The CPU 28 converts the offset value set in an entry corresponding to the entry 1106 of the thus obtained ID as well as an area expressed in terms of byte number set in an entry corresponding to the entry 1107 into real addresses, and returns these real addresses to the application. That is, the CPU adds together the header address and the object relative address and returns the addition value to the application (step 1502). With this, the application is able to reference/update the real address as the map object. Subsequently, in the deleting operation shown in FIG. 16, the CPU 28 compares the ID of the map object requested by the application with the ID of the map object set in an entry corresponding to the entry 1105 of the map object management table 1001 to search the same ID (step 1601). The CPU then adds in an idle list a memory block of the map object pool 1001 so far occupied by the map object to be deleted to delete the corresponding map object from the map object management table 1001 (step 1602). The memory block added in the idle list can be put in its re-usable state. Finally, the post-processing will be explained. As shown in FIG. 17, the CPU 28 unmaps the map object file 96 and the memory space 91 according to the aforementioned unmapping subroutine (step 1701) and then closes the map object file (step 1702). Explanation has been made as to how to process when the map object file (map database) locally exists in the external memory in the foregoing embodiment. Next explanation will be directed to how to process when the map object file globally exists in the external memory. FIG. 18 shows a so-called multi-user environment in which a plurality of users share the map object file present on a network. In FIG. 18, such a local area network (which will be referred to as the LAN, hereinafter) 1801 as, e.g., an Ethernet is connected with a server machine 1802 having an external memory 1802A functioning of storing therein a map database or map object file and also with a client machine 1803. A network file system (which will be referred to as the NFS, hereinafter) is set in each of the server and client machines 1802 and 1803. The NFS is a function of forming a network-transparent file system, which function is well known (for example, SunOS Release 4.0). The NFS setting of the server side work and the client side work can be carried out with use of the known technique and thus explanation thereof is omitted. When the NFS is set on both the server and client sides, the client machine 1803 performs a predetermined procedure to open the map object file in the external memory 1802A of the server machine 1802 through the LAN 1801 and to map the contents of the file on the locally existing memory space 1803A. The processing after the mapping can be carried out in substantially the same manner as for the aforementioned processing. Of course, the server machine 1802 also can map the map object file in the external memory 1802A on the locally existing memory space 1802B as mentioned above. It goes without saying that, when a plurality of users sharing the database access the database, a semaphore is used. In the aforementioned embodiment, a specific map object (polygon) can be retrieved by designating a desired position on the map displayed on the map display unit 24 with use of the mouse 21. In more detail, the coordinate transformer 27 transforms the coordinate values of a point on the map on the display screen of the map display unit 24 designated by the mouse 21 into corresponding coordinate values in the normalized coordinate system. The CPU 28 retrieves the corresponding specific map object (polygon) from the map object file on the basis of the transformed coordinate values. The retrieving operation of the specific map object (polygon) may be realized, for example, by examining whether or not the transformed coordinate values are included within the boundary rectangle "box" (refer to FIG. 8(a)) of the map object. In other words, this is realized, for example, by checking whether or not the transformed coordinate values are included within the boundary area "box" defined by the "Origin" coordinate values (X1, Y1) and the "Corner" coordinate values (X2, Y2) in the item "box" of FIG. 8(b). If the transformed values are included within the boundary area, then by knowing an offset "inst-off" referencing a block in which the specific map object is stored, an inherent data (ID) "inst-name" combined with the offset "inst-off" can be specified. Although the map data has been employed as graphic data in the foregoing embodiment, the present invention is not limited to the specific example, but any data may be handled so long as the data are included in the graphic data. For example, as the graphic data, data on design drawing designed by a computer aid design (CAD) may be used. As has been explained in the foregoing, in accordance with the present embodiment, since map data are converted into map objects which form a database and a file as the database is mapped on the memory space, the file input/output of the map data can be apparently or virtually eliminated and the need of such special processing as data conversion, which has so far been necessary for the file input/output, that is, code conversion in the pre- processing and post-processing can be eliminated and thus its overhead can be suppressed to its minimum level. Further, in a distributed processing/multi-user environment, even when a plurality of users access a file and thus a file competition takes place, since a change in the contents of the map data reflects on the map object file, the plurality of users can reference and update the-map data at the same time. In particular, the use of the NFS enables the user to know the renewed map data on a real time basis, which results in that efficient working on the network can be realized. Further, since map data are stored in a database in the form of map objects, such map data that becomes necessary for developing a city or a local area, for example, map data expressing an anti-fire area, a residential area or a commercial area can be easily generated. Note that "SunOS" is a trademark of the Sun Micro Systems Ltd. (U.S.A.) and "NFS" is a registered trademark of the Sun Micro Systems Ltd. As has been disclosed in the foregoing, in accordance with the present invention, the contents of a file having a group of graphic objects registered therein are mapped on the memory space so that the accessing of the mapped memory space causes reading/writing of the graphic object from into the file, whereby the need for code conversion, which has been necessary in the prior art, can be eliminated and thus the overhead of the system can be remarkably reduced. Further, when a change in the map data on the mapped memory space takes place, the modification contents reflect on the file. As a result, even when a file competition occurs at the time of accessing operation in a distributed processing/multi-user environment, file matching can be maintained. The present invention can be modified in various ways without departing the spirit and major features of the invention. Therefore, it should be appreciated that the foregoing embodiment is disclosed merely as an example and the present invention should not be restricted by the embodiment. The scope of the present invention is defined by the scope of the attached claims and should not be restricted by the body of the specification. Further, the present invention covers all equivalents, alternations and modifications included in the scope of the appended claims.
|
Same subclass Same class Consider this |
||||||||||