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

Last change on this file since 15617 was 15617, checked in by rhanghof, 20 months ago

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File size: 6.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using System.Threading.Tasks;
27
28namespace HeuristicLab.Problems.BinPacking3D.Geometry {
29  public enum Side { Top, Left, Bottom, Right, Front, Back }
30
31  /// <summary>
32  /// A plane is given as a point and two directing vectors
33  /// </summary>
34  public class Plane3D {
35    public Vector3D Point { get; private set; }
36    public Vector3D Direction1 { get; private set; }
37    public Vector3D Direction2 { get; private set; }
38    public Vector3D Normal { get; private set; }
39
40    private int rhs;
41
42    public Plane3D(PackingShape bin, Side side) {
43      switch (side) {
44        case Side.Top: // ZX plane
45          Point = new Vector3D(0, bin.Height, 0);
46          Direction1 = new Vector3D(0, 0, bin.Depth);
47          Direction2 = new Vector3D(bin.Width, 0, 0);
48          break;
49        case Side.Left: // ZY plane
50          Point = new Vector3D(0, 0, 0);
51          Direction1 = new Vector3D(0, 0, bin.Depth);
52          Direction2 = new Vector3D(0, bin.Height, 0);
53          break;
54        case Side.Bottom: // XZ plane
55          Point = new Vector3D(0, 0, 0);
56          Direction1 = new Vector3D(bin.Width, 0, 0);
57          Direction2 = new Vector3D(0, 0, bin.Depth);
58          break;
59        case Side.Right: // YZ plane
60          Point = new Vector3D(bin.Width, 0, 0);
61          Direction1 = new Vector3D(0, bin.Height, 0);
62          Direction2 = new Vector3D(0, 0, bin.Depth);
63          break;
64        case Side.Front: // XY plane
65          Point = new Vector3D(0, 0, bin.Depth);
66          Direction1 = new Vector3D(bin.Width, 0, 0);
67          Direction2 = new Vector3D(0, bin.Height, 0);
68          break;
69        case Side.Back: // YX plane
70          Point = new Vector3D(0, 0, 0);
71          Direction1 = new Vector3D(0, bin.Height, 0);
72          Direction2 = new Vector3D(bin.Width, 0, 0);
73          break;
74      }
75      Normal = Direction1.Cross(Direction2);
76      rhs = 0;
77    }
78
79    public Plane3D(PackingPosition pos, PackingItem item, Side side) {
80      // the directing vectors are chosen such that normal always points outside the packing item
81      switch (side) {
82        case Side.Top: // ZX plane
83          Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
84          Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
85          Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
86          break;
87        case Side.Left: // ZY plane
88          Point = new Vector3D(pos.X, pos.Y, pos.Z);
89          Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
90          Direction2 = new Vector3D(0, item.Height, 0);
91          break;
92        case Side.Bottom: // XZ plane
93          Point = new Vector3D(pos.X, pos.Y, pos.Z);
94          Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
95          Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
96          break;
97        case Side.Right: // YZ plane
98          Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
99          Direction1 = new Vector3D(0, item.Height, 0);
100          Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
101          break;
102        case Side.Front: // XY plane
103          Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
104          Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
105          Direction2 = new Vector3D(0, item.Height, 0);
106          break;
107        case Side.Back: // YX plane
108          Point = new Vector3D(pos.X, pos.Y, pos.Z);
109          Direction1 = new Vector3D(0, item.Height, 0);
110          Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
111          break;
112      }
113      Normal = Direction1.Cross(Direction2);
114      rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
115    }
116
117    /// <summary>
118    /// Returns true if the given point is an element of the current plane
119    /// </summary>
120    /// <param name="point"></param>
121    /// <returns></returns>
122    public bool IsElementOf(Vector3D point) {
123      return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
124    }
125
126    /// <summary>
127    /// Returns true, if the given line intersects with the current plane
128    /// </summary>
129    /// <param name="line"></param>
130    /// <returns></returns>
131    public bool Intersects(Line3D line) {
132      return Intersect(line) != null;
133    }
134
135    /// <summary>
136    /// Returns the point of intersection of a given line and the current plane.
137    /// It returns null if there is no intersection.
138    /// </summary>
139    /// <param name="line"></param>
140    /// <returns></returns>
141    public Vector3D Intersect(Line3D line) {
142      var denom = Normal * line.Direction;
143      if (denom == 0) {
144        // dir is perpendicular to the normal vector of the plane
145        // this means they intersect if p1 is element of the plane
146        // also the plane does not stretch infinitely, but is bound
147        // to the parallelogram spanned by the point and the two
148        // directing vectors
149        if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
150          return line.Point;
151        else
152          return null;
153      }
154      var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
155      if (IsWithinDirectionalVectors(intersect))
156        return intersect;
157      return null;
158    }
159
160    public bool IsWithinDirectionalVectors(Vector3D point) {
161      return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
162          && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
163          && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
164    }
165  }
166}
Note: See TracBrowser for help on using the repository browser.