Drawing information processing method and apparatus

• US 4,974,175 A
• Filed: 06/17/1988
• Issued: 11/27/1990
• Est. Priority Date: 06/19/1987
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Suzuki, Goro, Hamada, Nobuhiro
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/208,115
• Time in Patent Office: 893 Days
• Field of Search: 364/521, 364/518, 364/490, 364/491, 364/522, 357/41, 357/42, 357/54, 437/51, 340/747, 340/750
• US Class Current: 345/619
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

An apparatus and method for processing information of a drawing comprises steps of defining figure data representing figures, respectively, included in a drawing, preparing a plurality of regions called as field block memory regions for storing the figure data so that they can be selectively read out for edition of a drawing later on, and determining a usable range in each of the field block memories in accordance with the number of the figures included in the drawing. In a preferred mode, the method further includes steps of dividing the drawing into congruent rectangles called as buckets in a number determined in accordance with the number of the figures included in the drawing, allocating the abovementioned field block memory regions to the buckets, respectively, and storing the figure data in the memory region allocated to the bucket to which the associated figure belongs.

Claims

1. A method of processing information of a drawing illustrating a plurality of original figures included in a predetermined rectangular space defined by at least two dimensions for thereby storing data representing the respective original figures which are to be read out for determining any original figure at least a part of which is located within a given portion of the drawing, said method comprising:

a first step of representing each of said original figures by a first-stage figure representing a selected one of a plurality of first rectangular areas which are defined by said at least two dimensions defining said rectangular space and covering completely said original figures, said selected one of the first rectangular areas being smaller in size than any other first rectangular area;

a second step of preparing in a predetermined memory a first memory section including a plurality of memory regions and associated managing regions, and determining an upper limit of usable range of each of said memory regions as function of total number n of said figures included in said drawing;

a third step of storing position data capable of defining the position of each of said first-stage figures within said drawing sequentially in one of the memory regions of said first memory section;

a fourth step of storing the positional data of any one of said first-stage figures when storing of the position data of said one first stage figure at said third step will exceed said upper limit of the usable range of the one memory region, in a succeeding memory region of the same memory section;

a fifth step of defining a second stage figure representing a selected one of second rectangular areas which are defined by said at least two dimensions defining said rectangular space and covering all the first-stage figures corresponding to the position data stored in each of the memory regions of said first memory section, said selected one of said second rectangular areas being smaller in size than any other second rectangular area; and

a sixth step of storing position data capable of defining the position of said second-stage figure within said drawing in the managing region associated with the memory region of said first memory section in which said first-state figure covered by said second-stage figure is stored.

2. An apparatus for processing information of a drawing illustrating a plurality of original figures contained in a predetermined rectangular space defined by at least two dimensions for storing data representing the respective original figures to be read out for determining any original figure at least a part of which is located within a given portion of the drawing, said apparatus comprising:

input means for externally inputting figure information containing figure data capable of defining positions and shapes of said original figures in said drawing and a total number n of said original figures included in said drawing;

memory means having first memory section including a plurality of memory regions and associated managing regions;

first means for determining a first-stage figure representing a selected one of first rectangular areas which are defined by the same dimensions as those defining said rectangular space and covering completely each of said original figures on the basis of said inputted figure data, said selected one of said first rectangular areas being smaller in size than any other first rectangular area and determining position data indicating the positions of said first-stage figures on said drawing;

second means for establishing the upper limit of a usable range of each of said memory regions as a function of n;

third means for storing the position data of said firststage figures sequentially into one of said memory regions, so long as the upper limit of the usable range of said one memory region is not exceeded, and storing, when the position data of any of the first-stage figures cannot be stored in said one memory region without exceeding its upper limit of the usable range, the position data of said one and succeeding ones of the first-stage figures into a next memory region succeeding to said one memory region; and

fourth means for defining a second stage figure representing a selected one of second rectangular areas which are defined by the same dimensions as those defining said rectangular space and covering all the first stage figures corresponding to the position data stored in each of said memory regions of said first memory section, said selected one of the second rectangular areas being smaller in size than any other second rectangular area, determining position data indicating the position of said second-stage figure on said drawing and storing said position data in the managing region associated with the memory region.

3. A method of processing information of a drawing illustrating a plurality of original figures for storing data representing the respective original figures to be read out for determining any figure at least a part of which is viewed in a given rectangular window of the drawing, said method comprising the steps of:

representing each of said original figures by a first-stage figure which is a selected one of first rectangles which cover completely the original figure, said selected one of said first rectangles being smaller in size than any other first rectangle;

preparing in a predetermined memory first and second memory sections each including a plurality of memory regions and associated managing regions and determining an upper limit of usable range of each of said memory regions as a function of total number n of said figures included in said drawing;

storing position data capable of defining the positions of said first-stage figures in said drawing sequentially in one of the memory regions of said first memory section;

