Method of placing and extracting modules

• US 5,818,722 A
• Filed: 11/03/1995
• Issued: 10/06/1998
• Est. Priority Date: 11/03/1995
• Status: Expired due to Fees

• Current Assignee: Yoji Kajitani
• Original Assignee: Yoji Kajitani
• Inventors: Nakatake, Shigetoshi, Fujiyoshi, Kunihiro, Murata, Hiroshi, Kajitani, Yoji
• Primary Examiner(s): Elmore, Reba I.
• Assistant Examiner(s): Garland, Steven R.
• Application Number:
  US08/552,742
• Time in Patent Office: 1,068 Days
• Field of Search: 364/167.01, 364/468.03, 364/468.09, 364/468.4, 364/468.28, 364/478.02, 364/488-491, 364/578, 364/478.01, 395/921
• US Class Current: 700/213
• CPC Class Codes: G06Q 10/043 Optimisation of two dimensional placement, e.g. cutting of clothes or wood

Abstract

Method of placing and extracting raw materials or modules in such a way that a minimum area capable of accommodating the modules can be systematically searched for. The placement of the modules is started with drawing rightwardly upward oblique lines and rightwardly downward oblique lines. The number of the oblique lines of each kind is equal to the number of the modules. The modules are placed at the intersections of the oblique lines such that only one module is placed on each one of the oblique lines. Those modules which are located to the right of an arbitrary module are defined to be located on the right side. In this way, vertical or horizontal positional relations among all the modules are determined. Then, the left sides of those modules which have no other modules on their left sides are placed on a vertical baseline. The lower sides of those modules which have no other modules on their lower sides are placed on a horizontal baseline. The modules other than the modules existing on the vertical baseline are brought close to the left side without overlapping other modules. As a result, the modules are packed in on the left side. Similarly, the modules other than the modules existing on the horizontal baseline are brought close to the lower side without overlapping other modules. As a result, the modules are packed in on the lower side.

Claims

1. A method of placing a plurality of substantially rectangular modules of arbitrary sizes, said method comprising the steps of:

drawing rightwardly upward oblique lines which do not intersect with each other on a base, said rightwardly upward oblique lines being equal in number with said modules (first step);

drawing rightwardly downward oblique lines on the base which do not intersect with each other but intersect with said rightwardly upward oblique lines, said rightwardly downward oblique lines being equal in number with said modules (second step);

placing said modules at said intersections such that only one module is located on each one of said oblique lines (third step);

taking an arbitrary one of said modules to be located on a first one of said rightwardly downward oblique lines and on a first one of said rightwardly upward oblique lines;

taking second ones of said modules to be located on a right side of said first rightwardly downward oblique line and located on a right side of said first rightwardly upward oblique line;

defining said second modules to be located on a right side of said arbitrary module (fourth step);

taking third ones of said modules to be located on a left side of said first rightwardly downward oblique line and located on a left side of said first rightwardly upward oblique line;

defining said third modules to be located on a left side of said arbitrary module (fifth step);

taking fourth ones of said modules to be located over said first rightwardly downward oblique line and located over said first rightwardly upward oblique line;

defining said fourth modules to be located over said arbitrary module (sixth step);

taking fifth ones of said modules to be located under said first rightwardly downward oblique line and located under said first rightwardly upward oblique line;

defining said fifth modules to be located under said arbitrary module (seventh step);

repeating the fourth through seventh steps for others of said modules to determine vertical or horizontal positional relations among all the modules (eighth step);

establishing a vertical baseline either on the left or on the right of all of said modules;

taking some of said modules not having other modules on a side of said vertical baseline as sixth modules;

placing sides of said sixth modules on said vertical baseline (ninth step);

establishing a horizontal baseline either above or below all of said modules;

taking some of said modules not having other modules on a side of said horizontal baseline as seventh modules;

placing sides of said seventh modules on said horizontal baseline (tenth step);

bringing the modules other than the modules located on the vertical baseline close to the vertical baseline without overlapping other modules under definitions given by the fourth and fifth steps, whereby the modules are packed in on a side of said vertical baseline (eleventh step); and

bringing the modules other than the modules located on the horizontal baseline close to the horizontal baseline without overlapping other modules under definitions given by the sixth and seventh steps, whereby the modules are packed in on a side of said horizontal baseline (twelfth step).

2. The method of claim 1, wherein said modules placed in said third step are rearranged, and wherein said fourth through twelfth steps are repeated.

3. A method of extracting a plurality of substantially rectangular modules of arbitrary sizes, said method comprising the steps of:

drawing rightwardly upward oblique lines which do not intersect with each other on a base, said rightwardly upward oblique lines being equal in number with said extracted modules (first step);

drawing rightwardly downward oblique lines on said base which do not intersect with each other but intersect with said rightwardly upward oblique lines, said rightwardly downward oblique lines being equal in number with said extracted modules (second step);

