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  using System.Collections.Concurrent;


31 


32  namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {


33  /// <summary>


34  /// This extreme point creation class uses the line projection based method for creating extreme points.


35  /// This projection method enhances the point based projection method by creating extra extreme points on the intersection points of two items.


36  /// </summary>


37  public class LineProjectionBasedEPCreator : ExtremePointCreator {


38 


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  //EdgeProjectionForNewItem(binPacking, newItem, position);


169  }


170 


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


172 


173  /// <summary>


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


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


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


177  /// </summary>


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


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


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


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


182  int newWidth = newItem.Width;


183  int newDepth = newItem.Depth;


184  var binShape = binPacking.BinShape;


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


186  PointProjection(binPacking, sourcePoint, ProjectDown);


187  PointProjection(binPacking, sourcePoint, ProjectBackward);


188 


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


190  PointProjection(binPacking, sourcePoint, ProjectLeft);


191  PointProjection(binPacking, sourcePoint, ProjectBackward);


192 


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


194  PointProjection(binPacking, sourcePoint, ProjectDown);


195  PointProjection(binPacking, sourcePoint, ProjectLeft);


196  }


197 


198 


199  /// <summary>


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


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


202  /// </summary>


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


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


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


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


207  Vector3D sourcePoint = new Vector3D(position);


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


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


210  if (point != null) {


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


212  }


213  }


214  }


215  #endregion


216 


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


218 


219  /// <summary>


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


221  ///  left


222  ///  back


223  ///  down.


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


225  /// </summary>


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


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


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


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


230  int newWidth = newItem.Width;


231  int newDepth = newItem.Depth;


232  var binShape = binPacking.BinShape;


233 


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


235  AddExtremePoint(binPacking, ep.Key);


236  }


237 


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


239  AddExtremePoint(binPacking, ep.Key);


240  }


241 


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


243  AddExtremePoint(binPacking, ep.Key);


244  }


245  }


246  #endregion


247 


248  /// <summary>


249  /// Updates the residual spaces.


250  /// It removes not needed ones.


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


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


253  /// </summary>


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


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


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


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


258  }


259 


260  /// <summary>


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


262  /// </summary>


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


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


265  /// <returns></returns>


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


267  foreach (var item in binPacking.Items) {


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


269  var depth = item.Value.Depth;


270  var width = item.Value.Width;


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


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


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


274  return true;


275  }


276  }


277  return false;


278  }


279 


280  /// <summary>


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


282  /// </summary>


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


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


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


286  /// <returns></returns>


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


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


289  }


290 


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


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


293  Item = x.Value,


294  Position = binPacking.Positions[x.Key]


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


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


297  }


298 


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


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


301  Item = x.Value,


302  Position = binPacking.Positions[x.Key]


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


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


305  }


306 


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


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


309  Item = x.Value,


310  Position = binPacking.Positions[x.Key]


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


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


313  }


314 


315  /// <summary>


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


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


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


319  /// </summary>


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


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


322  /// <returns></returns>


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


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


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


326  var edges = GetProjectionEdgesOnLeft(item, position);


327 


328  foreach (var otherItem in items) {


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


330  continue;


331  }


332 


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


334  // left  in front


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


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


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


338  // So finally it is being projected down.


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


340  var residualSpaces = CalculateResidualSpace(binPacking, point);


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


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


343  eps.Add(newExtremePoint, residualSpaces);


344  }


345  }


346  }


347 


348  // left  on top


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


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


351  var point = ProjectLeft(binPacking, ep);


352  var residualSpaces = CalculateResidualSpace(binPacking, point);


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


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


355  eps.Add(newExtremePoint, residualSpaces);


356  }


357  }


358  }


359  }


360  return eps;


361  }


362 


363 


364  /// <summary>


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


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


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


368  /// </summary>


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


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


371  /// <returns></returns>


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


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


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


375  var edges = GetProjectionEdgesBelow(item, position);


376 


