Graphic data searching and storage method

• US 5,144,679 A
• Filed: 02/04/1991
• Issued: 09/01/1992
• Est. Priority Date: 06/29/1987
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd., Hitachi Seiko Limited
• Original Assignee: Hitachi, Ltd., Hitachi Seiko Limited
• Inventors: Watanabe, Kazuo, Otsu, Fumitaka, Kakumoto, Shigeru, Kato, Masayasu
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US07/650,404
• Time in Patent Office: 575 Days
• Field of Search: 382/1, 382/22, 382/25, 382/48, 382/56, 382/61, 340/747, 340/748, 340/798, 340/799
• US Class Current: 382/113
• CPC Class Codes: G06F 16/5854 using shape and object relationship

Abstract

In correspondence with the graphic data having a spatial extent, there is the address data table configured of arrays, the dimension of which are not smaller in number than the dimensions of the extent of the graphic data. Coordinate transformation is performed between the graphic data and the address data table, whereby any desired point on each figure can be brought into correspondence with one array number of the address data table. Those memory addresses of a graphic data table at which the individual graphic data items are sorted, are subsequently stored in the address data table. In case of searching for graphic data located at any desired position, the corresponding array number of the address data table is obtained on the basis of the position, whereupon the desired figure can be searched for through that memory address to the graphic data which is stored. In a case where the memory space of the address data table corresponding to any desired one of cells (each of which is a subspace of a graphic space) is full, relevant information of indirectly utilizing a memory space assigned to another of the cells is substitutionally stored in the address data table, conjointly with the memory address of the graphic data table storing the corresponding graphic data so that the address data table can be used efficiently. When the figure discriminators of the graphic data are stored in the address data, lines or points, the relevant attribute information items, or the like can be extracted selectively and efficiently by deciding the figure discriminators on the searching operation.

Claims

1. A graphic data handling method, comprising:

dividing a graphic image of figures into a plurality of graphic cells;

providing a graphic data table for storing graphic data for defining the figures within the cells;

providing an address data table which includes plurality of memory spaces of fixed capacity that are respectively assigned one-to one to the cells, for normally storing therein memory address pointers for the graphic data table, which memory address pointers respectively correspond to the figures in the cells; and

when a memory address pointer for the graphic data that corresponds to the figures in a pertinent cell cannot be stored in the memory space assigned to the pertinent cell, substitutionally storing said memory address pointer for the pertinent cell that cannot be so stored, in a memory space, as an overflow memory space, which is assigned to a different cell other than said pertinent cell.

2. The method of claim 1, including storing information indicative of the substitutional storing in the memory space of the pertinent cell of the address data table.

3. The method of claim 1, wherein said step of providing a graphic data table stores graphic data for the cells in random order independent of the position of the cells relative to the graphic image.

4. The method of claim 1, wherein said step of providing an address data table provides the memory spaces corresponding to the cells in a computer memory sequentially in a fixed order dependent upon the positions of the cells in the graphic image.

5. A method of claim 1, including retrieving graphic data from the graphic data table by:

defining an area that is only a part of the graphic image;

transposing the area into a representation of the cells within the area;

searing the memory spaces of the address data table corresponding to the cells of the area and memory spaces having substitutional storing of address pointers of the area, without searching the memory spaces corresponding to the remaining cells of the graphic image and determining address pointers therein assignable to the area; and

fetching from computer memory the graphic data in the graphic data table using only the pointers found in said searching.

6. The method of claim 2, including retrieving graphic data from the graphic data table by:

defining an area that is only a part of the graphic image;

transposing the area into a representation of the cells within the area;

searching the memory spaces of the address data table corresponding to the cells of the area and memory spaces having substitutional storing of address pointers of the area, without searching the memory spaces corresponding to the remaining cells of the graphic image and determining address pointers therein assignable to the area;

from the information indicative of the substitutional storing found in said step of searching, determining substitutional storage in other cells that contain address pointers relating to the cells of the area and retrieving the related address pointers; and

fetching from computer memory the graphic data from the graphic data table in accordance with the retrieved related address pointers.

7. The method of claim 1, including setting at least one coded number for each memory space of the addressed data table to indicate which ones of the different cells are substitutionally storing the address pointers for the pertinent cell.

8. The method of claim 1, wherein the different cells have a fixed physical location in the graphic image relative to the pertinent cell for each cell in the graphic image.

9. The method of claim 8, wherein the fixed physical location for the different cells is based on the criteria of physically directly adjacent cells in the graphic image.

