1  using System;


2  using System.Collections.Generic;


3  using System.Linq;


4  using System.Text;


5  using System.Threading.Tasks;


6 


7  namespace HeuristicLab.Problems.BinPacking3D.Geometry {


8  internal enum Side { Top, Left, Bottom, Right, Front, Back }


9 


10  /// <summary>


11  /// A plane is given as a point and two directing vectors


12  /// </summary>


13  internal class Plane3D {


14  public Vector3D Point { get; private set; }


15  public Vector3D Direction1 { get; private set; }


16  public Vector3D Direction2 { get; private set; }


17  public Vector3D Normal { get; private set; }


18  private int rhs;


19 


20  public Plane3D(PackingShape bin, Side side) {


21  switch (side) {


22  case Side.Top: // ZX plane


23  Point = new Vector3D(0, bin.Height, 0);


24  Direction1 = new Vector3D(0, 0, bin.Depth);


25  Direction2 = new Vector3D(bin.Width, 0, 0);


26  break;


27  case Side.Left: // ZY plane


28  Point = new Vector3D(0, 0, 0);


29  Direction1 = new Vector3D(0, 0, bin.Depth);


30  Direction2 = new Vector3D(0, bin.Height, 0);


31  break;


32  case Side.Bottom: // XZ plane


33  Point = new Vector3D(0, 0, 0);


34  Direction1 = new Vector3D(bin.Width, 0, 0);


35  Direction2 = new Vector3D(0, 0, bin.Depth);


36  break;


37  case Side.Right: // YZ plane


38  Point = new Vector3D(bin.Width, 0, 0);


39  Direction1 = new Vector3D(0, bin.Height, 0);


40  Direction2 = new Vector3D(0, 0, bin.Depth);


41  break;


42  case Side.Front: // XY plane


43  Point = new Vector3D(0, 0, bin.Depth);


44  Direction1 = new Vector3D(bin.Width, 0, 0);


45  Direction2 = new Vector3D(0, bin.Height, 0);


46  break;


47  case Side.Back: // YX plane


48  Point = new Vector3D(0, 0, 0);


49  Direction1 = new Vector3D(0, bin.Height, 0);


50  Direction2 = new Vector3D(bin.Width, 0, 0);


51  break;


52  }


53  Normal = Direction1.Cross(Direction2);


54  rhs = 0;


55  }


56 


57  public Plane3D(PackingPosition pos, PackingItem item, Side side) {


58  // the directing vectors are chosen such that normal always points outside the packing item


59  switch (side) {


60  case Side.Top: // ZX plane


61  Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);


62  Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);


63  Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);


64  break;


65  case Side.Left: // ZY plane


66  Point = new Vector3D(pos.X, pos.Y, pos.Z);


67  Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);


68  Direction2 = new Vector3D(0, item.Height, 0);


69  break;


70  case Side.Bottom: // XZ plane


71  Point = new Vector3D(pos.X, pos.Y, pos.Z);


72  Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);


73  Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);


74  break;


75  case Side.Right: // YZ plane


76  Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);


77  Direction1 = new Vector3D(0, item.Height, 0);


78  Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);


79  break;


80  case Side.Front: // XY plane


81  Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));


82  Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);


83  Direction2 = new Vector3D(0, item.Height, 0);


84  break;


85  case Side.Back: // YX plane


86  Point = new Vector3D(pos.X, pos.Y, pos.Z);


87  Direction1 = new Vector3D(0, item.Height, 0);


88  Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);


89  break;


90  }


91  Normal = Direction1.Cross(Direction2);


92  rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;


93  }


94 


95  public bool IsElementOf(Vector3D point) {


96  return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;


97  }


98 


99  public bool Intersects(Line3D line) {


100  return Intersect(line) != null;


101  }


102 


103  public Vector3D Intersect(Line3D line) {


104  var denom = Normal * line.Direction;


105  if (denom == 0) {


106  // dir is perpendicular to the normal vector of the plane


107  // this means they intersect if p1 is element of the plane


108  // also the plane does not stretch infinitely, but is bound


109  // to the parallelogram spanned by the point and the two


110  // directing vectors


111  if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))


112  return line.Point;


113  else


114  return null;


115  }


116  var intersect = line.Point + ((Normal * (Point  line.Point)) / denom) * line.Direction;


117  if (IsWithinDirectionalVectors(intersect))


118  return intersect;


119  return null;


120  }


121 


122  public bool IsWithinDirectionalVectors(Vector3D point) {


123  return point.X >= Point.X && (Direction1.X + Direction2.X == 0  (point.X < Point.X + Direction1.X  point.X < Point.X + Direction2.X))


124  && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0  (point.Y < Point.Y + Direction1.Y  point.Y < Point.Y + Direction2.Y))


125  && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0  (point.Z < Point.Z + Direction1.Z  point.Z < Point.Z + Direction2.Z));


126  }


127  }


128  }