placing module extraction patterns at said intersections such that only one module extraction pattern is located on each one of said oblique lines (third step);

taking an arbitrary one of said patterns to be located on a first one of said rightwardly downward oblique lines and on a first one of said rightwardly upward oblique lines;

taking second ones of said patterns to be located on a right side of said first rightwardly downward oblique line and located on a right side of said first rightwardly upward oblique line;

defining said second patterns to be located on a right side of said arbitrary pattern (fourth step);

taking third ones of said patterns to be located on a left side of said first rightwardly downward oblique line and located on a left side of said first rightwardly upward oblique line;

defining said third patterns to be located on a left side of said arbitrary pattern (fifth step);

taking fourth ones of said patterns to be located over said first rightwardly downward oblique line and over said first rightwardly upward oblique line;

defining said fourth patterns to be located over said arbitrary pattern (sixth step);

taking fifth ones of said patterns to be located under said first rightwardly downward oblique line and under said first rightwardly upward oblique line;

defining said fifth patterns to be located under said arbitrary pattern (seventh step);

repeating the fourth through seventh step for others of said patterns to determine vertical or horizontal positional relations among all the modules (eighth step);

establishing a vertical baseline either on the left or on the right of all of said patterns;

taking some of said spaces not having other spaces on a side of said vertical baseline as sixth patterns;

placing sides of said sixth patterns on said vertical baseline (ninth step);

establishing a horizontal baseline either above or below all of said patterns;

taking some of said patterns not having other spaces on a side of said horizontal baseline as seventh patterns;

placing sides of said seventh patterns on said horizontal baseline (tenth step);

bringing the patterns other than the patterns located on the vertical baseline close to the vertical baseline without overlapping other patterns under definitions given by the fourth and fifth steps, whereby the patterns are packed in on a side of said vertical baseline (eleventh step);

bringing the patterns other than the patterns located on the horizontal baseline close to the horizontal baseline without overlapping other patterns under definitions given by the sixth and seventh steps, whereby the patterns are packed in on a side of said horizontal baseline (twelfth step); and

extracting modules according to module extraction patterns arranged in the eleventh and twelfth steps (thirteenth step).

4. The method of claim 3, wherein said module extraction patterns placed in said third step are rearranged, and wherein said fourth through twelfth steps are repeated.

5. A method of placing a plurality of substantially rectangular modules of arbitrary sizes on a base wherein the modules are placed around voids of predetermined size, shape, and location, said method comprising the steps of:

drawing rightwardly upward oblique lines which do not intersect with each other on said base, said rightwardly upward oblique lines being equal in number with said modules (first step);

drawing rightwardly downward oblique lines on said base, which do not intersect with each other but intersect with said rightwardly upward oblique lines, said rightwardly downward oblique lines being equal in number with said modules (second step);

placing said modules at said intersections such that only one module is located on each one of said oblique lines and no module overlaps any of said voids (third step);

taking an arbitrary one of said modules to be located on a first one of said rightwardly downward oblique lines and on a first one of said rightwardly upward oblique lines;

taking second ones of said modules to be located on a right side of said first rightwardly downward oblique line and located on a right side of said first rightwardly upward oblique line;

defining said second modules to be located on a right side of said arbitrary module (fourth step);

taking third ones of said modules to be located on a left side of said first rightwardly downward oblique line and located on a left side of said first rightwardly upward oblique line;

defining said third modules to be located on a left side of said arbitrary module (fifth step);

taking fourth ones of said modules to be located over said first rightwardly downward oblique line and located over said first rightwardly upward oblique line;

defining said fourth modules to be located over said arbitrary module (sixth step);

taking fifth ones of said modules to be located under said first rightwardly downward oblique line and located under said first rightwardly upward oblique line;

defining said fifth modules to be located under said arbitrary module (seventh step);

repeating the fourth through seventh steps for others of said modules to determine vertical or horizontal positional relations among all the modules (eighth step);

establishing a vertical baseline either on the left or on the right of all of said modules;

taking some of said modules not having other modules on a side of said vertical baseline as sixth modules;

placing sides of said sixth modules on said vertical baseline (ninth step);

establishing a horizontal baseline either above or below all of said modules;

taking some of said modules not having other modules on a side of said horizontal baseline as seventh modules;

placing sides of said seventh modules on said horizontal baseline (tenth step);

bringing the modules other than the modules located on the vertical baseline close to the vertical baseline without overlapping any voids or other modules under definitions given by the fourth and fifth steps, whereby the modules are packed in on a side of said vertical baseline (eleventh step); and

bringing the modules other than the modules located on the horizontal baseline close to the horizontal baseline without overlapping any voids or other modules under definitions given by the sixth and seventh steps, whereby the modules are packed in on a side of said horizontal baseline (twelfth step).

6. The method of claim 5, wherein said modules placed in said third step are rearranged, and wherein said fourth through twelfth steps are repeated.