10. The method of claim 1, wherein said step of providing a graphic data table stores graphic data for end points, for node points, and an intersection with the pertinent cell boundary for each line in or passing through the pertinent cell.

11. The method of claim 10, wherein said step of forming a graphic data table includes storing therein selective intermediate points and attribute information concerning the figures of the graphic image within the pertinent cell, which figures include the lines.

12. The method of claim 1, further including storing, with respect to each address pointer in the address data table, a data field indicating the type of figure of graphic data pointed to by the address pointer.

13. The method according to claim 1, wherein said step of providing an address data table includes storing a data field including a single bit for each address pointer indicating whether the address pointer is an address pointer for the pertinent cell.

14. The method according to claim 1, further including storing a plurality of bits corresponding in number to said different cells having a specific physical relationship with the pertinent cell that is the same for each cell of the graphic image, and setting the bits to indicate which ones of the memory spaces assigned to said different cells contain memory address pointers for the graphic data of the pertinent cell.

15. The method of claim 1, performed completely by a computer system having a graphic data storage program, a graphic data searching program, a memory containing the address data table, a memory containing the graphic data table, an input device for inputting the graphic image, and a data output device for outputting searching program results.

16. The method of claim 1, further including providing an attribute information data table separate from said graphic data table for indicating attributes of figures within each cell, and wherein said step of providing an address data table provides address pointers in the address data table for addresses of attribute information in the attribute information data table correlated to the cells in the same manner that the graphic data in the graphic data table is correlated to the cells, and including with each pointer in the address data table a field indicating whether the pointer relates to the graphic data table or the attribute information data table.

17. The method of claim 1, including computing the size of address table space required for an input graphic image and dividing it into cell spaces;

determining if all graphic data items of the image have been processed, and if they have, ending the storage program, and if they have not, determining if all address pointers for the graphic image have been processed;

if all address pointers have not been processed, identifying a cell from coordinates of points in the graphic image, computing an address pointer of the cell, finding an empty space within the address data table, and storing the address pointer in the empty space of the address table according to the steps of forming an address table; and

thereafter returning to the determination if all address pointers of the graphic image having been processed.

18. The method of claim 17, wherein said step of forming an address data table includes forming a field with each address pointer that identifies the cell having the graphic data in the graphic data table pointed to by the pointer.

19. The method of claim 1, including determining the address of a different cell than said pertinent cell within the address data table by the address of the pertinent cell within the address data table and a fixed number unique to the physical location of the different cell relative to the pertinent cell in the graphic image, which is the same for the same physical relationship between any cell as a pertinent cell and its different cells within the graphic image.

20. The method of claim 4, including determining the address of a different cell than said pertinent cell within the address table by the address of the pertinent cell within the address data table and a fixed number unique to the physical location of the different cell relative to the pertinent cell in the graphic image, which is the same for the same physical relationship between any cell as a pertinent cell and its different cells within the graphic image.

21. The method of claim 20, wherein the fixed physical location for the different cells is based on the criteria of physically directly adjacent cells in the graphic image.

22. The method of claim 14, wherein said step of providing a graphic data table stores graphic data for the cells in random order independent of the position of the cells relative to the graphic image.

23. The method of claim 22, wherein said step of providing a graphic data table stores graphic data for end points, for node points, and an intersection with the pertinent cell boundary of reach line in or passing through the pertinent cell.

24. The method of claim 1, wherein the spaces are all of the same fixed capacity.

25. The method of claim 1, wherein the cells are all of equal size.

26. A graphic data handling method, comprising:

dividing a graphic image of figures into a plurality of graphic cells;

storing graphic data for defining the figures within the cells;

providing a plurality of memory spaces respectively assigned one-to-one to the cells, for normally storing therein memory address pointers for the graphic data, which memory address pointers respectively correspond to the figures in the cells; and

when a memory address pointer for the graphic data that corresponds to the figures in a pertinent cell cannot be stored in the memory space assigned to the pertinent cell due to an overflow condition in the memory space assigned to the pertinent cell, substitutionally storing said memory address pointer for the pertinent cell that cannot be so stored, in a memory space, as an overflow memory space, which is assigned to a different cell other than said pertinent cell.

27. The method of claim 26, including storing information indicative of the substitutional storing in the memory space of the pertinent cell of the address data table, and wherein said step of providing a graphic data table stores graphic data for the cells in random order independent of the position of the cells relative to the graphic image.

28. The method of claim 27, wherein said step of providing a graphic data table stores graphic data for end points, for node points, and an intersection with the pertinent cell boundary for each line in or passing through the pertinent cell.