377  foreach (var otherItem in items) {


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


379  continue;


380  }


381 


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


383  // below  in front


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


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


386  var point = ProjectDown(binPacking, ep);


387  var residualSpaces = CalculateResidualSpace(binPacking, point);


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


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


390  eps.Add(newExtremePoint, residualSpaces);


391  }


392  }


393  }


394 


395  // below  right


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


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


398  var point = ProjectDown(binPacking, ep);


399  var residualSpaces = CalculateResidualSpace(binPacking, point);


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


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


402  eps.Add(newExtremePoint, residualSpaces);


403  }


404  }


405  }


406  }


407  return eps;


408  }


409 


410  /// <summary>


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


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


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


414  /// </summary>


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


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


417  /// <returns></returns>


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


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


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


421  var edges = GetProjectionEdgesBehind(item, position);


422 


423  foreach (var otherItem in items) {


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


425  continue;


426  }


427 


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


429  // right  behind


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


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


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


433  // So finally it is being projected down.


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


435  var residualSpaces = CalculateResidualSpace(binPacking, point);


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


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


438  eps.Add(newExtremePoint, residualSpaces);


439  }


440  }


441  }


442 


443  // on top  behind


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


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


446  var point = ProjectBackward(binPacking, ep);


447  var residualSpaces = CalculateResidualSpace(binPacking, point);


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


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


450  eps.Add(newExtremePoint, residualSpaces);


451  }


452  }


453  }


454  }


455  return eps;


456  }


457 


458  #region Methods for getting the edges for items


459 


460  /// <summary>


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


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


463  /// 45


464  /// / /


465  /// /  / 


466  /// / 0/1


467  /// 6/7 /


468  ///  /  /


469  /// / /


470  /// 23


471  ///


472  /// 0 = (0,0,0)


473  /// </summary>


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


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


476  /// <returns></returns>


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


478  int width = item.Width;


479  int depth = item.Depth;


480  return new Vector3D[] {


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


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


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


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


485 


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


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


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


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


490  };


491  }


492 


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


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


495 


496  return new Edge3D[] {


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


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


499  };


500  }


501 


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


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


504 


505  return new Edge3D[] {


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


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


508  };


509  }


510 


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


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


513 


514  return new Edge3D[] {


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


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


517  };


518  }


519 


520  /// <summary>


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


522  /// </summary>


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


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


525  /// <returns></returns>


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


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


528 


529  return new Edge3D[] {


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


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


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


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


534  };


535  }


536 


537  /// <summary>


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


539  /// </summary>


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


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


542  /// <returns></returns>


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


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


545 


546  return new Edge3D[] {


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


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


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


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


551  };


552  }


553 


554  /// <summary>


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


556  /// </summary>


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


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


559  /// <returns></returns>


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


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


562 


563  return new Edge3D[] {


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


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


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


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


568  };


569  }


570 


571  #endregion


572 


573 


574  #region Intersections


575 


576  /// <summary>


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


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


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


580  /// The returned collecten can be empty.


581  /// </summary>


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


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


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


585  /// <returns></returns>


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


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


588  foreach (var edge in edges) {


589  Edge3D e = projectedEdge;


590  if (direction != null) {


591  if (direction.X != 0) {


592  e.Start.X = edge.Start.X;


593  e.End.X = edge.End.X;


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


595  e.Start.Y = edge.Start.Y;


596  e.End.Y = edge.End.Y;


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


598  e.Start.Z = edge.Start.Z;


599  e.End.Z = edge.End.Z;


600  }


601  }


602 


603  var ep = edge.Intersects(e);


604  if (ep != null) {


605  eps.Add(ep);


606  }


607  }


608 


609  return eps as IEnumerable<Vector3D>;


610  }


611 


612 


613 


614  #endregion


615 


616  /// <summary>


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


618  /// </summary>


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


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


621  /// <returns></returns>


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


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


624  }


625  }


626 


627 


628  }

