Method and electronic apparatus for optimal arrangement of shapes having at least two dimensions

• US 4,611,268 A
• Filed: 01/06/1984
• Issued: 09/09/1986
• Est. Priority Date: 01/06/1984
• Status: Expired due to Fees

• Current Assignee: Ferenc Szatmari, Sandor Gotz, Sandor Krenedits
• Original Assignee: Ferenc Szatmari, Sandor Gotz, Sandor Krenedits
• Inventors: Szatmari, Ferenc, Krenedits, Sandor, Gotz, Sandor
• Primary Examiner(s): Ruggiero, Joseph
• Application Number:
  US06/568,570
• Time in Patent Office: 977 Days
• Field of Search: 364/474, 364/475, 364/148, 364/191-193, 340/723, 340/724, 340/725, 340/739, 340/731, 340/747, 358/183
• US Class Current: 700/28
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06Q 10/043 Optimisation of two dimensional placement, e.g. cutting of clothes or wood

Abstract

The present invention relates to a method and an electronic apparatus for optimal arrangement of shapes having at least two dimensions, whereby optimization can be performed quickly while satisfying several requirements at the same time.

According to the proposed method shapes to be arranged are stored in the form of vectors, the unfilled areas among the shapes already arranged are defined and the shapes to be arranged are tried to be inserted in these unfilled areas while examining the accidental coincidences in row-line-resolution.

The proposed apparatus includes a vector memory (1), a vector/raster converter (2), a window generator (3), a displacement generator (4), an occupation analyzer (5), a control unit (6), a display unit (7), an external source (8) and intervening organs (9), wherein the vector memory (1) is connected to the control unit (6), the displacement generator (4) and the vector/raster converter (2), the external source (8) is connected to the displacement generator (4) and the control unit (6), the control unit (6) is connected to the displacement generator (4), the window generator (3), the occupation analyzer (5) and the intervening organs (9), the occupation analyzer (5) is connected to the vector/raster converter (2), the vector/raster converter (2) is connected to the display unit (7), the window generator (3) is connected to the displacement generator (4) and the vector memory (1) or the vector/raster converter (2).

Claims

1. A method of optimal arrangement of multidimensional shapes within a predetermined space, comprising the following steps:

(i) storing data, in vectorial form, of shapes already arranged;

(ii) providing data, in vectorial form, of shapes to be arranged;

(iii) generating one of a predetermined number of positions of one of said shapes to be arranged within said predetermined space with respect to said shapes already arranged;

(iv) repeating said step (iii) in accordance with a comparison of row-column resolutions of said shapes already arranged with said one of said shapes to be arranged, a scalar value being assigned to each outcome of said step (iii) in accordance with a predetermined algorithm;

(v) storing, in vectorial form, a position of said one of said shapes to be arranged, in accordance with scalar values generated in said steps (iii)-(iv), whereby said one of shapes to be arranged becomes one of said shapes already arranged; and

(vi) repeating said steps (i)-(v) until an insufficient amount of said space remains to arrange any more shapes.

2. A method as claimed in claim 1, wherein determination of whether said insufficient amount remains comprises the following steps:

receiving data representative of said shapes already arranged;

evaluating, in matrix form, vectorial data representative of said space;

determining, in matrix form, said positioning of said data representative of said shapes already arranged within said space, whereby unfilled space may be identified in matrix form;

examining consecutive rows and columns within said unfilled space;

comparing vectorial lengths of said rows and columns with vectorial lengths of shapes to be arranged; and

outputting signals representative of said insufficient remaining, if said vectorial lengths of said rows and columns are shorter than said vectorial lengths of shapes to be arranged.

3. A method as claimed in claim 1, wherein said steps (iii)-(v) are performed with respect only to said shapes already arranged which are an in immediate vicinity of a portion of said space where said one of said shapes to be arranged is intended to be placed.

4. A method as claimed in claim 1, wherein said steps (i)-(vi) are performed automatically, without external manual assistance.

5. An apparatus for optimal arrangement of multidimensional shapes within a predetermined space, said apparatus comprising:

vector memory means for storing, in vectorial form, data representing shapes already arranged within said predetermined space;

window generator means for generating vectorial representations of boundaries between shapes already arranged and unfilled portions of said predetermined space; and

displacement generator means for determining placement of shapes to be arranged in accordance with scalar values generated pursuant to comparisons of vectorial representations of said unfilled portions with vectorial representations of different orientations and positions of said shapes to be arranged, said displacement generator means performing said comparisons and selecting an appropriate one of said positions and orientations, whereby said optimal arrangement is achieved.

