1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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 


22  using HeuristicLab.Core;


23  using HeuristicLab.Problems.BinPacking3D.Geometry;


24  using System;


25  using System.Collections.Generic;


26  using System.Linq;


27  using System.Text;


28  using System.Threading.Tasks;


29  using HeuristicLab.Common;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31 


32  namespace 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 xaxis


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 yaxis


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 zaxis


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  }

