1  using HeuristicLab.Common;


2  using HeuristicLab.Problems.BinPacking3D.Geometry;


3  using System;


4  using System.Collections.Generic;


5  using System.Linq;


6  using System.Text;


7  using System.Threading.Tasks;


8 


9  namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {


10 


11  /// <summary>


12  /// This extreme point creation class uses the point projection based method by Crainic, T. G., Perboli, G., & Tadei, R. for creating extreme points.


13  /// Each extreme point of an item is being projectet backwards, downwards and to the left.


14  /// A new extreme point will be created where this projections instersects with another item or the bin boundins.


15  /// </summary>


16  public class PointProjectionBasedEPCreator : ExtremePointCreator {


17  protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


18  GenerateNewExtremePointsForItem(binPacking, item, position);


19 


20  // if an item is fit in below, before, or left of another its extreme points have to be regenerated


21  foreach (var above in GetItemsAbove(binPacking, position)) {


22  GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);


23  }


24  foreach (var front in GetItemsInfront(binPacking, position)) {


25  GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);


26  }


27  foreach (var right in GetItemsOnRight(binPacking, position)) {


28  GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);


29  }


30  }


31 


32  protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


33  foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {


34  var ep = extremePoint.Key;


35  var residualSpaces = extremePoint.Value as IList<ResidualSpace>;


36  for (int i = 0; i < residualSpaces.Count(); i++) {


37  var rs = residualSpaces[i];


38  var depth = position.Rotated ? item.Width : item.Depth;


39  var width = position.Rotated ? item.Depth : item.Width;


40  var changed = false;


41  if (ep.Z >= position.Z && ep.Z < position.Z + depth) {


42  if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {


43  var diff = position.X  ep.X;


44  var newRSX = Math.Min(rs.Width, diff);


45  rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);


46  changed = true;


47  }


48  if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {


49  var diff = position.Y  ep.Y;


50  var newRSY = Math.Min(rs.Height, diff);


51  rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);


52  changed = true;


53  }


54  }


55 


56  if (ep.Z <= position.Z &&


57  ep.Y >= position.Y && ep.Y < position.Y + item.Height &&


58  ep.X >= position.X && ep.X < position.X + width) {


59  var diff = position.Z  ep.Z;


60  var newRSZ = Math.Min(rs.Depth, diff);


61  rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);


62  changed = true;


63  }


64 


65  if (changed) {


66  if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {


67  residualSpaces[i] = rs;


68  } else {


69  binPacking.ExtremePoints.Remove(ep);


70  break;


71  }


72  }


73  }


74  }


75  return;


76  }


77 


78  /// <summary>


79  /// Adds an extreme point to a given bin packing.


80  /// It also adds the residual space for the new extreme point


81  /// and removes the extreme point and the related residual space for the given position which are not needed anymore.


82  /// </summary>


83  /// <param name="binPacking"></param>


84  /// <param name="position"></param>


85  /// <returns></returns>


86  protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {


87  if (binPacking.ExtremePoints.ContainsKey(position)) {


88  return false;


89  }


90 


91  var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));


92  binPacking.ExtremePoints.Add(position, residualSpaces);


93  // Check if the existing extreme points are shadowed by the new point


94  // This is, their residual space fit entirely into the residual space of the new point


95  foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {


96  foreach (var residualSpace in ep.Value) {


97  if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {


98  binPacking.ExtremePoints.Remove(ep);


99  break;


100  }


101  }


102  }


103  return true;


104  }


105 


106  /// <summary>


107  /// Calculates the residual space for a given bin packing and position.


108  /// It returns the residual space as a tuple which contains the dimensions


109  /// </summary>


110  /// <param name="binPacking"></param>


111  /// <param name="pos"></param>


112  /// <returns>A Tuple(width, Height, Depth)</width></returns>


113  protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {


114  var residualSpaces = new List<ResidualSpace>();


115  var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));


116  if (!residualSpace.IsZero()) {


117  residualSpaces.Add(residualSpace);


118  }


119  return residualSpaces;


120  }


121 


122  protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {


123 


124  if (pos == null) {


125  return Tuple.Create(0, 0, 0);


126  }


127  var itemPos = binPacking.Items.Select(x => new {


128  Item = x.Value,


129  Position = binPacking.Positions[x.Key]


130  });


131  Vector3D limit = new Vector3D() {


132  X = binPacking.BinShape.Width,


133  Y = binPacking.BinShape.Height,


134  Z = binPacking.BinShape.Depth


135  };


136 


137  if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {


138  var rightLimit = ProjectRight(binPacking, pos);


139  var upLimit = ProjectUp(binPacking, pos);


140  var forwardLimit = ProjectForward(binPacking, pos);


141  if (rightLimit.X > 0) {


142  limit.X = rightLimit.X;


143  }


144  if (upLimit.Y > 0) {


145  limit.Y = upLimit.Y;


146  }


147  if (forwardLimit.Z > 0) {


148  limit.Z = forwardLimit.Z;


149  }


150  }


151 


152  if (limit.X  pos.X <= 0  limit.Y  pos.Y <= 0  limit.Z  pos.Z <= 0) {


153  return Tuple.Create(0, 0, 0);


154  }


155  return Tuple.Create(limit.X  pos.X, limit.Y  pos.Y, limit.Z  pos.Z);


156  }


157  }


158  }

