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

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

#2817:

  • Changed the calculation algorithm for creating extreme points by using line based projection
  • Changed the calculation of the residual spaces for line based projection
File size: 6.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      residualSpaces.Add(rs1);
20
21
22      if (!residualSpaces.Any(rs => rs.Equals(rs2))) {
23        residualSpaces.Add(rs2);
24      }
25      if (!residualSpaces.Any(rs => rs.Equals(rs3))) {
26        residualSpaces.Add(rs3);
27      }
28      return residualSpaces;
29    }
30
31    private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
32      ResidualSpace rs = new ResidualSpace(binPacking, point);
33
34      LimitResidualSpaceOnRight(binPacking, point, rs);
35      LimitResidualSpaceInFront(binPacking, point, rs);
36      LimitResidualSpaceAbove(binPacking, point, rs);
37      return rs;
38    }
39
40    private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
41      ResidualSpace rs = new ResidualSpace(binPacking, point);
42
43      LimitResidualSpaceInFront(binPacking, point, rs);
44      LimitResidualSpaceAbove(binPacking, point, rs);
45      LimitResidualSpaceOnRight(binPacking, point, rs);
46      return rs;
47    }
48
49    private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
50      ResidualSpace rs = new ResidualSpace(binPacking, point);
51
52      LimitResidualSpaceAbove(binPacking, point, rs);
53      LimitResidualSpaceOnRight(binPacking, point, rs);
54      LimitResidualSpaceInFront(binPacking, point, rs);
55      return rs;
56    }
57   
58    private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
59      if (point.X > position.X && point.X >= position.X + item.Width) {
60        return false;
61      }
62
63      if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
64        return false;
65      }
66      return true;
67    }
68   
69    private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
70      if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
71        return false;
72      }
73
74      if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
75        return false;
76      }
77      return true;
78    }
79
80    private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
81      if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
82        return false;
83      }
84
85      if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
86        return false;
87      }
88      return true;
89    }
90
91    private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
92      if (point.X >= position.X) {
93        return false;
94      }
95      var y = OverlapsY(point, residualSpace, position, item);
96      var z = OverlapsZ(point, residualSpace, position, item);
97      return y && z;
98    }
99
100    private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
101      if (point.Z >= position.Z) {
102        return false;
103      }
104      var x = OverlapsX(point, residualSpace, position, item);
105      var y = OverlapsY(point, residualSpace, position, item);
106
107      return x && y;
108    }
109
110    private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
111      if (point.Y >= position.Y) {
112        return false;
113      }
114      var x = OverlapsX(point, residualSpace, position, item);
115      var z = OverlapsZ(point, residualSpace, position, item);
116
117      return x && z;
118    }
119   
120    private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
121      if (residualSpace.IsZero()) {
122        return;
123      }
124     
125      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
126                                  .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
127      if (items.Count() > 0) {
128        foreach (var item in items) {
129          int newWidth = item.Position.X - point.X;
130          if (newWidth <= 0) {
131            residualSpace.SetZero();
132            return;
133          } else if (residualSpace.Width > newWidth) {
134            residualSpace.Width = newWidth;
135          }
136        }
137      }     
138    }
139
140    private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
141      if (residualSpace.IsZero()) {
142        return;
143      }
144
145      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
146                                  .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
147      if (items.Count() > 0) {
148        foreach (var item in items) {
149          int newDepth = item.Position.Z - point.Z;
150          if (newDepth <= 0) {
151            residualSpace.SetZero();
152            return;
153          } else if (residualSpace.Depth > newDepth) {
154            residualSpace.Depth = newDepth;
155          }
156        }
157      }
158    }
159
160    private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
161      if (residualSpace.IsZero()) {
162        return;
163      }
164
165      var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
166                                  .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
167      if (items.Count() > 0) {
168        foreach (var item in items) {
169          int newHeight = item.Position.Y - point.Y;
170          if (newHeight <= 0) {
171            residualSpace.SetZero();
172            return;
173          } else if (residualSpace.Height > newHeight) {
174            residualSpace.Height = newHeight;
175          }
176        }
177      }
178    }
179  }
180}
Note: See TracBrowser for help on using the repository browser.