29. A graphic data handling system to be operated by a computer system having a graphic data storage program, a graphic data searching program, a memory containing the address data table, a memory containing the graphic data table, an input device for inputting the graphic image, and a data output device for outputting searching program results, comprising:

means for dividing a graphic image of figures into a plurality of graphic cells;

means for storing graphic data for defining the figures within the cells in a graphic data table in random order independent of the position of the cells relative to the graphic image;

means for providing an address data table which includes a plurality of memory spaces of fixed capacity respectively assigned one-to-one to the cells, and for normally storing therein memory address pointers to the graphic data table, which memory address pointers respectively correspond to the figures in the cells;

means for substitutionally storing a memory address pointer for a pertinent cell in a memory space, as an overflow memory space, which is assigned to a cell which is different from the cell assigned to the pertinent cell, when the memory address pointer cannot be stored in the memory space assigned to the pertinent cell; and

means for storing information indicative of the substitutional storing in the memory space of the pertinent cell of the address data table.

30. The system of claim 29, wherein said means for providing an address data table provides the memory spaces corresponding to the cells in a computer memory sequentially in a fixed order dependent upon the positions of the cells in the graphic image.

31. A system of claim 29, including means for retrieving graphic data from the graphic data table including means for transposing an area that is only a part of the graphic image into a representation of the cells within the area, means for searching the memory spaces of the address data table corresponding to the cells of the area and memory spaces having substitutional storing of address pointers of the area, without searching the memory spaces corresponding to the remaining cells of the graphic image and determining address pointers therein assignable to the area and means for fetching from computer memory the graphic data in the graphic data table using only the pointers found by said means for searching.

32. The system according to claim 29, further including means for storing a plurality of bits corresponding in number to said different cells having a specific physical relationship with the pertinent cell that is the same for each cell of the graphic image, and setting the bits to indicate which ones of the memory spaces assigned to said different cells contain memory address pointers for the graphic data of the pertinent cell.

33. The system of claim 30, including means for determining the address of a different cell than the pertinent cell within the address data table by the address of the pertinent cell within the address data table and a fixed number unique to the physical location of the different cell relative to the pertinent cell in the graphic image, which is the same for the same physical relationship between any cell as a pertinent cell and its different cells within the graphic image.

34. The system of claim 30, including means for retrieving graphic data from the graphic data table including means for transposing an area that is only a part of the graphic image into a representation of the cells within the area, means for searching the memory spaces of the address data table corresponding to the cells of the area and memory spaces having substitutional storing of address pointers of the area, without searching the memory spaces corresponding to the remaining cells of the graphic image and determining address pointers therein assignable to the area and means for fetching from computer memory the graphic data in the graphic data table using only the pointers found by said means for searching.

35. The system of claim 30, further including means for storing a plurality of bits corresponding in number to the different cells having a specific physical relationship with the pertinent cell that is the same for each cell of the graphic image, and setting the bits to indicate which ones of the memory spaces assigned to said different cells contain memory address pointers for the graphic data of the pertinent cell.

36. The system of claim 34, further including means for storing a plurality of bits corresponding in number to the different cells having a specific physical relationship with the pertinent cell that is the same for each cell of the graphic image, and setting the bits to indicate which ones of the memory spaces assigned to said different cells contain memory address pointers for the graphic data of the pertinent cell.

37. The system of claim 36, including means for determining the address of one of said different cells within the address data table by the address of the pertinent cell within the address data table and a fixed number unique to the physical location of the different cell relative to the pertinent cell in the graphic image, which is the same for the same physical relationship between any cell as a pertinent cell and its different cells within the graphic image.

38. The system of claim 34, including means for determining the address of a different cell than said pertinent cell within the address data table by the address of the pertinent cell within the address data table and a fixed number unique to the physical location of the different cell relative to the pertinent cell in the graphic image, which is the same for the same physical relationship between any cell as a pertinent cell and its different cells within the graphic image.

39. The system of claim 35, including means for determining the address of a different cell than said pertinent cell within the address data table by the address of the pertinent cell within the address data table and a fixed number unique to the physical location of the different cell relative to the pertinent cell in the graphic image, which is the same for the same physical relationship between any cell as a pertinent cell and its different cells within the graphic image.

40. The system of claim 31, further including means for storing a plurality of bits corresponding in number to the different cells having a specific physical relationship with the pertinent cell that is the same for each cell of the graphic image, and setting the bits to indicate which one of the memory spaces assigned to the different cells contain memory address pointers for the graphic data of the pertinent cell.