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 


33  /// <summary>


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


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


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


37  /// </summary>


38  public class PointProjectionBasedEPCreator : ExtremePointCreator {


39  /// <summary>


40  /// This lock object is needed because of creating the extreme points in an parallel for loop.


41  /// </summary>


42  object _lockAddExtremePoint = new object();


43 


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


45  binPacking.ExtremePoints.Clear();


46 


47  // generate all new extreme points parallel. This speeds up the creator.


48  Parallel.ForEach(binPacking.Items, i => {


49  PackingItem it = i.Value;


50  PackingPosition p = binPacking.Positions[i.Key];


51  GenerateNewExtremePointsForItem(binPacking, it, p);


52  });


53 


54  // remove not needed extreme points.


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


56  // check if a residual space can be removed


57  foreach (var rs in extremePoint.Value.ToList()) {


58  if (ResidualSpaceCanBeRemoved(binPacking, extremePoint.Key, rs)) {


59  ((IList<ResidualSpace>)extremePoint.Value).Remove(rs);


60  }


61  }


62  // if the current extreme point has no more residual spaces, it can be removed.


63  if (((IList<ResidualSpace>)extremePoint.Value).Count <= 0) {


64  binPacking.ExtremePoints.Remove(extremePoint);


65  }


66  }


67 


68  }


69 


70  /// <summary>


71  /// Returns true if a given residual space can be removed.


72  /// The given residual space can be removed if it is within another residual space and


73  ///  neither the position of the other residual space and the current extreme point have an item below or


74  ///  the current extreme point has an item below.


75  /// </summary>


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


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


78  /// <param name="rs"></param>


79  /// <returns></returns>


80  private bool ResidualSpaceCanBeRemoved(BinPacking3D binPacking, PackingPosition position, ResidualSpace rs) {


81  foreach (var extremePoint in binPacking.ExtremePoints) {


82  if (position.Equals(extremePoint.Key)) {


83  continue;


84  }


85  if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(position), rs, extremePoint.Key, extremePoint.Value)) {


86  var itemBelowEp = LiesOnAnyItem(binPacking, extremePoint.Key);


87  var itemBelowPos = LiesOnAnyItem(binPacking, position);


88 


89  if (itemBelowEp  !itemBelowEp && !itemBelowPos) {


90  return true;


91  }


92  }


93  }


94  return false;


95  }


96 


97  /// <summary>


98  /// Returns true if the given position lies on an item or an the ground.


99  /// </summary>


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


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


102  /// <returns></returns>


103  private bool LiesOnAnyItem(BinPacking3D binPacking, PackingPosition position) {


104  if (position.Y == 0) {


105  return true;


106  }


107 


108  var items = binPacking.Items.Where(x => {


109  var itemPosition = binPacking.Positions[x.Key];


110  var item = x.Value;


111  int width = item.Width;


112  int depth = item.Depth;


113 


114  return itemPosition.Y + item.Height == position.Y &&


115  itemPosition.X <= position.X && position.X < itemPosition.X + width &&


116  itemPosition.Z <= position.Z && position.Z < itemPosition.Z + depth;


117  });


118 


119  return items.Count() > 0;


120  }


121 


122 


123  /// <summary>


124  /// Adds a new extreme point an the related residual spaces to a given bin packing.


125  ///  The given position has to be valid.


126  ///  The extreme point does not exist in the bin packing.


127  ///  There must be at minimum one valid residual space. A residual space is invalid if the space is zero.


128  /// </summary>


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


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


131  /// <returns>True = the given point and its related residual spaces were successfully added to the bin packing</returns>


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


133  if (position == null) {


134  return false;


135  }


136 


137  if (PointIsInAnyItem(binPacking, new Vector3D(position))) {


138  return false;


139  }


140 


141  // this is necessary if the extreme points are being created in a parallel loop.


142  lock (_lockAddExtremePoint) {


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


144  return false;


145  }


146 


147  var rs = CalculateResidualSpace(binPacking, new Vector3D(position));


148 


149  if (rs.Count() <= 0) {


150  return false;


151  }


152 


