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.Common;


23  using HeuristicLab.Problems.BinPacking3D.Geometry;


24  using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;


25  using System;


26  using System.Collections.Generic;


27  using System.Linq;


28  using System.Text;


29  using System.Threading.Tasks;


30 


31  namespace 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 XZplane


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 subspace


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 XYplane


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 subspace


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 YZplane


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 subspace


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 XYplane


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 subspace


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 XZplane


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 subspace


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 YZplane


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 subspace


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  }

