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

Last change on this file since 15617 was 15617, checked in by rhanghof, 20 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: 17.5 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.Common;
23using HeuristicLab.Problems.BinPacking3D.Geometry;
24using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
25using System;
26using System.Collections.Generic;
27using System.Linq;
28using System.Text;
29using System.Threading.Tasks;
30
31namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
32  public abstract class ExtremePointCreator : IExtremePointCreator {
33
34
35    public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
36      UpdateExtremePoints(binPacking, item, position);
37      UpdateResidualSpace(binPacking, item, position);
38    }
39
40    protected abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
41
42    /// <summary>
43    /// Updates the residual space for a given bin packing.
44    /// </summary>
45    /// <param name="binPacking"></param>
46    /// <param name="item"></param>
47    /// <param name="position"></param>
48    protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
49
50    /// <summary>
51    /// Adds an extreme point to the bin packing.
52    /// </summary>
53    /// <param name="binPacking"></param>
54    /// <param name="position"></param>
55    /// <returns></returns>
56    protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
57
58    /// <summary>
59    /// Generates new extreme points for a given item and its position.
60    /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
61    /// </summary>
62    /// <param name="binPacking"></param>
63    /// <param name="newItem"></param>
64    /// <param name="position"></param>
65    protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
66      int newWidth = newItem.Width;
67      int newDepth = newItem.Depth;
68      var binShape = binPacking.BinShape;
69
70      var itemPlacement = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }).ToList();
71      // Find ExtremePoints beginning from sourcepointX
72      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
73      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
74        // Projecting onto the XZ-plane
75        var below = ProjectDown(binPacking, sourcePoint);
76        var residualSpaces = CalculateResidualSpace(binPacking, below);
77        if (residualSpaces.Count() > 0
78          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
79          // add only if the projected point's residual space is not a sub-space
80          // of another extreme point's residual space
81          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
82          AddExtremePoint(binPacking, belowPoint);
83        }
84        // Projecting onto the XY-plane
85        var back = ProjectBackward(binPacking, sourcePoint);
86        residualSpaces = CalculateResidualSpace(binPacking, back);
87        if (residualSpaces.Count() > 0
88          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
89          // add only if the projected point's residual space is not a sub-space
90          // of another extreme point's residual space
91          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
92          AddExtremePoint(binPacking, backPoint);
93        }
94      }
95
96      //Find ExtremePoints beginning from sourcepointY
97      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
98      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
99        // Projecting onto the YZ-plane
100        var left = ProjectLeft(binPacking, sourcePoint);
101        var residualSpaces = CalculateResidualSpace(binPacking, left);
102        if (residualSpaces.Count() > 0
103          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
104          // add only if the projected point's residual space is not a sub-space
105          // of another extreme point's residual space
106          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
107          AddExtremePoint(binPacking, leftPoint);
108        }
109        // Projecting onto the XY-plane
110        var back = ProjectBackward(binPacking, sourcePoint);
111        residualSpaces = CalculateResidualSpace(binPacking, back);
112        if (residualSpaces.Count() > 0
113          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
114          // add only if the projected point's residual space is not a sub-space
115          // of another extreme point's residual space
116          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
117          AddExtremePoint(binPacking, backPoint);
118        }
119      }
120
121      //Find ExtremePoints beginning from sourcepointZ
122      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
123      if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
124        // Projecting onto the XZ-plane
125        var below = ProjectDown(binPacking, sourcePoint);
126        var residualSpaces = CalculateResidualSpace(binPacking, below);
127        if (residualSpaces.Count() > 0
128          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
129          // add only if the projected point's residual space is not a sub-space
130          // of another extreme point's residual space
131          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
132          AddExtremePoint(binPacking, belowPoint);
133        }
134        // Projecting onto the YZ-plane
135        var left = ProjectLeft(binPacking, sourcePoint);
136        residualSpaces = CalculateResidualSpace(binPacking, left);
137        if (residualSpaces.Count() > 0
138          && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
139          // add only if the projected point's residual space is not a sub-space
140          // of another extreme point's residual space
141          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
142          AddExtremePoint(binPacking, leftPoint);
143        }
144      }
145    }
146
147    #region Get items
148
149    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(BinPacking3D binPacking, PackingPosition pos) {
150      var line = new Line3D(pos, new Vector3D(0, 1, 0));
151      return binPacking.Items.Select(x => new {
152        Item = x.Value,
153        Position = binPacking.Positions[x.Key],
154        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Bottom))
155      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
156        .Select(x => Tuple.Create(x.Position, x.Item));
157    }
158
159    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(BinPacking3D binPacking, PackingPosition pos) {
160      var line = new Line3D(pos, new Vector3D(0, 0, 1));
161      return binPacking.Items.Select(x => new {
162        Item = x.Value,
163        Position = binPacking.Positions[x.Key],
164        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Back))
165      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
166        .Select(x => Tuple.Create(x.Position, x.Item));
167    }
168
169    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(BinPacking3D binPacking, PackingPosition pos) {
170      var line = new Line3D(pos, new Vector3D(1, 0, 0));
171      return binPacking.Items.Select(x => new {
172        Item = x.Value,
173        Position = binPacking.Positions[x.Key],
174        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Left))
175      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
176        .Select(x => Tuple.Create(x.Position, x.Item));
177    }
178
179    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingPosition pos) {
180      var line = new Line3D(pos, new Vector3D(0, 1, 0));
181      return binPacking.Items.Select(x => new {
182        Item = x.Value,
183        Position = binPacking.Positions[x.Key],
184        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Top))
185      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
186        .Select(x => Tuple.Create(x.Position, x.Item));
187    }
188
189    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingPosition pos) {
190      var line = new Line3D(pos, new Vector3D(0, 0, 1));
191      return binPacking.Items.Select(x => new {
192        Item = x.Value,
193        Position = binPacking.Positions[x.Key],
194        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Front))
195      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
196        .Select(x => Tuple.Create(x.Position, x.Item));
197    }
198
199    protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingPosition pos) {
200      var line = new Line3D(pos, new Vector3D(1, 0, 0));
201      return binPacking.Items.Select(x => new {
202        Item = x.Value,
203        Position = binPacking.Positions[x.Key],
204        Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Right))
205      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
206        .Select(x => Tuple.Create(x.Position, x.Item));
207    }
208
209    #endregion
210
211    #region Residual space
212
213
214    /// <summary>
215    ///
216    /// </summary>
217    /// <param name="binPacking"></param>
218    /// <param name="pos"></param>
219    /// <param name="residualSpace"></param>
220    /// <returns></returns>
221    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
222      var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value));
223      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value));
224    }
225
226    /// <summary>
227    ///
228    /// </summary>
229    /// <param name="binPacking"></param>
230    /// <param name="pos"></param>
231    /// <param name="residualSpaces"></param>
232    /// <returns></returns>
233    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable<ResidualSpace> residualSpaces) {
234      foreach (var residualSpace in residualSpaces) {
235        if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) {
236          return true;
237        }
238      }
239      return false;
240    }
241
242
243    /// <summary>
244    /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep).
245    /// </summary>
246    /// <param name="pos">Given poisition</param>
247    /// <param name="rsPos"></param>
248    /// <param name="ep">Given extreme point</param>
249    /// <param name="rsEp"></param>
250    /// <returns></returns>
251    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) {
252      return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x));
253    }
254
255    /// <summary>
256    /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep).
257    /// </summary>
258    /// <param name="pos">Given poisition</param>
259    /// <param name="rsPos"></param>
260    /// <param name="ep">Given extreme point</param>
261    /// <param name="rsEp"></param>
262    /// <returns></returns>
263    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
264      /*old implementation
265      return rsEp.Width >= pos.X - ep.X + rsPos.Width
266          && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
267          && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/
268
269      var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width;
270      var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height;
271      var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth;
272
273      return x && y && z;
274    }
275
276    /// <summary>
277    /// Calculates the residual spaces for a given bin packing and position.
278    /// It returns a collection of residual spaces
279    /// </summary>
280    /// <param name="binPacking"></param>
281    /// <param name="pos"></param>
282    /// <returns></returns>
283    protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos);
284   
285    #endregion
286
287    #region Projections
288
289    protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
290      var line = new Line3D(pos, new Vector3D(0, 0, -1));
291      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
292                             .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
293                             .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
294                             .Select(x => x.Intersect(line))
295                             .Where(x => x != null && x.Z <= pos.Z);
296      if (m.Where(x => x != null).Any()) {
297        return m.MaxItems(x => x.Y).First();
298      }
299      return null;
300    }
301
302    protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
303      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
304      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
305                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
306                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
307                  .Select(x => x.Intersect(line))
308                  .Where(x => x != null && x.X <= pos.X);
309      if (m.Where(x => x != null).Any()) {
310        return m.MaxItems(x => x.Y).First();
311      }
312      return null;
313    }
314
315    protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) {
316      var line = new Line3D(pos, new Vector3D(0, -1, 0));
317      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
318                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
319                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
320                  .Select(x => x.Intersect(line))
321                  .Where(x => x != null && x.Y <= pos.Y);
322      if (m.Where(x => x != null).Any()) {
323        return m.MaxItems(x => x.Y).First();
324      }
325      return null;
326    }
327
328    protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) {
329      var line = new Line3D(pos, new Vector3D(0, 0, 1));
330      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
331                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
332                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
333                  .Select(x => x.Intersect(line))
334                  .Where(x => x != null && x.Z >= pos.Z);
335      if (m.Where(x => x != null).Any()) {
336        return m.MaxItems(x => x.Y).First();
337      }
338      return null;
339    }
340
341    protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) {
342      var line = new Line3D(pos, new Vector3D(1, 0, 0));
343      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
344                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
345                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
346                  .Select(x => x.Intersect(line))
347                  .Where(x => x != null && x.X >= pos.X);
348      if (m.Where(x => x != null).Any()) {
349        return m.MaxItems(x => x.Y).First();
350      }
351      return null;
352    }
353
354    protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) {
355      var line = new Line3D(pos, new Vector3D(0, 1, 0));
356      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
357                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
358                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
359                  .Select(x => x.Intersect(line))
360                  .Where(x => x != null && x.Y >= pos.Y);
361      if (m.Where(x => x != null).Any()) {
362        return m.MaxItems(x => x.Y).First();
363      }
364      return null;
365    }
366    #endregion
367  }
368}
Note: See TracBrowser for help on using the repository browser.