Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 15866 was 15838, checked in by rhanghof, 7 years ago

#2817:

  • Fixed a bug at creating the extreme points with the point projection based method.
File size: 17.2 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      return residualSpaces.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, x));
235    }
236
237
238    /// <summary>
239    /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep).
240    /// </summary>
241    /// <param name="pos">Given poisition</param>
242    /// <param name="rsPos"></param>
243    /// <param name="ep">Given extreme point</param>
244    /// <param name="rsEp"></param>
245    /// <returns></returns>
246    protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) {
247      return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x));
248    }
249
250    /// <summary>
251    /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep).
252    /// </summary>
253    /// <param name="pos">Given poisition</param>
254    /// <param name="rsPos"></param>
255    /// <param name="ep">Given extreme point</param>
256    /// <param name="rsEp"></param>
257    /// <returns></returns>
258    protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
259      var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width;
260      var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height;
261      var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth;
262
263      return x && y && z;
264    }
265
266    /// <summary>
267    /// Calculates the residual spaces for a given bin packing and position.
268    /// It returns a collection of residual spaces
269    /// </summary>
270    /// <param name="binPacking"></param>
271    /// <param name="pos"></param>
272    /// <returns></returns>
273    protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos);
274   
275    #endregion
276
277    #region Projections
278
279    protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
280      var line = new Line3D(pos, new Vector3D(0, 0, -1));
281      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
282                             .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
283                             .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
284                             .Select(x => x.Intersect(line))
285                             .Where(x => x != null && x.Z <= pos.Z);
286      if (m.Any(x => x != null)) {
287        return m.MaxItems(x => x.Z).FirstOrDefault();
288      }
289      return null;
290    }
291
292    protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
293      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
294      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
295                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
296                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
297                  .Select(x => x.Intersect(line))
298                  .Where(x => x != null && x.X <= pos.X);
299      if (m.Any(x => x != null)) {
300        return m.MaxItems(x => x.X).FirstOrDefault();
301      }
302      return null;
303    }
304
305    protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) {
306      var line = new Line3D(pos, new Vector3D(0, -1, 0));
307      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
308                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
309                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
310                  .Select(x => x.Intersect(line))
311                  .Where(x => x != null && x.Y <= pos.Y);
312      if (m.Any(x => x != null)) {
313        return m.MaxItems(x => x.Y).FirstOrDefault();
314      }
315      return null;
316    }
317
318    protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) {
319      var line = new Line3D(pos, new Vector3D(0, 0, 1));
320      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
321                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
322                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
323                  .Select(x => x.Intersect(line))
324                  .Where(x => x != null && x.Z >= pos.Z);
325      if (m.Any(x => x != null)) {
326        return m.MinItems(x => x.Z).FirstOrDefault();
327      }
328      return null;
329    }
330
331    protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) {
332      var line = new Line3D(pos, new Vector3D(1, 0, 0));
333      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
334                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
335                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
336                  .Select(x => x.Intersect(line))
337                  .Where(x => x != null && x.X >= pos.X);
338      if (m.Any(x => x != null)) {
339        return m.MinItems(x => x.X).FirstOrDefault();
340      }
341      return null;
342    }
343
344    protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) {
345      var line = new Line3D(pos, new Vector3D(0, 1, 0));
346      var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
347                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
348                  .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
349                  .Select(x => x.Intersect(line))
350                  .Where(x => x != null && x.Y >= pos.Y);
351      if (m.Any(x => x != null)) {
352        return m.MinItems(x => x.Y).FirstOrDefault();
353      }
354      return null;
355    }
356    #endregion
357  }
358}
Note: See TracBrowser for help on using the repository browser.