Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/07/17 08:24:24 (6 years ago)
Author:
rhanghof
Message:

#2817

  • Extreme point bin packing does not need the occupation layer anymore
  • Changes at the fitting algorithm. Now they are packing the items as in the paper of S. Martello, D. Pisinger, D. Vigo described
File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15424 r15454  
    2727using HeuristicLab.Common;
    2828using HeuristicLab.Problems.BinPacking;
     29using HeuristicLab.Problems.BinPacking3D.Geometry;
    2930
    3031namespace HeuristicLab.Problems.BinPacking3D {
    … …  
    3839    public BinPacking3D(PackingShape binShape)
    3940      : base(binShape) {
    40       ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
     41      ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
    4142      AddExtremePoint(binShape.Origin);
    4243      InitializeOccupationLayers();
    … …  
    6364      #endregion
    6465    }
     66
     67    #region New methods for bin packer class
     68
     69    public void AddItem(int itemID, PackingItem item, PackingPosition position) {
     70      Items[itemID] = item;
     71      Positions[itemID] = position;
     72      ExtremePoints.Remove(position);
     73      ResidualSpace.Remove(position);
     74    }
     75
     76    public void UpdateExtremePoints(PackingItem item, PackingPosition position, bool stackingConstraints) {
     77      /*if (stackingConstraints) {
     78        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X + item.Width, position.Y, position.Z));
     79        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y + item.Height, position.Z));
     80        AddExtremePoint(new PackingPosition(position.AssignedBin, position.X, position.Y, position.Z + item.Depth));
     81      } else {*/
     82      GenerateNewExtremePointsForNewItem(item, position);
     83
     84      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
     85      foreach (var above in GetItemsAbove(position)) {
     86        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
     87      }
     88      foreach (var front in GetItemsInfront(position)) {
     89        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
     90      }
     91      foreach (var right in GetItemsOnRight(position)) {
     92        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
     93      }
     94      //}
     95    }
     96
     97
     98
     99    /// <summary>
     100    /// In this case feasability is defined as following:
     101    /// 1. the item fits into the bin-borders;
     102    /// 2. the point is supported by something;
     103    /// 3. the item does not collide with another already packed item
     104    ///
     105    /// Unfortunatelly this method does not support item rotation
     106    /// </summary>
     107    /// <param name="item"></param>
     108    /// <param name="position"></param>
     109    /// <param name="stackingConstraints"></param>
     110    /// <returns></returns>
     111    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
     112      var b1 = CheckItemDimensions(item);
     113      var b2 = ItemCanBePlaced(item, position);
     114      var b3 = CheckStackingConstraints(item, position, stackingConstraints);
     115
     116      return b1 && b2 && b3;
     117    }
     118
     119    /// <summary>
     120    /// Compares the dimensions of a given item and the current bin.
     121    /// </summary>
     122    /// <param name="item"></param>
     123    /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns>
     124    private bool CheckItemDimensions(PackingItem item) {
     125      return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth;
     126    }
     127
     128    /// <summary>
     129    /// Returns true if a given item can be placed in the current bin
     130    /// </summary>
     131    /// <param name="givenItem"></param>
     132    /// <param name="givenItemPosition"></param>
     133    /// <returns></returns>
     134    private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
     135      // Check if the boundings of the bin would injured
     136      if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
     137          givenItemPosition.Y + givenItem.Height > BinShape.Height ||
     138          givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
     139        return false;
     140      }
     141
     142      //if the given item collides with any other item, it can not be placed
     143      foreach (var item in Items) {
     144        if (ItemsCollides(new Tuple<PackingPosition, PackingItem>(Positions[item.Key], item.Value),
     145                          new Tuple<PackingPosition, PackingItem>(givenItemPosition, givenItem))) {
     146          return false;
     147        }
     148      }
     149      return true;     
     150    }
     151
     152    /// <summary>
     153    /// Checks if two given items in a space collides
     154    /// </summary>
     155    /// <param name="t1"></param>
     156    /// <param name="t2"></param>
     157    /// <returns></returns>
     158    bool ItemsCollides(Tuple<PackingPosition, PackingItem> t1, Tuple<PackingPosition, PackingItem> t2) {
     159      var position1 = t1.Item1;
     160      var item1 = t1.Item2;
     161      var position2 = t2.Item1;
     162      var item2 = t2.Item2;
     163      var cx = (position2.X == position1.X) || (position2.X < position1.X && position2.X + item2.Width > position1.X) || (position2.X > position1.X && position1.X + item1.Width > position2.X);
     164      var cy = (position2.Y == position1.Y) || (position2.Y < position1.Y && position2.Y + item2.Height > position1.Y) || (position2.Y > position1.Y && position1.Y + item1.Height > position2.Y);
     165      var cz = (position2.Z == position1.Z) || (position2.Z < position1.Z && position2.Z + item2.Depth > position1.Z) || (position2.Z > position1.Z && position1.Z + item1.Depth > position2.Z);
     166      return cx && cy && cz;
     167    }
     168
     169    /// <summary>
     170    /// Checks the stacking constraints. This method depends that the given item can be placed at this position
     171    /// </summary>
     172    /// <param name="item"></param>
     173    /// <param name="position"></param>
     174    /// <param name="stackingConstraints"></param>
     175    /// <returns></returns>
     176    private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
     177      if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
     178        return true;
     179      }
     180
     181      return IsStaticStable(item, position) && IsWeightSupported(item, position);
     182    }
     183
     184
     185    /// <summary>
     186    /// Checks if a given item has any point lieing on another item.
     187    /// </summary>
     188    /// <param name="item"></param>
     189    /// <param name="position"></param>
     190    /// <returns></returns>
     191    public bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
     192      bool p1, p2, p3, p4;
     193      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     194
     195      return p1 || p2 || p3 || p4;
     196    }
     197
     198    /// <summary>
     199    /// Checks if a given item is static stable.
     200    /// A item is static stable if all edges have an object below.
     201    /// </summary>
     202    /// <param name="item"></param>
     203    /// <param name="position"></param>
     204    /// <returns></returns>
     205    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
     206      bool p1, p2, p3, p4;
     207      PointsLiesOnAnItems(item, position, out p1, out p2, out p3, out p4);
     208      return p1 && p2 && p3 && p4;
     209    }
     210
     211    /// <summary>
     212    /// This method sets the out parameters p1 ... p3 if the point lies on another item.
     213    /// p1 ... p3 represents one point on the bottom side of an given item.
     214    /// +---------+
     215    /// |p1     p2|
     216    /// |         |
     217    /// |p4     p3|
     218    /// +---------+
     219    /// </summary>
     220    /// <param name="item">Given item</param>
     221    /// <param name="position">Given item position</param>
     222    /// <param name="p1"></param>
     223    /// <param name="p2"></param>
     224    /// <param name="p3"></param>
     225    /// <param name="p4"></param>
     226    public void PointsLiesOnAnItems(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
     227      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
     228      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
     229      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
     230      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
     231
     232      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
     233
     234      p1 = itemsP1.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
     235      p2 = itemsP2.Where(x => position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
     236      p3 = itemsP3.Where(x => position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
     237      p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
     238    }
     239
     240
     241    /// <summary>
     242    ///
     243    /// </summary>
     244    /// <param name="item"></param>
     245    /// <param name="position"></param>
     246    /// <param name="itemsP1"></param>
     247    /// <param name="itemsP2"></param>
     248    /// <param name="itemsP3"></param>
     249    /// <param name="itemsP4"></param>
     250    private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
     251                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1,
     252                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2,
     253                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3,
     254                                   out IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4) {
     255      itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
     256      itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
     257      itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
     258      itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
     259
     260    }
     261
     262    /// <summary>
     263    /// Returns a collection of items which are below a given point.
     264    /// The top side of every item is at the same level as the Y-coordinate of the given position.
     265    /// </summary>
     266    /// <param name="position"></param>
     267    /// <returns></returns>
     268    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelowForPosition(PackingPosition position) {
     269      return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
     270    }
     271
     272
     273    /// <summary>
     274    /// Checks if a given the weight of an given item is supportet by the items below.
     275    /// </summary>
     276    /// <param name="item"></param>
     277    /// <param name="position"></param>
     278    /// <returns></returns>
     279    public bool IsWeightSupported(PackingItem item, PackingPosition position) {
     280      if (position.Y == 0) {
     281        return true;
     282      }
     283      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP1;
     284      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP2;
     285      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP3;
     286      IEnumerable<Tuple<PackingPosition, PackingItem>> itemsP4;
     287
     288      GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
     289
     290      return itemsP1.Where(x => x.Item2.SupportsStacking(item)).Any() &&
     291        itemsP2.Where(x => x.Item2.SupportsStacking(item)).Any() &&
     292        itemsP3.Where(x => x.Item2.SupportsStacking(item)).Any() &&
     293        itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any();
     294    }
     295
     296
     297
     298    #endregion
    65299
    66300    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
    … …  
    83317    }
    84318
     319
     320
    85321    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
    86322      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
    … …  
    168404    }
    169405
     406
    170407    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    171408      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
    … …  
    204441
    205442    #region Projections
    206        
     443
    207444    private Vector3D ProjectBackward(Vector3D pos) {
    208445      var line = new Line3D(pos, new Vector3D(0, 0, -1));
    … …  
    268505    #region Get items
    269506
    270    
     507    /// <summary>
     508    ///
     509    /// </summary>
     510    /// <param name="pos"></param>
     511    /// <returns></returns>
    271512    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
    272513      var line = new Line3D(pos, new Vector3D(0, 1, 0));
    … …  
    298539        .Select(x => Tuple.Create(x.Position, x.Item));
    299540    }
     541
     542    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) {
     543      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     544      return Items.Select(x => new {
     545        Item = x.Value,
     546        Position = Positions[x.Key],
     547        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
     548      }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
     549        .Select(x => Tuple.Create(x.Position, x.Item));
     550    }
     551
     552    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {
     553      var line = new Line3D(pos, new Vector3D(0, 0, 1));
     554      return Items.Select(x => new {
     555        Item = x.Value,
     556        Position = Positions[x.Key],
     557        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))
     558      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     559        .Select(x => Tuple.Create(x.Position, x.Item));
     560    }
     561
     562    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {
     563      var line = new Line3D(pos, new Vector3D(1, 0, 0));
     564      return Items.Select(x => new {
     565        Item = x.Value,
     566        Position = Positions[x.Key],
     567        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))
     568      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     569        .Select(x => Tuple.Create(x.Position, x.Item));
     570    }
     571
    300572    #endregion
     573
     574
    301575
    302576    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
    … …  
    316590    }
    317591
    318     public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
    319       var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
    320       return feasible
    321         && IsSupportedByAtLeastOnePoint(item, position)
    322         && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
    323     }
     592 
    324593
    325594    #region Sliding based packing   
    … …  
    425694      return shortestSide;
    426695    }
    427     public override bool IsStaticStable(PackingItem item, PackingPosition position) {
    428       //Static stability is given, if item is placed on the ground
    429       if (position.Y == 0)
    430         return true;
    431 
    432       if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
    433         && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
    434         && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
    435         && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
    436         return true;
    437 
    438       return false;
    439     }
    440 
    441     public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
    442       if (position.Y == 0)
    443         return true;
    444 
    445       int y = position.Y - 1;
    446       for (int x = position.X; x < position.X + item.Width; x++)
    447         for (int z = position.Z; z < position.Z + item.Depth; z++)
    448           if (IsPointOccupied(new PackingPosition(0, x, y, z)))
    449             return true;
    450 
    451       return false;
    452     }
    453     public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
    454       if (ep.Y == 0)
    455         return true;
    456 
    457       if (Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
    458         && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
    459         && Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
    460         && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
    461         return true;
    462 
    463       return false;
    464     }
     696   
    465697
    466698    protected override void InitializeOccupationLayers() {
    … …  
    488720      return result;
    489721    }
    490    
     722
    491723    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    492724      foreach (var ep in ExtremePoints.ToList()) {
    … …  
    509741          }
    510742        }
    511         if (ep.Z <= pos.Z &&
     743
     744        if (ep.Z <= pos.Z &&
    512745            ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
    513746            ep.X >= pos.X && ep.X < pos.X + width) {
    … …  
    517750          changed = true;
    518751        }
     752
    519753        if (changed) {
    520754          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
    … …  
    529763    }
    530764
    531     #region Helper classes for vector math
    532     private class Vector3D {
    533       public int X;
    534       public int Y;
    535       public int Z;
    536       public Vector3D() { }
    537       public Vector3D(int x, int y, int z) {
    538         X = x;
    539         Y = y;
    540         Z = z;
    541       }
    542       public Vector3D(PackingPosition pos) {
    543         X = pos.X;
    544         Y = pos.Y;
    545         Z = pos.Z;
    546       }
    547       public static Vector3D AlongX(Vector3D pos, PackingItem item) {
    548         return new Vector3D(
    549           pos.X + item.Width,
    550           pos.Y,
    551           pos.Z
    552         );
    553       }
    554       public static Vector3D AlongY(Vector3D pos, PackingItem item) {
    555         return new Vector3D(
    556           pos.X,
    557           pos.Y + item.Height,
    558           pos.Z
    559         );
    560       }
    561       public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
    562         return new Vector3D(
    563           pos.X,
    564           pos.Y,
    565           pos.Z + item.Depth
    566         );
    567       }
    568       public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
    569         return new Vector3D(
    570           pos.X + item.Width,
    571           pos.Y,
    572           pos.Z
    573         );
    574       }
    575       public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
    576         return new Vector3D(
    577           pos.X,
    578           pos.Y + item.Height,
    579           pos.Z
    580         );
    581       }
    582       public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
    583         return new Vector3D(
    584           pos.X,
    585           pos.Y,
    586           pos.Z + item.Depth
    587         );
    588       }
    589 
    590       public Vector3D Cross(Vector3D b) {
    591         return new Vector3D(
    592           Y * b.Z - Z * b.Y,
    593           -X * b.Z + Z * b.X,
    594           X * b.Y - Y * b.X
    595         );
    596       }
    597 
    598       public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
    599         return X >= pos.X && X < pos.X + rs.Item1
    600           && Y >= pos.Y && Y < pos.Y + rs.Item2
    601           && Z >= pos.Z && Z < pos.Z + rs.Item3;
    602       }
    603 
    604       public static int operator *(Vector3D a, Vector3D b) {
    605         return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
    606       }
    607       public static Vector3D operator *(int a, Vector3D b) {
    608         return new Vector3D(a * b.X, a * b.Y, a * b.Z);
    609       }
    610       public static Vector3D operator *(Vector3D a, int b) {
    611         return new Vector3D(a.X * b, a.Y * b, a.Z * b);
    612       }
    613       public static Vector3D operator +(Vector3D a, Vector3D b) {
    614         return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
    615       }
    616       public static Vector3D operator -(Vector3D a, Vector3D b) {
    617         return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
    618       }
    619 
    620       public override bool Equals(object obj) {
    621         var packPos = obj as PackingPosition;
    622         if (packPos != null) {
    623           return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
    624         }
    625         var vec = obj as Vector3D;
    626         if (vec != null) {
    627           return X == vec.X && Y == vec.Y && Z == vec.Z;
    628         }
    629         return false;
    630       }
    631     }
    632 
    633     // A line is given as a point and a directing vector
    634     private class Line3D {
    635       public Vector3D Point;
    636       public Vector3D Direction;
    637 
    638       public Line3D(Vector3D point, Vector3D direction) {
    639         Point = point;
    640         Direction = direction;
    641       }
    642       public Line3D(PackingPosition position, Vector3D direction) {
    643         Point = new Vector3D(position);
    644         Direction = direction;
    645       }
    646 
    647       public bool Intersects(Plane3D plane) {
    648         return plane.Intersects(this);
    649       }
    650 
    651       public Vector3D Intersect(Plane3D plane) {
    652         return plane.Intersect(this);
    653       }
    654     }
    655 
    656     private enum Side { Top, Left, Bottom, Right, Front, Back }
    657     // A plane is given as a point and two directing vectors
    658     private class Plane3D {
    659       public Vector3D Point { get; private set; }
    660       public Vector3D Direction1 { get; private set; }
    661       public Vector3D Direction2 { get; private set; }
    662       public Vector3D Normal { get; private set; }
    663       private int rhs;
    664 
    665       public Plane3D(PackingShape bin, Side side) {
    666         switch (side) {
    667           case Side.Top: // ZX plane
    668             Point = new Vector3D(0, bin.Height, 0);
    669             Direction1 = new Vector3D(0, 0, bin.Depth);
    670             Direction2 = new Vector3D(bin.Width, 0, 0);
    671             break;
    672           case Side.Left: // ZY plane
    673             Point = new Vector3D(0, 0, 0);
    674             Direction1 = new Vector3D(0, 0, bin.Depth);
    675             Direction2 = new Vector3D(0, bin.Height, 0);
    676             break;
    677           case Side.Bottom: // XZ plane
    678             Point = new Vector3D(0, 0, 0);
    679             Direction1 = new Vector3D(bin.Width, 0, 0);
    680             Direction2 = new Vector3D(0, 0, bin.Depth);
    681             break;
    682           case Side.Right: // YZ plane
    683             Point = new Vector3D(bin.Width, 0, 0);
    684             Direction1 = new Vector3D(0, bin.Height, 0);
    685             Direction2 = new Vector3D(0, 0, bin.Depth);
    686             break;
    687           case Side.Front: // XY plane
    688             Point = new Vector3D(0, 0, bin.Depth);
    689             Direction1 = new Vector3D(bin.Width, 0, 0);
    690             Direction2 = new Vector3D(0, bin.Height, 0);
    691             break;
    692           case Side.Back: // YX plane
    693             Point = new Vector3D(0, 0, 0);
    694             Direction1 = new Vector3D(0, bin.Height, 0);
    695             Direction2 = new Vector3D(bin.Width, 0, 0);
    696             break;
    697         }
    698         Normal = Direction1.Cross(Direction2);
    699         rhs = 0;
    700       }
    701 
    702       public Plane3D(PackingPosition pos, PackingItem item, Side side) {
    703         // the directing vectors are chosen such that normal always points outside the packing item
    704         switch (side) {
    705           case Side.Top: // ZX plane
    706             Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
    707             Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    708             Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    709             break;
    710           case Side.Left: // ZY plane
    711             Point = new Vector3D(pos.X, pos.Y, pos.Z);
    712             Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    713             Direction2 = new Vector3D(0, item.Height, 0);
    714             break;
    715           case Side.Bottom: // XZ plane
    716             Point = new Vector3D(pos.X, pos.Y, pos.Z);
    717             Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    718             Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    719             break;
    720           case Side.Right: // YZ plane
    721             Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
    722             Direction1 = new Vector3D(0, item.Height, 0);
    723             Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
    724             break;
    725           case Side.Front: // XY plane
    726             Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
    727             Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    728             Direction2 = new Vector3D(0, item.Height, 0);
    729             break;
    730           case Side.Back: // YX plane
    731             Point = new Vector3D(pos.X, pos.Y, pos.Z);
    732             Direction1 = new Vector3D(0, item.Height, 0);
    733             Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
    734             break;
    735         }
    736         Normal = Direction1.Cross(Direction2);
    737         rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
    738       }
    739 
    740       public bool IsElementOf(Vector3D point) {
    741         return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
    742       }
    743 
    744       public bool Intersects(Line3D line) {
    745         return Intersect(line) != null;
    746       }
    747 
    748       public Vector3D Intersect(Line3D line) {
    749         var denom = Normal * line.Direction;
    750         if (denom == 0) {
    751           // dir is perpendicular to the normal vector of the plane
    752           // this means they intersect if p1 is element of the plane
    753           // also the plane does not stretch infinitely, but is bound
    754           // to the parallelogram spanned by the point and the two
    755           // directing vectors
    756           if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
    757             return line.Point;
    758           else return null;
    759         }
    760         var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
    761         if (IsWithinDirectionalVectors(intersect)) return intersect;
    762         return null;
    763       }
    764 
    765       public bool IsWithinDirectionalVectors(Vector3D point) {
    766         return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
    767             && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
    768             && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
    769       }
    770     }
    771     #endregion
     765
    772766  }
    773767}
Note: See TracChangeset for help on using the changeset viewer.