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

Last change on this file since 15770 was 15770, checked in by rhanghof, 3 years ago

#2817:

  • Added a graph to the BinPacking3D for calculating the weight distribution.
  • Added some materials.
File size: 10.8 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.Core;
23using HeuristicLab.Problems.BinPacking3D.Geometry;
24using System;
25using System.Collections.Generic;
26using System.Linq;
27using System.Text;
28using System.Threading.Tasks;
29using HeuristicLab.Common;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
33  internal class ResidualSpaceCalculator : Item, IResidualSpaceCalculator {
34
35    internal ResidualSpaceCalculator() {}
36
37    [StorableConstructor]
38    protected ResidualSpaceCalculator(bool deserializing) : base(deserializing) { }
39
40    protected ResidualSpaceCalculator(ResidualSpaceCalculator original, Cloner cloner)
41      : base(original, cloner) {
42    }
43
44    public override IDeepCloneable Clone(Cloner cloner) {
45      return new ResidualSpaceCalculator(this, cloner);
46    }
47
48    public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
49      IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
50      var rs1 = CalculateXZY(binPacking, point);
51      var rs2 = CalculateZYX(binPacking, point);
52      var rs3 = CalculateYXZ(binPacking, point);
53
54      if (!rs1.IsZero()) {
55        residualSpaces.Add(rs1);
56      }
57
58      if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
59        residualSpaces.Add(rs2);
60      }
61      if (!rs3.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs3))) {
62        residualSpaces.Add(rs3);
63      }
64      return residualSpaces;
65    }
66
67    /// <summary>
68    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
69    /// 1. x
70    /// 2. z
71    /// 3. y
72    /// </summary>
73    /// <param name="binPacking"></param>
74    /// <param name="point"></param>
75    /// <returns></returns>
76    private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
77      ResidualSpace rs = new ResidualSpace(binPacking, point);
78
79      LimitResidualSpaceOnRight(binPacking, point, rs);
80      LimitResidualSpaceInFront(binPacking, point, rs);
81      LimitResidualSpaceAbove(binPacking, point, rs);
82      return rs;
83    }
84
85    /// <summary>
86    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
87    /// 1. z
88    /// 2. y
89    /// 3. x
90    /// </summary>
91    /// <param name="binPacking"></param>
92    /// <param name="point"></param>
93    /// <returns></returns>
94    private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
95      ResidualSpace rs = new ResidualSpace(binPacking, point);
96
97      LimitResidualSpaceInFront(binPacking, point, rs);
98      LimitResidualSpaceAbove(binPacking, point, rs);
99      LimitResidualSpaceOnRight(binPacking, point, rs);
100      return rs;
101    }
102
103    /// <summary>
104    /// Calculates a resiual space by expanding to the limits of the axis in the following order:
105    /// 1. y
106    /// 2. x
107    /// 3. z
108    /// </summary>
109    /// <param name="binPacking"></param>
110    /// <param name="point"></param>
111    /// <returns></returns>
112    private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
113      ResidualSpace rs = new ResidualSpace(binPacking, point);
114
115      LimitResidualSpaceAbove(binPacking, point, rs);
116      LimitResidualSpaceOnRight(binPacking, point, rs);
117      LimitResidualSpaceInFront(binPacking, point, rs);
118      return rs;
119    }
120   
121    /// <summary>
122    /// Returnst true if a given residual space and item overlaps at the x-axis
123    /// </summary>
124    /// <param name="point"></param>
125    /// <param name="residualSpace"></param>
126    /// <param name="position"></param>
127    /// <param name="item"></param>
128    /// <returns></returns>
129    private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
130      if (point.X > position.X && point.X >= position.X + item.Width) {
131        return false;
132      }
133
134      if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
135        return false;
136      }
137      return true;
138    }
139
140    /// <summary>
141    /// Returnst true if a given residual space and item overlaps at the y-axis
142    /// </summary>
143    /// <param name="point"></param>
144    /// <param name="residualSpace"></param>
145    /// <param name="position"></param>
146    /// <param name="item"></param>
147    private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
148      if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
149        return false;
150      }
151
152      if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
153        return false;
154      }
155      return true;
156    }
157
158    /// <summary>
159    /// Returnst true if a given residual space and item overlaps at the z-axis
160    /// </summary>
161    /// <param name="point"></param>
162    /// <param name="residualSpace"></param>
163    /// <param name="position"></param>
164    /// <param name="item"></param>
165    private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
166      if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
167        return false;
168      }
169
170      if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
171        return false;
172      }
173      return true;
174    }
175
176    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
177      // if point.x >= position.x => the residual space is being located on the left side!
178      if (point.X >= position.X) {
179        return false;
180      }
181      var y = OverlapsY(point, residualSpace, position, item);
182      var z = OverlapsZ(point, residualSpace, position, item);
183      return y && z;
184    }
185
186    private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
187      if (point.Z >= position.Z) {
188        return false;
189      }
190      var x = OverlapsX(point, residualSpace, position, item);
191      var y = OverlapsY(point, residualSpace, position, item);
192
193      return x && y;
194    }
195
196
197    private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
198      if (point.Y >= position.Y) {
199        return false;
200      }
201      var x = OverlapsX(point, residualSpace, position, item);
202      var z = OverlapsZ(point, residualSpace, position, item);
203
204      return x && z;
205    }
206
207    /// <summary>
208    /// Recalculates the width of a given residual space.
209    /// The new width is being limited by any item right of the residual space or the dimension of the bin shape.
210    /// If the new width is zero, the whole residual space is being set to zero.
211    /// </summary>
212    /// <param name="binPacking"></param>
213    /// <param name="point"></param>
214    /// <param name="residualSpace"></param>
215    private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
216      if (residualSpace.IsZero()) {
217        return;
218      }
219     
220      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
221                                  .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
222      if (items.Count() > 0) {
223        foreach (var item in items) {
224          int newWidth = item.Position.X - point.X;
225          if (newWidth <= 0) {
226            residualSpace.SetZero();
227            return;
228          } else if (residualSpace.Width > newWidth) {
229            residualSpace.Width = newWidth;
230          }
231        }
232      }     
233    }
234
235    /// <summary>
236    /// Recalculates the depth of a given residual space.
237    /// The new depth is being limited by any item in front of the residual space or the dimension of the bin shape.
238    /// If the new depth is zero, the whole residual space is being set to zero.
239    /// </summary>
240    /// <param name="binPacking"></param>
241    /// <param name="point"></param>
242    /// <param name="residualSpace"></param>
243    private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
244      if (residualSpace.IsZero()) {
245        return;
246      }
247
248      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
249                                  .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
250      if (items.Count() > 0) {
251        foreach (var item in items) {
252          int newDepth = item.Position.Z - point.Z;
253          if (newDepth <= 0) {
254            residualSpace.SetZero();
255            return;
256          } else if (residualSpace.Depth > newDepth) {
257            residualSpace.Depth = newDepth;
258          }
259        }
260      }
261    }
262
263    /// <summary>
264    /// Recalculates the height of a given residual space.
265    /// The new height is being limited by any item above the residual space or the dimension of the bin shape.
266    /// If the new height is zero, the whole residual space is being set to zero.
267    /// </summary>
268    /// <param name="binPacking"></param>
269    /// <param name="point"></param>
270    /// <param name="residualSpace"></param>
271    private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
272      if (residualSpace.IsZero()) {
273        return;
274      }
275
276      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
277                                  .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
278      if (items.Count() > 0) {
279        foreach (var item in items) {
280          int newHeight = item.Position.Y - point.Y;
281          if (newHeight <= 0) {
282            residualSpace.SetZero();
283            return;
284          } else if (residualSpace.Height > newHeight) {
285            residualSpace.Height = newHeight;
286          }
287        }
288      }
289    }
290  }
291}
Note: See TracBrowser for help on using the repository browser.