source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs @ 15617

Last change on this file since 15617 was 15617, checked in by rhanghof, 21 months ago

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File size: 10.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Problems.BinPacking3D.Geometry;
23using System;
24using System.Collections.Generic;
25using System.Linq;
26using System.Text;
27using System.Threading.Tasks;
28
29namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
30  internal class ResidualSpaceCalculator : IResidualSpaceCalculator {
31
32    internal ResidualSpaceCalculator() {}
33   
34    public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
35      IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
36      var rs1 = CalculateXZY(binPacking, point);
37      var rs2 = CalculateZYX(binPacking, point);
38      var rs3 = CalculateYXZ(binPacking, point);
39
40      if (!rs1.IsZero()) {
41        residualSpaces.Add(rs1);
42      }
43
44      if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
45        residualSpaces.Add(rs2);
46      }
47      if (!rs3.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs3))) {
48        residualSpaces.Add(rs3);
49      }
50      return residualSpaces;
51    }
52
53    /// <summary>
54    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
55    /// 1. x
56    /// 2. z
57    /// 3. y
58    /// </summary>
59    /// <param name="binPacking"></param>
60    /// <param name="point"></param>
61    /// <returns></returns>
62    private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
63      ResidualSpace rs = new ResidualSpace(binPacking, point);
64
65      LimitResidualSpaceOnRight(binPacking, point, rs);
66      LimitResidualSpaceInFront(binPacking, point, rs);
67      LimitResidualSpaceAbove(binPacking, point, rs);
68      return rs;
69    }
70
71    /// <summary>
72    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
73    /// 1. z
74    /// 2. y
75    /// 3. x
76    /// </summary>
77    /// <param name="binPacking"></param>
78    /// <param name="point"></param>
79    /// <returns></returns>
80    private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
81      ResidualSpace rs = new ResidualSpace(binPacking, point);
82
83      LimitResidualSpaceInFront(binPacking, point, rs);
84      LimitResidualSpaceAbove(binPacking, point, rs);
85      LimitResidualSpaceOnRight(binPacking, point, rs);
86      return rs;
87    }
88
89    /// <summary>
90    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
91    /// 1. y
92    /// 2. x
93    /// 3. z
94    /// </summary>
95    /// <param name="binPacking"></param>
96    /// <param name="point"></param>
97    /// <returns></returns>
98    private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
99      ResidualSpace rs = new ResidualSpace(binPacking, point);
100
101      LimitResidualSpaceAbove(binPacking, point, rs);
102      LimitResidualSpaceOnRight(binPacking, point, rs);
103      LimitResidualSpaceInFront(binPacking, point, rs);
104      return rs;
105    }
106   
107    /// <summary>
108    /// Returnst true if a given residual space and item overlaps at the x-axis
109    /// </summary>
110    /// <param name="point"></param>
111    /// <param name="residualSpace"></param>
112    /// <param name="position"></param>
113    /// <param name="item"></param>
114    /// <returns></returns>
115    private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
116      if (point.X > position.X && point.X >= position.X + item.Width) {
117        return false;
118      }
119
120      if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
121        return false;
122      }
123      return true;
124    }
125
126    /// <summary>
127    /// Returnst true if a given residual space and item overlaps at the y-axis
128    /// </summary>
129    /// <param name="point"></param>
130    /// <param name="residualSpace"></param>
131    /// <param name="position"></param>
132    /// <param name="item"></param>
133    private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
134      if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
135        return false;
136      }
137
138      if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
139        return false;
140      }
141      return true;
142    }
143
144    /// <summary>
145    /// Returnst true if a given residual space and item overlaps at the z-axis
146    /// </summary>
147    /// <param name="point"></param>
148    /// <param name="residualSpace"></param>
149    /// <param name="position"></param>
150    /// <param name="item"></param>
151    private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
152      if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
153        return false;
154      }
155
156      if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
157        return false;
158      }
159      return true;
160    }
161
162    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
163      // if point.x >= position.x => the residual space is being located on the left side!
164      if (point.X >= position.X) {
165        return false;
166      }
167      var y = OverlapsY(point, residualSpace, position, item);
168      var z = OverlapsZ(point, residualSpace, position, item);
169      return y && z;
170    }
171
172    private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
173      if (point.Z >= position.Z) {
174        return false;
175      }
176      var x = OverlapsX(point, residualSpace, position, item);
177      var y = OverlapsY(point, residualSpace, position, item);
178
179      return x && y;
180    }
181
182
183    private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
184      if (point.Y >= position.Y) {
185        return false;
186      }
187      var x = OverlapsX(point, residualSpace, position, item);
188      var z = OverlapsZ(point, residualSpace, position, item);
189
190      return x && z;
191    }
192
193    /// <summary>
194    /// Recalculates the width of a given residual space.
195    /// The new width is being limited by any item right of the residual space or the dimension of the bin shape.
196    /// If the new width is zero, the whole residual space is being set to zero.
197    /// </summary>
198    /// <param name="binPacking"></param>
199    /// <param name="point"></param>
200    /// <param name="residualSpace"></param>
201    private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
202      if (residualSpace.IsZero()) {
203        return;
204      }
205     
206      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
207                                  .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
208      if (items.Count() > 0) {
209        foreach (var item in items) {
210          int newWidth = item.Position.X - point.X;
211          if (newWidth <= 0) {
212            residualSpace.SetZero();
213            return;
214          } else if (residualSpace.Width > newWidth) {
215            residualSpace.Width = newWidth;
216          }
217        }
218      }     
219    }
220
221    /// <summary>
222    /// Recalculates the depth of a given residual space.
223    /// The new depth is being limited by any item in front of the residual space or the dimension of the bin shape.
224    /// If the new depth is zero, the whole residual space is being set to zero.
225    /// </summary>
226    /// <param name="binPacking"></param>
227    /// <param name="point"></param>
228    /// <param name="residualSpace"></param>
229    private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
230      if (residualSpace.IsZero()) {
231        return;
232      }
233
234      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
235                                  .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
236      if (items.Count() > 0) {
237        foreach (var item in items) {
238          int newDepth = item.Position.Z - point.Z;
239          if (newDepth <= 0) {
240            residualSpace.SetZero();
241            return;
242          } else if (residualSpace.Depth > newDepth) {
243            residualSpace.Depth = newDepth;
244          }
245        }
246      }
247    }
248
249    /// <summary>
250    /// Recalculates the height of a given residual space.
251    /// The new height is being limited by any item above the residual space or the dimension of the bin shape.
252    /// If the new height is zero, the whole residual space is being set to zero.
253    /// </summary>
254    /// <param name="binPacking"></param>
255    /// <param name="point"></param>
256    /// <param name="residualSpace"></param>
257    private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
258      if (residualSpace.IsZero()) {
259        return;
260      }
261
262      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
263                                  .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
264      if (items.Count() > 0) {
265        foreach (var item in items) {
266          int newHeight = item.Position.Y - point.Y;
267          if (newHeight <= 0) {
268            residualSpace.SetZero();
269            return;
270          } else if (residualSpace.Height > newHeight) {
271            residualSpace.Height = newHeight;
272          }
273        }
274      }
275    }
276  }
277}
Note: See TracBrowser for help on using the repository browser.