US3596068A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for optimizing material utilization
Assignee: Cal Comp Inc
•
Filing: 1968-12-30
•
Granted: 1971-07-27
•
Expires: 1988-12-30
Abstract
Abstract Patterns can be automatically arranged on the surface of a material in a manner which will require less material than that which is consumed by a competent human performing the same task. The simulated movement of each pattern piece about an already established marker boundary may be accomplished by data processing techniques. Once the contour of a piece outline and the boundary outline is known and the slopes of the vertex connecting segments determined, the displacing moves of the piece about the boundary may be carried out in a nonoverlapping manner. In such a system it is only necessary to examine the trial marker dimension after each move in order to ascertain whether the new position is a preferred location.
Inventors
- 👤 Harold W Doyle
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 07:03
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/04; G06Q10/043; A; A41; A41H; A41H3/00; A41H3/007
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
95 words
A system for positioning a plurality of patterns to form a marker comprising: a digitizer for converting the vertices of each pattern boundary to an array of cartesian coordinate data; means for determining the contour of each vertex; data processing means for augmenting each data array to simulate a noninterferring translation of the piece in tangential contact with the marker boundary; means for computing and storing the marker length dimension after each move whereby the location of minimum length may be determined; means for recording the final location of each piece to form a marker.
Claim 2
Independent Claim
95 words
A system for positioning a plurality of patterns to form a marker comprising: a digitizer for converting the vertices of each pattern boundary to an array of cartesian coordinate data; means for determining the contour of each vertex; data processing means for augmenting each data array to simulate a noninterferring translation of the piece in tangential contact with the marker boundary; means for computing and storing the marker length dimension after each move whereby the location of minimum length may be determined; means for recording the final location of each piece to form a marker.
Claim 3
Independent Claim
169 words
A system for marking comprising: a digitizer for determining the coordinates of data points representing the perimeter of a piece; means for identifying the vertices of the piece and marker boundary; storage means for retaining the vertex coordinates of the piece and marker boundary; means for generating vector representations of segments which connect each vertex of the piece with the next adjacent vertex of the piece; means for generating vector representations of segments which connect each vertex of the marker boundary with the next adjacent vertex of the marker boundary; means for determining the contour of each vertex; means responsive to the contour information and vector representations for augmenting the vertex coordinate data to simulate a sequence of nonoverlapping translations of each piece about the previous established marker boundary; means for computing the marker length after each move; means for storing the computed length; means for comparing each new computed length with previous lengths whereby the piece location which will produce the smallest increase in length may be determined.
Claim 4
Independent Claim
169 words
A system for marking comprising: a digitizer for determining the coordinates of data points representing the perimeter of a piece; means for identifying the vertices of the piece and marker boundary; storage means for retaining the vertex coordinates of the piece and marker boundary; means for generating vector representations of segments which connect each vertex of the piece with the next adjacent vertex of the piece; means for generating vector representations of segments which connect each vertex of the marker boundary with the next adjacent vertex of the marker boundary; means for determining the contour of each vertex; means responsive to the contour information and vector representations for augmenting the vertex coordinate data to simulate a sequence of nonoverlapping translations of each piece about the previous established marker boundary; means for computing the marker length after each move; means for storing the computed length; means for comparing each new computed length with previous lengths whereby the piece location which will produce the smallest increase in length may be determined.
Claim 5
Independent Claim
119 words
A system for positioning patterns which are represented in digital form about a two-dimensional area comprising: a digital computer for updating the digital data representing each piece to correspond to a nonoverlapping physical translation of the piece about and in contact with a preestablished boundary as defined by previously positioned pieces; sensing means for determining the border of the area; means for determining the new dimensions of the boundary after each simulated translation of the piece; means for selectively storing the location of each new position of the piece which results in a smaller boundary dimension than previous locations of the piece, whereby the piece may be fitted in that location which produces the smallest increase in occupied area.
Claim 6
Independent Claim
119 words
A system for positioning patterns which are represented in digital form about a two-dimensional area comprising: a digital computer for updating the digital data representing each piece to correspond to a nonoverlapping physical translation of the piece about and in contact with a preestablished boundary as defined by previously positioned pieces; sensing means for determining the border of the area; means for determining the new dimensions of the boundary after each simulated translation of the piece; means for selectively storing the location of each new position of the piece which results in a smaller boundary dimension than previous locations of the piece, whereby the piece may be fitted in that location which produces the smallest increase in occupied area.
Claim 7
Dependent Claim
116 words
The combination comprising: means for digitizing pattern boundaries; means for tabulating the data representing each pattern to form an array; means for arranging the arrays representing each piece in a sequence for placement within an area; means for augmenting each data array in sequence to correspond with a physical translation of each piece to different locations within the area which is not occupied by previously positioned pieces; means for gauging the external dimensions of the border formed by the augmented data representing the previously positioned pieces and the data representing the various locations of the piece presently undergoing translation whereby the location of the piece which produces the smallest increase in border dimensions may be determined.
Claim 8
Dependent Claim
116 words
The combination comprising: means for digitizing pattern boundaries; means for tabulating the data representing each pattern to form an array; means for arranging the arrays representing each piece in a sequence for placement within an area; means for augmenting each data array in sequence to correspond with a physical translation of each piece to different locations within the area which is not occupied by previously positioned pieces; means for gauging the external dimensions of the border formed by the augmented data representing the previously positioned pieces and the data representing the various locations of the piece presently undergoing translation whereby the location of the piece which produces the smallest increase in border dimensions may be determined.
Claim 9
Dependent Claim
47 words
The combination described in claim 4 wherein the means for augmenting each data array comprises a computer for arithmetically determining the new location of each data point which corresponds with a physical translation of piece in sliding contact with an already-establiShed boundary determined by previously positioned pieces.
Claim 10
Dependent Claim
119 words
An arrangement for automatically laying out templates to reduce the amount of material utilized in marking comprising: means for presenting a digital representation of each template in sequence; means for manipulating the data representing each piece to correspond with a physical positioning of each piece in turn, within the borders of the material; means for manipulating the data of each piece to correspond with a positioning of each piece in tangential contact with the boundary formed by previously positioned pieces at the location which results in the smallest increase in the dimensions of the marker; means for augmenting the old boundary to include the addition of each piece at the location which produces the smallest increase in marker dimensions.
Claim 11
Dependent Claim
119 words
An arrangement for automatically laying out templates to reduce the amount of material utilized in marking comprising: means for presenting a digital representation of each template in sequence; means for manipulating the data representing each piece to correspond with a physical positioning of each piece in turn, within the borders of the material; means for manipulating the data of each piece to correspond with a positioning of each piece in tangential contact with the boundary formed by previously positioned pieces at the location which results in the smallest increase in the dimensions of the marker; means for augmenting the old boundary to include the addition of each piece at the location which produces the smallest increase in marker dimensions.
Claim 12
Independent Claim
446 words
A method of laying out patterns to reduce material waste comprising the steps of: digitizing the boundaries of each piece; assembling the data representing each piece into an array of entries, each entry of the array to represent the X-Y coordinates of the piece vertices; arranging the data array in a sequence; storing the sequence of data arrays; augmenting each data array to produce a particular view and orientation relative to the coordinate axis of the material; computing the contour tags at each piece vertex; scanning the data array representing each piece to determine the vertex having the largest Y value; augmenting each data array to correspond with positioning each piece to have the vertex with the largest Y value coincident with the lower boundary of the material; augmenting each data array to correspond with translation of each piece to bring the vertex of the piece having the largest value into coincidence with the furthest vertex of the boundary formed by previously positioned pieces which is tangent with the lower border of the material; operating upon the data arrays to generate the vector equations representing the line segments connecting the piece vertices; operating upon the data representing the boundary formed by previously positioned pieces to generate therefrom the vector equations representing the line segments connecting the boundary vertices; computing the contour tags at each vertex of the preestablished boundary; multiplying the piece vector to the left of the contact vertices by the boundary vector to the left of the contact vertices to form the vector product for determining a displacement vector along which a nonoverlapping translation may be made; augmenting the piece data to correspond with a series of displacements which may be either nonoverlapping full translation of the piece in sliding contact with the boundary to a new vertex or a nonoverlapping partial translation of the piece in sliding contact with the boundary to a point of contact with the boundary as determined by the contour information; testing the new position of the piece after each displacement to determine whether the piece is within the borders of the material; comparing the length of the boundary after each displacement to determine whether the new location of the piece will result in a marker whose length is less than that of previous locations of the piece; storing the location information of the piece where the piece is within the boundaries of the material and the new location of the piece results in a shorter marker than previous positions of the piece, whereby the data array representing each piece may be augmented to place the piece at a location which will produce the smallest increase in marker length.
Claim 13
Independent Claim
446 words
A method of laying out patterns to reduce material waste comprising the steps of: digitizing the boundaries of each piece; assembling the data representing each piece into an array of entries, each entry of the array to represent the X-Y coordinates of the piece vertices; arranging the data array in a sequence; storing the sequence of data arrays; augmenting each data array to produce a particular view and orientation relative to the coordinate axis of the material; computing the contour tags at each piece vertex; scanning the data array representing each piece to determine the vertex having the largest Y value; augmenting each data array to correspond with positioning each piece to have the vertex with the largest Y value coincident with the lower boundary of the material; augmenting each data array to correspond with translation of each piece to bring the vertex of the piece having the largest value into coincidence with the furthest vertex of the boundary formed by previously positioned pieces which is tangent with the lower border of the material; operating upon the data arrays to generate the vector equations representing the line segments connecting the piece vertices; operating upon the data representing the boundary formed by previously positioned pieces to generate therefrom the vector equations representing the line segments connecting the boundary vertices; computing the contour tags at each vertex of the preestablished boundary; multiplying the piece vector to the left of the contact vertices by the boundary vector to the left of the contact vertices to form the vector product for determining a displacement vector along which a nonoverlapping translation may be made; augmenting the piece data to correspond with a series of displacements which may be either nonoverlapping full translation of the piece in sliding contact with the boundary to a new vertex or a nonoverlapping partial translation of the piece in sliding contact with the boundary to a point of contact with the boundary as determined by the contour information; testing the new position of the piece after each displacement to determine whether the piece is within the borders of the material; comparing the length of the boundary after each displacement to determine whether the new location of the piece will result in a marker whose length is less than that of previous locations of the piece; storing the location information of the piece where the piece is within the boundaries of the material and the new location of the piece results in a shorter marker than previous positions of the piece, whereby the data array representing each piece may be augmented to place the piece at a location which will produce the smallest increase in marker length.
Claim 14
Dependent Claim
269 words
(The method described in claim 8 wherein the manipulation of the digitized data to simulate a positioning of each piece in sequence within the borders of the material comprises the steps of:) A method for laying out the pieces on a material comprising the steps of: digitizing the piece perimeters; transforming the digitized datA representing each piece to correspond with a physical location of the piece within the borders of the material; manipulating the digitized data to simulate a positioning of each piece in sequence within the borders of the material to a location which will produce the smallest increase in marker length, said manipulating steps comprises: forming the vector representations of the segments connecting each vertex of the piece; forming the vector representations of the segments connecting each vertex of the marker boundary; identifying the contour at each piece and boundary vertex; positioning the piece to be in a nonoverlapping tangential contact with the marker boundary; multiplying contacting vectors together to form the cross product; testing the sign of the cross produce to determine the displacement vector; calculating the magnitude of the displacement to be made according to the contour information; augmenting the data to simulate the piece displacement in accordance with the previously established magnitude and direction; examining the marker length after each move to determine whether the new length is smaller than a previous length; storing the data representing the location of the piece which results in a shorter marker length than previous positions of the piece whereby the location of the piece within the border which results in the shortest marker length may be determined.
Claim 15
Dependent Claim
221 words
(The method described in claim 8 wherein the manipulating of the digitized data to simulate a positioning of each piece in sequence within the borders of the material comprises the steps of:) A method for laying out the pieces on a material comprising the steps of: digitizing the piece perimeters; transforming the digitized data representing each piece to correspond with a physical location of the piece within the borders of the material; manipulating the digitized data to simulate a positioning of each piece in sequence within the borders of the material to a location which will produce the smallest increase in marker length, said manipulating steps comprises: augmenting the data to correspond with bringing each piece into tangential contact with the marker boundary formed by previously positioned pieces; selecting the magnitude and direction of each displacement move which corresponds to a nonoverlapping translation of the piece in sliding contact with the marker boundary; augmenting the data to correspond with a piece displacement in accordance with the previously established magnitude and direction; testing the marker length after each move of the piece to determine the location which produces the smallest increase in marker dimensions; augmenting the old boundary data to include the piece as positioned at the location which produces the smallest increase in marker dimension; selecting the next piece for placement.
Claim 16
Dependent Claim
107 words
The method described in claim 9 wherein the selection of the magnitude and direction of each displacement move comprises the steps of: forming the vector representation of the segments connecting each vertex of the piece; forming the vector representations of the segments connecting each vertex of the marker boundary; identifying the contour at each piece and boundary vertex; positioning the piece to be in a nonoverlapping tangential contact with the marker boundary; multiplying contacting vectors together to form the cross product; testing the sign of the cross products to determine the displacement vector; calculating the magnitude of the displacement to be made according to the contour information.
Claim 17
Independent Claim
189 words
A method of positioning patterns to reduce material waste comprising the steps of: computing the contour tags of the vertices representing each piece; computing the contour tags representing the boundary formed by previously positioned pieces; adjusting the data representing each piece to correspond with positIoning each piece in turn at a starting location; selecting a trial displacement vector for each displacement of each piece; testing the contour tags of contact vertices to determine whether potential overlap exists; testing the boundary- and piece-defining data to determine whether a total displacement of concave contact vertices will produce an actual overlap; calculating the magnitude of the maximum nonoverlapping partial displacements which may be made; adjusting the data representing each piece to correspond with a total displacement to a new vertex or a partial displacement to a new point of nonoverlapping contact; testing the new location of each piece after each displacement to determine whether the piece is within the borders of the material; computing the boundary dimensions after each displacement; adjusting the piece data to correspond with positioning each piece at the location which results in the smallest increase in boundary dimensions.
Claim 18
Independent Claim
189 words
A method of positioning patterns to reduce material waste comprising the steps of: computing the contour tags of the vertices representing each piece; computing the contour tags representing the boundary formed by previously positioned pieces; adjusting the data representing each piece to correspond with positIoning each piece in turn at a starting location; selecting a trial displacement vector for each displacement of each piece; testing the contour tags of contact vertices to determine whether potential overlap exists; testing the boundary- and piece-defining data to determine whether a total displacement of concave contact vertices will produce an actual overlap; calculating the magnitude of the maximum nonoverlapping partial displacements which may be made; adjusting the data representing each piece to correspond with a total displacement to a new vertex or a partial displacement to a new point of nonoverlapping contact; testing the new location of each piece after each displacement to determine whether the piece is within the borders of the material; computing the boundary dimensions after each displacement; adjusting the piece data to correspond with positioning each piece at the location which results in the smallest increase in boundary dimensions.
Claim 19
Dependent Claim
120 words
The method recited in claim 11 wherein the calculating of the magnitude of a partial displacement of a piece comprises the steps of: superposing the trial displacement vector on each vertex of the piece to be displaced; determining whether the superposed trial displacement vectors will interfere with the segments connecting adjacent vertices of the boundary formed by previously positioned pieces; superposing an oppositely directed trial displacement vector on each vertex of the boundary formed by previously positioned pieces; determining whether the oppositely directed displacement vectors will interfere with the segments connecting adjacent vertices of the piece; calculating the point of intersection of each interfering displacement vector with a segment to determine the maximum nonoverlapping partial displacement which may be made.
Claim 20
Dependent Claim
27 words
The method recited in claim 12 wherein is included the steps of testing the piece and boundary to eliminate vertices and segments which are not potentially interferring.
Claim 21
Dependent Claim
139 words
The method recited in claim 13 wherein the steps of testing the piece and boundary to eliminate vertices and segments which are not potentially interfering comprises the steps of: constructing a first circumscribing rectangle about the piece; constructing a second circumscribing rectangle about the boundary formed by previously positioned pieces; superposing the trial displacement vector and an oppositely directed trial displacement vector on each corner of the rectangular area which is common to said first and second rectangles; expanding the rectangular area which is common with said first and second rectangles to include the positive trial displacement vectors at each corner; expanding the rectangular area which is common with said first and second rectangles to include the negative trail displacement vectors at each corner; eliminating all vertices and segments outside the expanded rectangular areas as being not potentially interfering.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-07-26 | 1975-01-25 | 1975-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-07-26 | 1979-01-25 | 1979-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-07-26 | 1983-01-25 | 1983-07-27 | $7700.00 | Window Closed / Lapsed |