source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/PackingShape.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: 7.2 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 HeuristicLab.Core;
24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
25using HeuristicLab.Common;
26using HeuristicLab.Data;
27using HeuristicLab.Parameters;
28using HeuristicLab.Problems.BinPacking;
29
30namespace HeuristicLab.Problems.BinPacking3D {
31  [Item("PackingShape (3d)", "Represents the cuboid measures (width, height, depth) of a three-dimensional cuboidic bin-packing object.")]
32  [StorableClass]
33  public class PackingShape : PackingShape<PackingPosition>, IComparable<PackingShape> {
34    public IFixedValueParameter<IntValue> HeightParameter {
35      get { return (IFixedValueParameter<IntValue>)Parameters["Height"]; }
36    }
37    public IFixedValueParameter<IntValue> WidthParameter {
38      get { return (IFixedValueParameter<IntValue>)Parameters["Width"]; }
39    }
40    public IFixedValueParameter<IntValue> DepthParameter {
41      get { return (IFixedValueParameter<IntValue>)Parameters["Depth"]; }
42    }
43
44    public int Height {
45      get { return HeightParameter.Value.Value; }
46      set { HeightParameter.Value.Value = value; }
47    }
48
49    public int Width {
50      get { return WidthParameter.Value.Value; }
51      set { WidthParameter.Value.Value = value; }
52    }
53
54    public int Depth {
55      get { return DepthParameter.Value.Value; }
56      set { DepthParameter.Value.Value = value; }
57    }
58
59    [StorableConstructor]
60    protected PackingShape(bool deserializing) : base(deserializing) { }
61    protected PackingShape(PackingShape original, Cloner cloner)
62      : base(original, cloner) {
63      RegisterEvents();
64    }
65    public PackingShape()
66      : base() {
67      Parameters.Add(new FixedValueParameter<IntValue>("Width"));
68      Parameters.Add(new FixedValueParameter<IntValue>("Height"));
69      Parameters.Add(new FixedValueParameter<IntValue>("Depth"));
70
71      RegisterEvents();
72    }
73
74    public PackingShape(int width, int height, int depth)
75      : this() {
76      this.Width = width;
77      this.Height = height;
78      this.Depth = depth;
79    }
80
81    public override IDeepCloneable Clone(Cloner cloner) {
82      return new PackingShape(this, cloner);
83    }
84
85    [StorableHook(HookType.AfterDeserialization)]
86    private void AfterDeserialization() {
87      RegisterEvents();
88    }
89
90    private void RegisterEvents() {
91      // only because of ToString override
92      HeightParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
93      WidthParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
94      DepthParameter.Value.ValueChanged += (sender, args) => OnToStringChanged();
95    }
96
97    public override string ToString() {
98      return String.Format("CuboidPackingShape ({0}, {1}, {2})", this.Width, this.Height, this.Depth);
99    }
100
101    #region IComparable Members
102
103    public int CompareTo(PackingShape other) {
104      //Using "Clustered-Area-Height"-comparison as descr
105
106      int result = (this.Width * this.Depth).CompareTo(other.Width * other.Depth);
107
108      if (result == 0)
109        result = this.Volume.CompareTo(other.Volume);
110      if (result == 0)
111        result = this.Height.CompareTo(other.Height);
112      return result;
113    }
114
115    public override int CompareTo(object obj) {
116      var other = (PackingShape)obj;
117      if (other != null) return CompareTo(other);
118      else throw new ArgumentException(string.Format("Cannot compare with object {0}", obj), "obj");
119    }
120
121    #endregion
122
123    private struct CuboidDiagonal {
124      public int x1;
125      public int y1;
126      public int z1;
127      public int x2;
128      public int y2;
129      public int z2;
130      public CuboidDiagonal(PackingShape myShape) : this(new PackingPosition(0, 0, 0, 0), myShape) { }
131      public CuboidDiagonal(PackingPosition myPosition, PackingShape myShape) {
132        x1 = myPosition.X;
133        y1 = myPosition.Y;
134        z1 = myPosition.Z;
135        x2 = myPosition.X + (myPosition.Rotated ? myShape.Depth : myShape.Width) - 1;
136        y2 = myPosition.Y + myShape.Height - 1;
137        z2 = myPosition.Z + (myPosition.Rotated ? myShape.Width : myShape.Depth) - 1;
138      }
139    }
140
141
142    #region Helpers
143    public override PackingPosition Origin { get { return new PackingPosition(0, 0, 0, 0); } }
144    public override int Volume { get { return Width * Height * Depth; } }
145
146    public override bool EnclosesPoint(PackingPosition myPosition, PackingPosition checkedPoint) {
147      return (myPosition.X <= checkedPoint.X &&
148                (myPosition.X + (myPosition.Rotated ? Depth : Width) - 1) >= checkedPoint.X &&
149                myPosition.Y <= checkedPoint.Y &&
150                (myPosition.Y + Height - 1) >= checkedPoint.Y &&
151                myPosition.Z <= checkedPoint.Z &&
152                (myPosition.Z + (myPosition.Rotated ? Width : Depth) - 1) >= checkedPoint.Z);
153    }
154    public override bool Encloses(PackingPosition checkedPosition, PackingShape<PackingPosition> checkedShape) {
155      return Encloses(checkedPosition, (PackingShape)checkedShape);
156    }
157    private bool Encloses(PackingPosition checkedPosition, PackingShape checkedShape) {
158      return Encloses(new CuboidDiagonal(this), new CuboidDiagonal(checkedPosition, checkedShape));
159    }
160    private bool Encloses(CuboidDiagonal c1, CuboidDiagonal c2) {
161      return (c1.x1 <= c2.x1 &&
162                c1.x2 >= c2.x2 &&
163                c1.y1 <= c2.y1 &&
164                c1.y2 >= c2.y2 &&
165                c1.z1 <= c2.z1 &&
166                c1.z2 >= c2.z2);
167    }
168
169    public override bool Overlaps(PackingPosition myPosition, PackingPosition checkedPosition, PackingShape<PackingPosition> checkedShape) {
170      return Overlaps(myPosition, checkedPosition, (PackingShape)checkedShape);
171    }
172    private bool Overlaps(PackingPosition myPosition, PackingPosition checkedPosition, PackingShape checkedShape) {
173      return Overlaps(new CuboidDiagonal(myPosition, this), new CuboidDiagonal(checkedPosition, checkedShape));
174    }
175    private bool Overlaps(CuboidDiagonal c1, CuboidDiagonal c2) {
176      return !(c1.x1 > c2.x2 ||
177               c1.y1 > c2.y2 ||
178               c1.z1 > c2.z2 ||
179               c1.x2 < c2.x1 ||
180               c1.y2 < c2.y1 ||
181               c1.z2 < c2.z1);
182    }
183
184    public override void ApplyHorizontalOrientation() {
185      if (Width > Depth) {
186        var aux = Width;
187        Width = Depth;
188        Depth = aux;
189      }
190    }
191    #endregion
192
193  }
194}
Note: See TracBrowser for help on using the repository browser.