153  binPacking.ExtremePoints.Add(position, rs);


154  return true;


155  }


156  }


157 


158  /// <summary>


159  /// Getnerates the extreme points for a given item.


160  /// It creates extreme points by using a point projection based method and


161  /// creates points by using an edge projection based method.


162  /// </summary>


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


164  /// <param name="newItem"></param>


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


166  protected override void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {


167  PointProjectionForNewItem(binPacking, newItem, position);


168  }


169 


170  #region Extreme point creation by using a point projection based method


171 


172  /// <summary>


173  /// This method creates extreme points by using a point projection based method.


174  /// For each item there will be created three points and each of the points will be projected twice.


175  /// The direction of the projection depends on position of the point.


176  /// </summary>


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


178  /// <param name="newItem"></param>


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


180  private void PointProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {


181  int newWidth = newItem.Width;


182  int newDepth = newItem.Depth;


183  var binShape = binPacking.BinShape;


184  var sourcePoint = new PackingPosition(position.AssignedBin, position.X + newWidth, position.Y, position.Z);


185  PointProjection(binPacking, sourcePoint, ProjectDown);


186  PointProjection(binPacking, sourcePoint, ProjectBackward);


187 


188  sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y + newItem.Height, position.Z);


189  PointProjection(binPacking, sourcePoint, ProjectLeft);


190  PointProjection(binPacking, sourcePoint, ProjectBackward);


191 


192  sourcePoint = new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + newDepth);


193  PointProjection(binPacking, sourcePoint, ProjectDown);


194  PointProjection(binPacking, sourcePoint, ProjectLeft);


195  }


196 


197 


198  /// <summary>


199  /// Projects a given point by using the given projection method to the neares item.


200  /// The given projection method returns a point which lies on a side of the nearest item in the direction.


201  /// </summary>


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


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


204  /// <param name="projectionMethod"></param>


205  private void PointProjection(BinPacking3D binPacking, PackingPosition position, Func<BinPacking3D, Vector3D, Vector3D> projectionMethod) {


206  Vector3D sourcePoint = new Vector3D(position);


207  if (sourcePoint.X < binPacking.BinShape.Width && sourcePoint.Y < binPacking.BinShape.Height && sourcePoint.Z < binPacking.BinShape.Depth) {


208  Vector3D point = projectionMethod?.Invoke(binPacking, sourcePoint);


209  if (point != null) {


210  AddExtremePoint(binPacking, new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));


211  }


212  }


213  }


214  #endregion


215 


216  #region Extreme point creation by using an edge projection based method


217 


218  /// <summary>


219  /// This method creates extreme points be projecting the edges of a given item


220  ///  left


221  ///  back


222  ///  down.


223  /// A extreme point will be created, if an edge instersects with an edge of another item.


224  /// </summary>


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


226  /// <param name="newItem"></param>


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


228  private void EdgeProjectionForNewItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {


229  int newWidth = newItem.Width;


230  int newDepth = newItem.Depth;


231  var binShape = binPacking.BinShape;


232 


233  foreach (var ep in GetEpsOnLeft(binPacking, newItem, position)) {


234  AddExtremePoint(binPacking, ep.Key);


235  }


236 


237  foreach (var ep in GetEpsBelow(binPacking, newItem, position)) {


238  AddExtremePoint(binPacking, ep.Key);


239  }


240 


241  foreach (var ep in GetEpsBehind(binPacking, newItem, position)) {


242  AddExtremePoint(binPacking, ep.Key);


243  }


244  }


245  #endregion


246 


247  /// <summary>


248  /// Updates the residual spaces.


249  /// It removes not needed ones.


250  /// A residual space will be removed if the space is a subspace of another one and


251  /// the current one has no item below or both have an item below.


252  /// </summary>


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


254  /// <param name="item"></param>


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


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


257  }


258 


259  /// <summary>


260  /// Returns true if any item in the bin packing encapsulates the given point


261  /// </summary>


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


263  /// <param name="point"></param>


264  /// <returns></returns>