storing the position data of any one of said first-stage figures when the position data of said one first-stage figure cannot be stored in said one memory region without exceeding its upper limit of the usable range, in a succeeding memory region of the same memory section;

defining a second-stage figure which is a selected one of second rectangles which cover all the first-stage figures of which the position data are stored in each of the memory regions of said first memory section, said selected one of said second rectangle being smaller in size than any other second rectangle;

storing position data defining a position of each of said second-stage figures in said drawing in the managing region associated with the memory region of said first memory section in which the position data of said first-stage figures covered by said second-stage figure are stored;

storing the position data defining the positions of said second-stage figures in said drawing sequentially in one of the memory regions of said second memory section;

storing when the position data of any one of said second stage figures can not be stored in said one memory region of said second memory without exceeding its upper limit of the usable range of said one memory region of said second memory section the data of said one and succeeding ones of said second stage figures sequentially, into a succeeding memory region of the same memory section;

defining a third-stage figure which is a selected one of third rectangles which cover all of said second-stage figures corresponding to the position data stored in each of the memory regions of said second memory section, said selected one of said third rectangles being smaller in size than any other third rectangle; and

storing the position data defining a position of said third-stage figure in said drawing in the managing regions associated with the memory region of said second memory section in which the position data of said second-stage figures covered by said third-stage figure are stored.

4. A method of processing information of a drawing according to claim 3, further including steps of:

dividing said drawing in correspondence with said first and second stage figures into first and second buckets having same sizes and same shapes, respectively, of said first and second buckets being determined as a function of n^2/3 and n^1/3 respectively;

making each of said first stage figures belong to one of the first buckets resulting from said division in which a particular point of said each first stage figure is located;

allocating the memory regions of said first memory section to said first buckets, respectively;

storing said position data of each of said first stage figures in one of the memory regions of said first memory section allocated to one of said first blocks to which said each first stage figure belong, respectively;

making each of said second stage figures belong to one of said second buckets in which a particular point of said each second stage figure is located; and

storing said position data of each of said second stage figures in one of the memory regions of said second memory section allocated to the second bucket to which said each second stage figure belongs, respectively.

5. An apparatus for processing information of a drawing illustrating a plurality of original figures for storing data representing the respective figure to be read out for determining any original figure at least a part of which is viewed in a given rectangular window of the drawing, said apparatus comprising:

input means for externally inputting figure information containing figure data defining the positions and shapes of said figures on said drawing and a global number n of said original figures included in said drawing;

memory means having first and second memory sections, each including a plurality of memory regions and associated managing regions;

first means for determining a first-stage figure which is a selected one of first rectangles which cover completely each of said original figures on the basis of said inputted figure data, said selected one of said first rectangles being smaller in size than any other first rectangle and determining position data indicating a position of said first-stage figure on said drawing;

second means for establishing an upper limit of a usable range of each of the memory regions of said first and second memory sections as a function of n^1/3 ;

third means for storing the position data of said firststage figures of the respective original sequentially into one of said memory regions of said first memory section, and storing, when the position data of any one of said first-stage figures cannot be stored in said one memory region without exceeding its upper limit of the usable range, the position data of said one and succeeding ones of said first stage figures sequentially into a succeeding one of said memory regions of said first memory section;

fourth means for determining a second-stage figure which is a selected one of second rectangles which cover completely all of said first stage figures corresponding to the position data stored in each of the memory regions of said first memory section, said selected one of said second rectangles being smaller in size than any other second rectangle and storing position data of the second-stage figure in the managing region associated with said each memory regions;

fifth means for storing the position data of said secondstage figures sequentially into one of said memory region of said second memory section, and storing, when the position data of any one of said second-stage figures cannot be stored in said one memory region without exceeding its upper limit of the usable range, the position data of said one and succeeding ones of said second-stage figures sequentially into a succeeding one of said emory regions of said second memory section; and

sixth means for defining a third-stage figure which is a selected one of third rectangles which cover all the second-stage figures corresponding to the position data stored in each of the memory regions of said second memory section, said selected one of the third rectangles being smaller in size than any other third rectangle and storing said position data of said third-stage figure in the managing region associated with the memory region.

6. An apparatus for processing information of a drawing according to claim 5, further including:

seventh means for dividing said drawing into first and second buckets having same sizes and same shapes, respectively, in numbers of said first and second buckets being determined as function of n^2/3 and n^1/3, respectively, in correspondence to said first and second stage figures; and

eighth means for determining for each of said first-stage figures one of said first buckets in which a particular point on each of said each first-stage figures is located and making said figure having said particular point thereon belong to said one first bucket;

wherein the memory regions of said first memory section are allocated to said first buckets, respectively, said position data of each of said first stage figures being stored in one of the memory regions of said first memory section allocated to said one first bucket to which said first stage figure associated with said position data belongs;

