Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2817:

  • Fixed a bug at creating the extreme points with the point projection based method.
File size: 11.0 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.ExtremePointPruning;
24using HeuristicLab.Problems.BinPacking3D.Geometry;
25using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
26using System;
27using System.Collections.Generic;
28using System.Linq;
29using System.Text;
30using System.Threading.Tasks;
31
32namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
33
34  /// <summary>
35  /// This extreme point creation class uses the point projection based method by Crainic, T. G., Perboli, G., & Tadei, R. for creating extreme points.
36  /// Each extreme point of an item is being projectet backwards, downwards and to the left.
37  /// A new extreme point will be created where this projections instersects with another item or the bin boundins.
38  /// </summary>
39  public class PointProjectionBasedEPCreator : ExtremePointCreator {
40    /// <summary>
41    /// This lock object is needed because of creating the extreme points in an parallel for loop.
42    /// </summary>
43    protected object _lockAddExtremePoint = new object();
44
45    protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
46      binPacking.ExtremePoints.Clear();
47
48      if (binPacking.Items.Count <= 0) {
49        return;
50      }
51     
52      // generate all new extreme points parallel. This speeds up the creator.     
53      Parallel.ForEach(binPacking.Items, i => {
54        PackingItem it = i.Value;
55        PackingPosition pos = binPacking.Positions[i.Key];
56        GenerateNewExtremePointsForItem(binPacking, it, pos);
57      });
58     
59      // remove not needed extreme points.
60      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
61        // check if a residual space can be removed
62        foreach (var rs in extremePoint.Value.ToList()) {
63          if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {
64            ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);
65          }
66        }
67        // if the current extreme point has no more residual spaces, it can be removed.
68        if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {
69          binPacking.ExtremePoints.Remove(extremePoint);
70        }
71      }
72
73    }
74
75    /// <summary>
76    /// Returns true if a given residual space can be removed.
77    /// The given residual space can be removed if it is within another residual space and
78    /// - neither the position of the other residual space and the current extreme point have an item below or
79    /// - the current extreme point has an item below.
80    /// </summary>
81    /// <param name="binPacking"></param>
82    /// <param name="position"></param>
83    /// <param name="rs"></param>
84    /// <returns></returns>
85    private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {
86      foreach (var extremePoint in binPacking.ExtremePoints) {
87        if (position.Equals(extremePoint.Key)) {
88          continue;
89        }
90        if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {
91          var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);
92          var itemBelowPos = LiesOnAnyItem(binPacking, position);
93
94          if (itemBelowEp || !itemBelowEp && !itemBelowPos) {
95            return true;
96          }
97        }
98      }
99      return false;
100    }
101
102    /// <summary>
103    /// Returns true if the given position lies on an item or an the ground.
104    /// </summary>
105    /// <param name="binPacking"></param>
106    /// <param name="position"></param>
107    /// <returns></returns>
108    private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {
109      if (position.Y == 0) {
110        return true;
111      }
112
113      var items = binPacking.Items.Where(x => {
114        var itemPosition = binPacking.Positions[x.Key];
115        var item = x.Value;
116        int width = item.Width;
117        int depth = item.Depth;
118
119        return itemPosition.Y + item.Height == position.Y &&
120               itemPosition.X <= position.X && position.X < itemPosition.X + width &&
121               itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;
122      });
123
124      return items.Count() > 0;
125    }
126
127
128    /// <summary>
129    /// Adds a new extreme point an the related residual spaces to a given bin packing.
130    /// - The given position has to be valid.
131    /// - The extreme point does not exist in the bin packing.
132    /// - There must be at minimum one valid residual space. A residual space is invalid if the space is zero.
133    /// </summary>
134    /// <param name="binPacking"></param>
135    /// <param name="position"></param>
136    /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>
137    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
138      if (position == null) {
139        return false;
140      }
141
142      if (PointIsInAnyItem(binPacking, new Vector3D(position))) {
143        return false;
144      }
145
146      // this is necessary if the extreme points are being created in a parallel loop.
147      lock (_lockAddExtremePoint) {
148        if (binPacking.ExtremePoints.ContainsKey(position)) {
149          return false;
150        }
151
152        var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
153
154        if (rs.Count() <= 0) {
155          return false;
156        }
157
158        binPacking.ExtremePoints.Add(position, rs);
159        return true;
160      }
161    }
162
163    /// <summary>
164    /// Getnerates the extreme points for a given item.
165    /// It creates extreme points by using a point projection based method and
166    /// creates points by using an edge projection based method.
167    /// </summary>
168    /// <param name="binPacking"></param>
169    /// <param name="newItem"></param>
170    /// <param name="position"></param>
171    protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
172      PointProjectionForNewItem(binPacking, newItem, position);
173    }
174
175    #region Extreme point creation by using a point projection based method
176
177    /// <summary>
178    /// This method creates extreme points by using a point projection based method.
179    /// For each item there will be created three points and each of the points will be projected twice.
180    /// The direction of the projection depends on position of the point.
181    /// </summary>
182    /// <param name="binPacking"></param>
183    /// <param name="newItem"></param>
184    /// <param name="position"></param>
185    protected void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
186      int newWidth = newItem.Width;
187      int newDepth = newItem.Depth;
188      var binShape = binPacking.BinShape;
189      var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);
190      PointProjection(binPacking, sourcePoint, ProjectDown);
191      PointProjection(binPacking, sourcePoint, ProjectBackward);
192
193      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);
194      PointProjection(binPacking, sourcePoint, ProjectLeft);
195      PointProjection(binPacking, sourcePoint, ProjectBackward);
196
197      sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);
198      PointProjection(binPacking, sourcePoint, ProjectDown);
199      PointProjection(binPacking, sourcePoint, ProjectLeft);
200    }
201
202
203    /// <summary>
204    /// Projects a given point by using the given projection method to the neares item.
205    /// The given projection method returns a point which lies on a side of the nearest item in the direction.
206    /// </summary>
207    /// <param name="binPacking"></param>
208    /// <param name="position"></param>
209    /// <param name="projectionMethod"></param>
210    private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {
211      Vector3D sourcePoint = new Vector3D(position);
212      if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {
213        Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);
214        if (point != null) {
215          AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
216        }
217      }
218    }
219    #endregion
220
221    /// <summary>
222    /// Updates the residual spaces.
223    /// It removes not needed ones.
224    /// A residual space will be removed if the space is a subspace of another one and
225    /// the current one has no item below or both have an item below.
226    /// </summary>
227    /// <param name="binPacking"></param>
228    /// <param name="item"></param>
229    /// <param name="position"></param>
230    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
231    }
232
233    /// <summary>
234    /// Returns true if any item in the bin packing encapsulates the given point
235    /// </summary>
236    /// <param name="binPacking"></param>
237    /// <param name="point"></param>
238    /// <returns></returns>
239    private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {
240      foreach (var item in binPacking.Items) {
241        PackingPosition position = binPacking.Positions[item.Key];
242        var depth = item.Value.Depth;
243        var width = item.Value.Width;
244        if (position.X <= point.X && point.X < position.X + width &&
245            position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&
246            position.Z <= point.Z && point.Z < position.Z + depth) {
247          return true;
248        }
249      }
250      return false;
251    }
252
253
254    /// <summary>
255    /// Calculates the residual spaces for an extreme point.
256    /// </summary>
257    /// <param name="binPacking"></param>
258    /// <param name="pos"></param>
259    /// <returns></returns>
260    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
261      return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);
262    }
263  }
264}
Note: See TracBrowser for help on using the repository browser.