265  private bool PointIsInAnyItem(BinPacking3D binPacking, Vector3D point) {


266  foreach (var item in binPacking.Items) {


267  PackingPosition position = binPacking.Positions[item.Key];


268  var depth = item.Value.Depth;


269  var width = item.Value.Width;


270  if (position.X <= point.X && point.X < position.X + width &&


271  position.Y <= point.Y && point.Y < position.Y + item.Value.Height &&


272  position.Z <= point.Z && point.Z < position.Z + depth) {


273  return true;


274  }


275  }


276  return false;


277  }


278 


279  /// <summary>


280  /// Returns true if an item is in the residual space of a given extrem point


281  /// </summary>


282  /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>


283  /// <param name="item">Given Item</param>


284  /// <param name="position">Given position</param>


285  /// <returns></returns>


286  private bool ItemIsInRs(KeyValuePair<PackingPosition, ResidualSpace> rs, PackingItem item, PackingPosition position) {


287  return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();


288  }


289 


290  protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


291  return binPacking.Items.Select(x => new {


292  Item = x.Value,


293  Position = binPacking.Positions[x.Key]


294  }).Where(x => x.Position.Y < position.Y)


295  .Select(x => Tuple.Create(x.Position, x.Item));


296  }


297 


298  protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


299  return binPacking.Items.Select(x => new {


300  Item = x.Value,


301  Position = binPacking.Positions[x.Key]


302  }).Where(x => x.Position.Z < position.Z)


303  .Select(x => Tuple.Create(x.Position, x.Item));


304  }


305 


306  protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


307  return binPacking.Items.Select(x => new {


308  Item = x.Value,


309  Position = binPacking.Positions[x.Key]


310  }).Where(x => x.Position.X < position.X)


311  .Select(x => Tuple.Create(x.Position, x.Item));


312  }


313 


314  /// <summary>


315  /// Returns the extreme points and its related residual spaces on the left side of an given item.


316  /// This extreme points are being created by intersecting two edges on the left side of the given item


317  /// (left  in front, left  on top) with all edges on the right side of all other items int the bin packing.


318  /// </summary>


319  /// <param name="item"></param>


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


321  /// <returns></returns>


322  private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


323  var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();


324  IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, item, position);


325  var edges = GetProjectionEdgesOnLeft(item, position);


326 


327  foreach (var otherItem in items) {


328  if (position.Equals(otherItem.Item1)) {


329  continue;


330  }


331 


332  var otherItemEdges = GetEdgesOnRight(otherItem.Item2, otherItem.Item1);


333  // left  in front


334  foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(1, 0, 0))) {


335  if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {


336  // As this edge has a vertical direction, every point of intersection won't have an item below.


337  // So finally it is being projected down.


338  var point = ProjectDown(binPacking, ProjectLeft(binPacking, ep));


339  var residualSpaces = CalculateResidualSpace(binPacking, point);


340  var newExtremePoint = point.ToPackingPosition(position.AssignedBin);


341  if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {


342  eps.Add(newExtremePoint, residualSpaces);


343  }


344  }


345  }


346 


347  // left  on top


348  foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(1, 0, 0))) {


349  if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {


350  var point = ProjectLeft(binPacking, ep);


351  var residualSpaces = CalculateResidualSpace(binPacking, point);


352  var newExtremePoint = point.ToPackingPosition(position.AssignedBin);


353  if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {


354  eps.Add(newExtremePoint, residualSpaces);


355  }


356  }


357  }


358  }


359  return eps;


360  }


361 


362 


363  /// <summary>


364  /// Returns the extreme points and its related residual spaces below of an given item.


365  /// This extreme points are being created by intersecting two edges below of the given item


366  /// (below  in front, below  right) with all edges on top side of all other items int the bin packing.


367  /// </summary>


368  /// <param name="item"></param>


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


370  /// <returns></returns>


371  private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


372  var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();


373  IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);


374  var edges = GetProjectionEdgesBelow(item, position);


375 


