source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ResidualSpaceCalculation/ResidualSpaceCalculator.cs @ 15554

Last change on this file since 15554 was 15554, checked in by rhanghof, 21 months ago

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
File size: 7.4 KB
Line 
1using HeuristicLab.Problems.BinPacking3D.Geometry;
2using System;
3using System.Collections.Generic;
4using System.Linq;
5using System.Text;
6using System.Threading.Tasks;
7
8namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
9  internal class ResidualSpaceCalculator : IResidualSpaceCalculator {
10
11    internal ResidualSpaceCalculator() {}
12   
13    public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
14      IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
15      var rs1 = CalculateXZY(binPacking, point);
16      var rs2 = CalculateZYX(binPacking, point);
17      var rs3 = CalculateYXZ(binPacking, point);
18
19      if (!rs1.IsZero()) {
20        residualSpaces.Add(rs1);
21      }     
22
23
24      if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
25        residualSpaces.Add(rs2);
26      }
27      if (!rs3.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs3))) {
28        residualSpaces.Add(rs3);
29      }
30      return residualSpaces;
31    }
32
33    private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
34      ResidualSpace rs = new ResidualSpace(binPacking, point);
35
36      LimitResidualSpaceOnRight(binPacking, point, rs);
37      LimitResidualSpaceInFront(binPacking, point, rs);
38      LimitResidualSpaceAbove(binPacking, point, rs);
39      return rs;
40    }
41
42    private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
43      ResidualSpace rs = new ResidualSpace(binPacking, point);
44
45      LimitResidualSpaceInFront(binPacking, point, rs);
46      LimitResidualSpaceAbove(binPacking, point, rs);
47      LimitResidualSpaceOnRight(binPacking, point, rs);
48      return rs;
49    }
50
51    private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
52      ResidualSpace rs = new ResidualSpace(binPacking, point);
53
54      LimitResidualSpaceAbove(binPacking, point, rs);
55      LimitResidualSpaceOnRight(binPacking, point, rs);
56      LimitResidualSpaceInFront(binPacking, point, rs);
57      return rs;
58    }
59   
60    /// <summary>
61    /// Returnst true if a given residual space and item overlaps at the x-axis
62    /// </summary>
63    /// <param name="point"></param>
64    /// <param name="residualSpace"></param>
65    /// <param name="position"></param>
66    /// <param name="item"></param>
67    /// <returns></returns>
68    private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
69      if (point.X > position.X && point.X >= position.X + item.Width) {
70        return false;
71      }
72
73      if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
74        return false;
75      }
76      return true;
77    }
78
79    /// <summary>
80    /// Returnst true if a given residual space and item overlaps at the y-axis
81    /// </summary>
82    /// <param name="point"></param>
83    /// <param name="residualSpace"></param>
84    /// <param name="position"></param>
85    /// <param name="item"></param>
86    private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
87      if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
88        return false;
89      }
90
91      if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
92        return false;
93      }
94      return true;
95    }
96
97    /// <summary>
98    /// Returnst true if a given residual space and item overlaps at the z-axis
99    /// </summary>
100    /// <param name="point"></param>
101    /// <param name="residualSpace"></param>
102    /// <param name="position"></param>
103    /// <param name="item"></param>
104    private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
105      if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
106        return false;
107      }
108
109      if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
110        return false;
111      }
112      return true;
113    }
114
115    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
116      // if point.x >= position.x, the residual space would be located on the left side!
117      if (point.X >= position.X) {
118        return false;
119      }
120      var y = OverlapsY(point, residualSpace, position, item);
121      var z = OverlapsZ(point, residualSpace, position, item);
122      return y && z;
123    }
124
125    private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
126      if (point.Z >= position.Z) {
127        return false;
128      }
129      var x = OverlapsX(point, residualSpace, position, item);
130      var y = OverlapsY(point, residualSpace, position, item);
131
132      return x && y;
133    }
134
135    private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
136      if (point.Y >= position.Y) {
137        return false;
138      }
139      var x = OverlapsX(point, residualSpace, position, item);
140      var z = OverlapsZ(point, residualSpace, position, item);
141
142      return x && z;
143    }
144   
145    private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
146      if (residualSpace.IsZero()) {
147        return;
148      }
149     
150      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
151                                  .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
152      if (items.Count() > 0) {
153        foreach (var item in items) {
154          int newWidth = item.Position.X - point.X;
155          if (newWidth <= 0) {
156            residualSpace.SetZero();
157            return;
158          } else if (residualSpace.Width > newWidth) {
159            residualSpace.Width = newWidth;
160          }
161        }
162      }     
163    }
164
165    private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
166      if (residualSpace.IsZero()) {
167        return;
168      }
169
170      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
171                                  .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
172      if (items.Count() > 0) {
173        foreach (var item in items) {
174          int newDepth = item.Position.Z - point.Z;
175          if (newDepth <= 0) {
176            residualSpace.SetZero();
177            return;
178          } else if (residualSpace.Depth > newDepth) {
179            residualSpace.Depth = newDepth;
180          }
181        }
182      }
183    }
184
185    private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
186      if (residualSpace.IsZero()) {
187        return;
188      }
189
190      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
191                                  .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
192      if (items.Count() > 0) {
193        foreach (var item in items) {
194          int newHeight = item.Position.Y - point.Y;
195          if (newHeight <= 0) {
196            residualSpace.SetZero();
197            return;
198          } else if (residualSpace.Height > newHeight) {
199            residualSpace.Height = newHeight;
200          }
201        }
202      }
203    }
204  }
205}
Note: See TracBrowser for help on using the repository browser.