the memory regions of said second memory section being allocated to said second buckets, respectively, said position data of each of said second stage figures being stored in one of the memory regions of said second memory section allocated to the second bucket to which said each second stage figure belongs.

7. A method of processing information of a drawing illustrating a plurality of original figures contained in a predetermined rectangular space defined by at least two dimensions for thereby storing data representing the respective figures which are to be read out for determining any original figure at least a part of which is located within a given portion of the drawing, said method comprising:

a first step of representing each of the original figures by a first-stage figure representing a selected one of first rectangular areas which are defined by the same dimensions as those defining said rectangular space and covering completely the original figure, said selected one of said first rectangular areas being smaller in size than any other first rectangular area;

a second step of preparing in a predetermined memory first to (k-1)th memory sections each including a plurality of memory regions and associated meaning regions, where k is an integer larger than 2, each memory region having an upper limit of its usable range determined as a function of n1/k;

a third step of storing position data defining a position of each of 1-th stage figures, where i=1, 2, 3, . . . (k-1), within said drawing sequentially in one of the memory regions of the i=th memory section;

a fourth step of storing the position data of any one of the i-th stage figure cannot be stored in said one memory region at the third step without exceeding the upper limit of the usable range of said one memory region, in a succeeding memory region of the i-th memory section;

a fifth step of defining a (i+1)th stage figure representing a selected one of second rectangular areas which are defined by the same dimensions as those defining the rectangular space and covering all the i-th stage figures whose position data are stored in each of said memory regions of said i-th memory section, said selected one of said second rectangular area being smaller in size than any other second rectangular area; and

a sixth step of storing position data defining a position of the (i+1)th stage figure within the drawing in the managing region of said i-th memory section associated with memory region in which the i-th stage figures covered by the (i+1)th stage figure are stored.

8. A method of processing information of a drawing according to claim 7, further including:

a step of classifying said original figures into predetermined plural groups in accordance with the sizes of said original figures; and

a step of dividing each of said first to (k-1)th memory sections into a plurality of subsections in correspondence with said plural groups, and determining the upper limit of the usable range of memory region of each subsection as a function of the total number of the original figures classified to the corresponding group;

wherein said third to sixth steps are applied to the respective groups of the original figures, separately, so that the position data of said i-th stage figures associated with the original figures of any one group are stored in the memory regions of said subsection of said i-th memory section corresponding to said one group.

9. A method of processing information of a drawing according to claim 7, further including:

a step of classifying said original figures into predetermined plural groups in accordance with the features of said original figures; and

a step of dividing each of said first to (k-1)th memory sections into a plurality of subsections in correspondence with said plural groups, and determining the upper limit of the usable range of memory region of each subsection as a function of the total number of the original figures classified to the corresponding group;

wherein said third to sixth steps are applied to the respective groups of the original figures, separately so that, the position data of said i-th stage figures associated with the original figures of any one group are stored in the memory regions of said subsection of said i-th memory corresponding to said one group.

10. A method of processing information of a drawing according to claim 7, further including:

a step of dividing said drawing in correspondence with said i-th stage figures (i-1, 2, . . . , k-1) into a number of buckets having a same size and a same shape determined as a function of n, k and i;

a step of making each of said i-th stage figures belong to one of the buckets in which a particular point on said figure is located; and

a step of allocating the memory regions of said i-th memory section to said bucket, respectively;

wherein at said third steps, said position data of each of said i-th stage figures are stored in the memory region of said i-th memory section allocated to the bucket to which said i-th stage figure belongs.

11. A method of processing information of a drawing according to claim 10, wherein said drawing is divided into n.sup.(k-1)/k, n.sup.(k-2)/k, . . . , n^1/k buckets with respect to said first, second, . . . , (k-1)th stage figures, respectively.

12. A method of processing information of a drawing according to claim 10, further including:

a step of selecting one original figure from the original figures of which information has already been stored in said memory and determining one of the buckets into which the drawing is divided with respect to said i-th stage figures, in which one bucket (called as a current bucket) the i-th stage figure associated with said selected one original figure is located;

a step of transforming said selected one original figure into a new figure differing from said selected one figure at least in the position or shape, determining the i-th stage figure for the new figure, and determining one bucket (called as post-transformation bucket) of said buckets divided with respect to said i-th stage figures, said one bucket (post-transformation bucket) covering the position of said i-th stage figure;

a step of deciding whether or not said current bucket is same as said post-transformation bucket;

a step of erasing the data of the i-th stage figure relating to said selected one original figure stored in the memory region of said i-th memory section, when said current bucket is same as said post-transformation bucket, and storing subsequently the data of the i-th stage figure relating to said new figure in said memory region; and