376  foreach (var otherItem in items) {


377  if (position.Equals(otherItem.Item1)) {


378  continue;


379  }


380 


381  var otherItemEdges = GetEdgesOnTop(otherItem.Item2, otherItem.Item1);


382  // below  in front


383  foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 1, 0))) {


384  if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {


385  var point = ProjectDown(binPacking, ep);


386  var residualSpaces = CalculateResidualSpace(binPacking, point);


387  var newExtremePoint = point.ToPackingPosition(position.AssignedBin);


388  if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {


389  eps.Add(newExtremePoint, residualSpaces);


390  }


391  }


392  }


393 


394  // below  right


395  foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 1, 0))) {


396  if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {


397  var point = ProjectDown(binPacking, ep);


398  var residualSpaces = CalculateResidualSpace(binPacking, point);


399  var newExtremePoint = point.ToPackingPosition(position.AssignedBin);


400  if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {


401  eps.Add(newExtremePoint, residualSpaces);


402  }


403  }


404  }


405  }


406  return eps;


407  }


408 


409  /// <summary>


410  /// Returns the extreme points and its related residual spaces below of an given item.


411  /// This extreme points are being created by intersecting two edges below of the given item


412  /// (right  behind, on top  behind) with all edges on top side of all other items int the bin packing.


413  /// </summary>


414  /// <param name="item"></param>


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


416  /// <returns></returns>


417  private IDictionary<PackingPosition, IEnumerable<ResidualSpace>> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {


418  var eps = new SortedList<PackingPosition, IEnumerable<ResidualSpace>>();


419  IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);


420  var edges = GetProjectionEdgesBehind(item, position);


421 


422  foreach (var otherItem in items) {


423  if (position.Equals(otherItem.Item1)) {


424  continue;


425  }


426 


427  var otherItemEdges = GetEdgesInFront(otherItem.Item2, otherItem.Item1);


428  // right  behind


429  foreach (var ep in IntersectionsForItem(edges[0], otherItemEdges, new Vector3D(0, 0, 1))) {


430  if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {


431  // As this edge has a vertical direction, every point of intersection won't have an item below.


432  // So finally it is being projected down.


433  var point = ProjectDown(binPacking, ProjectBackward(binPacking, ep));


434  var residualSpaces = CalculateResidualSpace(binPacking, point);


435  var newExtremePoint = point.ToPackingPosition(position.AssignedBin);


436  if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {


437  eps.Add(newExtremePoint, residualSpaces);


438  }


439  }


440  }


441 


442  // on top  behind


443  foreach (var ep in IntersectionsForItem(edges[1], otherItemEdges, new Vector3D(0, 0, 1))) {


444  if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {


445  var point = ProjectBackward(binPacking, ep);


446  var residualSpaces = CalculateResidualSpace(binPacking, point);


447  var newExtremePoint = point.ToPackingPosition(position.AssignedBin);


448  if (residualSpaces.Count() > 0 && !eps.ContainsKey(newExtremePoint)) {


449  eps.Add(newExtremePoint, residualSpaces);


450  }


451  }


452  }


453  }


454  return eps;


455  }


456 


457  #region Methods for getting the edges for items


458 


459  /// <summary>


460  /// Returns an array of packing position which represents the vertices of an item.


461  /// The position of a vertex in the array is mapped to an item as followed:


462  /// 45


463  /// / /


464  /// /  / 


465  /// / 0/1


466  /// 6/7 /


467  ///  /  /


468  /// / /


469  /// 23


470  ///


471  /// 0 = (0,0,0)


472  /// </summary>


473  /// <param name="item"></param>


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


475  /// <returns></returns>


476  private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {


477  int width = item.Width;


478  int depth = item.Depth;


479  return new Vector3D[] {


480  new Vector3D(position.X + 0, position.Y + 0, position.Z + 0), // (0,0,0)


481  new Vector3D(position.X + width, position.Y + 0, position.Z + 0), // (x,0,0)


482  new Vector3D(position.X + 0, position.Y + 0, position.Z + depth), // (0,0,z)


483  new Vector3D(position.X + width, position.Y + 0, position.Z + depth), // (x,0,z)


484 


485  new Vector3D(position.X + 0, position.Y + item.Height, position.Z + 0), // (0,y,0)


486  new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)


487  new Vector3D(position.X + 0, position.Y + item.Height, position.Z + depth), // (0,y,z)


488  new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)


