The present invention relates to a method of performing interactive retrieval and edition of drawing information of various design schematics and maps at a high speed. More particularly, the present invention concerns a high-speed processing procedure suited for drawing of a type which contains components or elements having a magnitude undergoing steep or abrupt variation.
Heretofore, a variety of high-speed processing procedures have been proposed for retrieving at a high speed a drawing including spatial position information concerning two- or more-dimensional objects, such as schematics and maps. By way of example, JP-A No. 62-145369 (hereinafter referred to as a reference (1)) discloses a high-speed processing method for the drawing according to which the multi-dimensional space of a schematic is divided into latices of a predetermined grid constant (hereinafter referred to as meshes), wherein the positions of the meshes traversed by individual picture elements constituting the drawing pattern are stored so that upon retrieval, only a limited number of the picture elements are retrieved to be subjected to the processing from the designated mesh positions, to thereby allow the processing to be speeded up.
In J. L. Bentley's article entitled "Multi-Dimensional Binary Search Trees Used For Associative Searching" appearing in "COMMUN. ACM." 19, 9(1975) (hereinafter referred to as the reference (2)), there is proposed a domain dividing method known as the K-D tree method, according to which a schematic is divided into areas of different sizes (hereinafter referred to as key areas) covering individual elements instead of being divided into meshes through the procedure based on the binary division system, wherein the division into key areas and tree structurization are repeated until the number of the picture elements contained in the individual key areas becomes uniform. This procedure allows the number of the key areas used for limitation of the picture elements in the processing to be reduced.
In general, however, the design schematics as well as maps include the picture elements of which magnitudes vary remarkably. Besides, they are frequently subjected to editing manipulations such as alteration of the picture element position and others. Under the circumstance, when the procedure disclosed in the reference (1) is adopted, the number of the meshes traversed by the picture element having a large size is increased. Accordingly, in case the processing such as displacement of the picture element positions is to be performed at the stage of edition, the volume of processing involved in the alteration of the mesh positions traversed by the picture elements will be significantly increased, presenting a problem. On the other hand, in case the procedure disclosed in the reference (2) is applied, there are required a series of processings which includes determination of the position within the key area to which picture elements have been displaced through the editing procedure and verification of the predetermined positions by tracing the structural tree in the key areas for modifying the tree structure. However, these processings are in general of a complicated nature. Besides, the modification is inevitably accompanied with remarkable degradation in performance of the K-D tree and is rendered actually impractical, thus giving rise to a problem.