a step of preparing a new memory region in said i-th memory section, when said current bucket differs from said post-transformation bucket, and storing the data of the i-th stage figure relating to said new figure in said new memory region while erasing the data of the i-th stage figure relating to said selected one original figure in said memory region.

13. An apparatus for processing information of a drawing illustrating a plurality of original figures contained in a predetermined rectangular space defined by at least two dimensions for thereby storing data representing the respective figures which are to be read out for determining any original figure at least a part of which is located within a given portion of the drawing, said apparatus comprising:

input means for externally inputting figure information containing figure data defining positions and shapes of said individual original figures in said drawings included in the drawing;

memory means having first to (k-1)th memory sections each including a plurality of memory regions and associated managing regions, where k is an integer larger than 2;

first means for representing each of the original figures by a first-stage figure representing a selected one of first rectangular areas which are defined by the same dimensions as those defining said rectangular space and covering completely the original figure based on the inputted figure data, said selected one of said first rectangular areas being smaller in size than any other first rectangular area and determining position data indicating the position of said first-stage figure on said drawing;

second means for establishing an upper limit of a usable range of each of said memory regions as a function of n^1/k ;

third means for storing position data defining respective positions of i-th stage figures, where i =1, 2, 3, . . . (k-1), within said drawing sequentially in one of the memory regions of the i-th memory section so long as the upper limit of the usable range of said one memory region is not exceeded;

fourth means for storing the position data of any one of the i-th stage figure, when the position data of said one i-th stage figures cannot be stored in said one memory region without exceeding the upper limit of the usable range of said one memory region, in a succeeding memory region of the i-th memory section;

fifth means for defining a (i+1)th stage figure representing a selected one of second rectangular areas which are defined by the same dimensions as those defining the rectangular space and covering all the i-th stage figures whose position data are stored in each of said memory regions of said i-th memory section, said selected one of said second rectangular areas being smaller in size than any other second rectangular area; and

sixth means for storing position data defining a position of the (i+1)th stage figure within the drawing in the managing region of said i-th memory section associated with the memory region in which the i-th stage figures covered by the (i+1)th stage figure are stored.

14. An apparatus for processing information of a drawing according to claim 13, further including seventh means for classifying said original figures into predetermined plural groups in accordance with the sizes of said original figures,

each of said first to (k-1)th memory sections having a plurality of subsections allocated to said plural groups, respectively,

wherein said second means determines the upper limit of the usable range of memory region of each subsection as a function of the total number of the original figures classified to the corresponding group, the position data of said i-th stage figures associated with the respective groups of the original figures being stored in the memory regions of said subsections allocated to said groups, respectively.

15. An apparatus for processing information of a drawing according to claim 13, further including seventh means for classifying said original figures into predetermined plural groups in accordance with the features of said original figures,

each of said first to (k-1)th memory sections having a plurality of subsections allocated to said plural groups, respectively;

wherein said second means determines the upper limit of the usable range of memory region of each subsection as a function of the total number of the original figures classified to the corresponding group, the position data of said i-th stage figures associated with the respective groups of the original figures being stored in the memory regions of said subsections allocated to said groups, respectively.

16. An apparatus for processing information of a drawing according to claim 13, further including:

seventh means for dividing said drawing when said i-th stage figures (i-1, 2, . . . , k-1) are to be processed into buckets having a same size and a same shape in a number determined as a function of n, k and i; and

eighth means for determining one of the buckets in which a particular point on each of said i-th stage figures is located, and making the i-th stage figure belong to said one bucket;

wherein the memory regions of said i-th memory section are allocated to said buckets, respectively, while said position data of said i-th stage figures are stored in the memory regions of said i-th memory section allocated to the buckets to which the i-th stage figures belong, respectively.

17. An apparatus for processing information of a drawing according to claim 16, wherein said drawing is divided into n^k-1)/k, n.sup.(k-2)/k, . . . , n^1/k buckets, respectively, when said first, second, . . . , (k-1)th stage figures are to be processed.

18. An apparatus for processing information of a drawing according to claim 16, further including:

ninth means for transforming one of the original figures whose information has already been stored to a new figure differing from said one original figure at least in the position or shape through said input means;

tenth means for determining a first one of the buckets in which said i-th stage figure associated with said selected one original figure is located, and determining a second one of the buckets divided for said i-th stage figures in which a second bucket of said i-th stage figure after said transformation is located;

eleventh means for deciding whether or not said first bucket is same as said second bucket; and

twelfth means for erasing the data of the i-th stage figure relating to said selected one original figure stored in the memory region of said i-th memory section, when said first bucket is decided to be same as said second bucket, and storing subsequently the data of the i-th stage figure relating to said new figure in said memory region, while preparing a new memory region in said i-th memory section, when said first bucket differs from said second bucket, and storing the data of the i-th stage figure relating to said new figure in said new memory region with the data of the i-th stage figure relating to said selected one original figure being erased from said memory region.