489  };


490  }


491 


492  private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {


493  Vector3D[] points = GetVertices(item, position);


494 


495  return new Edge3D[] {


496  new Edge3D(points[2], points[6]),


497  new Edge3D(points[6], points[4])


498  };


499  }


500 


501  private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {


502  Vector3D[] points = GetVertices(item, position);


503 


504  return new Edge3D[] {


505  new Edge3D(points[2], points[3]),


506  new Edge3D(points[3], points[1])


507  };


508  }


509 


510  private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {


511  Vector3D[] points = GetVertices(item, position);


512 


513  return new Edge3D[] {


514  new Edge3D(points[1], points[5]),


515  new Edge3D(points[5], points[4])


516  };


517  }


518 


519  /// <summary>


520  /// Returns an array of edges which contains all edges of the rigth side of an given item.


521  /// </summary>


522  /// <param name="item"></param>


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


524  /// <returns></returns>


525  private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {


526  Vector3D[] points = GetVertices(item, position);


527 


528  return new Edge3D[] {


529  new Edge3D(points[1], points[5]),


530  new Edge3D(points[5], points[7]),


531  new Edge3D(points[7], points[3]),


532  new Edge3D(points[3], points[1])


533  };


534  }


535 


536  /// <summary>


537  /// Returns an array of edges which contains all edges on the top of an given item.


538  /// </summary>


539  /// <param name="item"></param>


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


541  /// <returns></returns>


542  private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {


543  Vector3D[] points = GetVertices(item, position);


544 


545  return new Edge3D[] {


546  new Edge3D(points[4], points[5]),


547  new Edge3D(points[5], points[7]),


548  new Edge3D(points[7], points[6]),


549  new Edge3D(points[6], points[4])


550  };


551  }


552 


553  /// <summary>


554  /// Returns an array of edges which contains all edges in front of an given item.


555  /// </summary>


556  /// <param name="item"></param>


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


558  /// <returns></returns>


559  private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {


560  Vector3D[] points = GetVertices(item, position);


561 


562  return new Edge3D[] {


563  new Edge3D(points[2], points[3]),


564  new Edge3D(points[3], points[7]),


565  new Edge3D(points[7], points[6]),


566  new Edge3D(points[6], points[2])


567  };


568  }


569 


570  #endregion


571 


572 


573  #region Intersections


574 


575  /// <summary>


576  /// Returns a collection of points where a given edge (projectedEdge) intersects with other edges.


577  /// The given edge (projectedEdge) will be projected by using the given vector direction


578  /// and a edge of the given edge collection.


579  /// The returned collecten can be empty.


580  /// </summary>


581  /// <param name="projectedEdge"></param>


582  /// <param name="edges"></param>


583  /// <param name="direction"></param>


584  /// <returns></returns>


585  private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges, Vector3D direction = null) {


586  IList<Vector3D> eps = new List<Vector3D>();


587  foreach (var edge in edges) {


588  Edge3D e = projectedEdge;


589  if (direction != null) {


590  if (direction.X != 0) {


591  e.Start.X = edge.Start.X;


592  e.End.X = edge.End.X;


593  } else if (direction.Y != 0) {


594  e.Start.Y = edge.Start.Y;


595  e.End.Y = edge.End.Y;


596  } else if (direction.Z != 0) {


597  e.Start.Z = edge.Start.Z;


598  e.End.Z = edge.End.Z;


599  }


600  }


601 


602  var ep = edge.Intersects(e);


603  if (ep != null) {


604  eps.Add(ep);


605  }


606  }


607 


608  return eps as IEnumerable<Vector3D>;


609  }


610 


611 


612 


613  #endregion


614 


615  /// <summary>


616  /// Calculates the residual spaces for an extreme point.


617  /// </summary>


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


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


620  /// <returns></returns>


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


622  return ResidualSpaceCalculatorFactory.CreateCalculator().CalculateResidualSpaces(binPacking, pos);


623  }


624  }


625  }

