- 上一篇：工业机器人的结构设计英文文献和中文翻译
- 下一篇：Java演进英文文献和中文翻译
The Minkowski Sum
The shape of blanks to be nested is approximated as a polygon with n vertices, numbered consecutively in the CCW direction. As the number of vertices increases, curved edges on the blank can be approximated to any desired accuracy. Given two polygons, A and B, the Minkowski sum is defined as the summation of each point in A with each point in B,
(1)
Intuitively, one can think of this process as ‘growing’ shape A by shape B, or by sliding shape –B (i.e., B rotated 180º) around A and following the trace of some reference point on B. For example, Fig.1 shows an example blank A. If a reference vertex is chosen at (0, 0), and a copy of the blank rotated 180º (i.e., –A) is slid around A, the reference vertex on –A will trace out the path shown as the heavy line in Fig.2. This path is the Minkowski sum . Methods for calculating the Minkowski sum can be found in computational geometry texts such as [17, 18].
Sample Part A to be Nested.
Minkowski Sum (heavy line) of sample Part (light line).
The significance of this is that if the reference vertex on –A is on the perimeter of , A and –A will touch but not overlap. The two blanks are as close as they can be. Thus, for a layout of a pair of blanks with one rotated 180º relative to the other, defines all feasible relative positions between the pair of blanks.
A corollary of this property is that if the Minkowski sum of a single part is calculated. With its negative, i.e., . (A complete explanation of these properties of the Minkowski sum is given in [15].) These observations were the basis for the algorithm for optimally nesting a single part on a strip.
The situation when nesting pairs of parts is more complex, since not only do the optimal orientations of the blanks and the strip width need to be determined, but the optimal relative position of the two blanks needs to be determined as well. To solve this problem, an iterative algorithm is suggested:
Given: Blanks A and B (where B=–A when a blank is paired with itself at 180º)
1. Select the relative position of B with respect to A. The Minkowski sum defines the set of feasible relative positions (Fig.2).
2. ‘Join’ A and B at this relative position. Call the combined blank C.
3. Nest the combined blank C on a strip using the Minkowski sum with the algorithm given in [14] or [15].
4. Repeat steps 1-3 to span a full range of potential relative positions of A and B. At each potential position, evaluate if a local optima may be present. If so, numerically optimize the relative positions to maximize material uti lization.
Layout Optimization of One Part Paired with Itself
The first step in the above procedure is to select a feasible position of blank B relative to A. This position is defined by translation vector t from the origin to a point on , as shown in Fig.3. During the optimization process, this translation vector traverses the perimeter of .
Relative Part Translation Nodes on , showing Translation Vector t.
Initially, a discrete number of nodes are placed on each edge of . The two parts are temporarily ‘joined’ at a relative position described by each of the translation nodes, then the combined blank is evaluated for optimal orientation and strip width using a single-part layout procedure (e.g., as in [14] or [15]). In this example, consists of 12 edges, each containing 10 nodes, for a total of 120 translation nodes. The position of each node is found via linear interpolation along each edge , where is vertex I on the Minkowski sum with a coordinate of ( , ). Defining a position parameter s such that s = 0 at and s = 1 at , coordinates of each translation node can be found as:
(2)
(3)
If m nodes are placed on each edge, ,the position parameter values for the node, , are found as: