source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Plane3D.cs @ 15454

Last change on this file since 15454 was 15454, checked in by rhanghof, 23 months ago

#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 size: 5.4 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Threading.Tasks;
6
7namespace 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}
Note: See TracBrowser for help on using the repository browser.