6. An electronic apparatus as claimed in claim 5, further comprising:

vector/raster converter means for converting vectorial representations in said vector memory means to a form suitable for a CRT display;

occupation analyzer means for identifying said unfilled portions wherein said shapes to be arranged may be inserted;

control means for examining said vectorial representations of said different orientations and positions of said shapes to be arranged;

display means for receiving an output of said vector/raster converter means; and

external source means for externally providing, in vectorial form, data representative of said shapes to be arranged to said displacement generator means and said control means;

wherein said vector memory means is connected to said control means, said displacement generator means and said vector/raster converter means, said external source means is connected to said displacement generator means and said control means, said control means is connected to said displacement generator means, said window generator means, and said occupation analyzer means, said occupation analyzer means is connected to said vector/raster converter means, said vector/raster converter means is connected to said display means, said window generator means is connected to said displacement generator means.

7. An apparatus as claimed in claim 6, wherein said window generator means is further connected to said vector memory means.

8. An apparatus as claimed in claim 6, wherein said window generator means is further connected to said vector/raster converter means.

9. An apparatus as claimed in claim 6, further comprising interface means, connected to said control means, for enabling manual arrangement of said shapes to be arranged.

10. An apparatus as claimed in claim 5, wherein said vector memory means (1) comprises a memory (10), a double normal form transformer (11), a provisional memory (12), a comparator unit (13) and a stack memory (14), wherein said double normal form transformer (11) is connected to said comparator unit (13) and said memory (10), said comparator unit (13) is connected to said memory (10) and said stack memory (14), and said stack memory (14) is connected to said memory (10).

11. An apparatus according to claim 5, wherein said displacement generator means (4) comprises an inner controller (18), a shape memory (16), a multiplexer (23), a position transformer (19), an overlap analyzing means (17), a scalar value generator (20), an environment memory (15), a scalar value stack memory (22) and a stack memory controller (21), wherein said inner controller (18) is connected to said shape memory (16), said stack memory controller (21) and said multiplexer (23), said multiplexer (23) is connected to said stack memory controller (21) and said position transformer (19), said position transformer (10) is connected to said shape memory (16), said overlap analyzing means (17) and said scalar value stack memory (22), said overlap analyzing means (17) is connected to said scalar value generator (20) and said environment memory (15), said scalar value generator (20) is connected to said scalar value stack memory (22), and said scalar value stack memory (22) is connected to said stack memory controller (21).

12. An apparatus as claimed in claim 5, wherein said occupation analyzer means (5) comprises a separator unit (24), a discriminator unit (25), an unfilled area totalizer (31), a co-ordinate counter (26), a co-ordinate register (27), an unfilled dot counter (28), a gravity center generator (38), an area generator (39), a write-in logic (30), a parameter memory (29), a minimum limiter equivalence unit (33), a minimum limiter register (32), a magnitude logic (34), a length register (40), a length equivalence unit (41), an address register (37), an interval register (35), an interval equivalence unit (36), a magnitude register (42), a magnitude equivalence unit (43), and a magnitude stack memory (44), wherein said separator unit (24) is connected to said unfilled area totalizer (31), said co-ordinate register (26) and said discriminator unit (25), said discriminator unit (25) is connected to said unfilled area totalizer (31), said co-ordinate register (27), said unfilled dot counter (28), said magnitude logic (34), said length equivalent unit (41), said write-in logic (30), and said interval equivalence unit (36), said co-ordinate register (27) is connected to said write-in logic (30) and said interval equivalence unit (36), said unfilled dot counter (28) is connected to said gravity center generator (38), said area generator (39), said write-in logic (30), said length equivalence unit (41) and said minimum limiter equivalence unit (33), said minimum limiter equivalence unit (33) is connected to said magnitude logic (34) and said minimum limiter register (32), said magnitude logic (34) is connected to said write-in logic (30), said length equivalence unit (41) is connected to said write-in logic (30) and said length register (40), said length register (40) is connected to said parameter memory (29), said magnitude equivalence unit (43) is connected to said magnitude register (42), said magnitude stack memory (44), said parameter memory (29), and said interval register (35), said interval register (35) is connected to said parameter memory (29), said interval equivalence unit (36), said address register (37) and said write-in logic (30), said address register (37) is connected to said parameter memory (29), said parameter memory (29) is connected to said magnitude stack memory (44), said write-in logic (30) is connected to said parameter memory (29), and said co-ordinate counter (26) is connected to said co-ordinate register (27).