[14162] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[15584] | 3 | * Copyright (C) 2002-2018 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[14162] | 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 |
|
---|
[15278] | 22 | using System;
|
---|
[14162] | 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
| 25 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
| 26 | using HeuristicLab.Core;
|
---|
| 27 | using HeuristicLab.Common;
|
---|
| 28 | using HeuristicLab.Problems.BinPacking;
|
---|
| 29 |
|
---|
| 30 | namespace HeuristicLab.Problems.BinPacking3D {
|
---|
| 31 | [Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
|
---|
| 32 | [StorableClass]
|
---|
| 33 | public class BinPacking3D : BinPacking<PackingPosition, PackingShape, PackingItem> {
|
---|
| 34 |
|
---|
[15278] | 35 | [Storable]
|
---|
| 36 | public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; }
|
---|
| 37 |
|
---|
[14162] | 38 | public BinPacking3D(PackingShape binShape)
|
---|
| 39 | : base(binShape) {
|
---|
[15278] | 40 | ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
|
---|
| 41 | AddExtremePoint(binShape.Origin);
|
---|
[14162] | 42 | InitializeOccupationLayers();
|
---|
| 43 | }
|
---|
| 44 | [StorableConstructor]
|
---|
| 45 | protected BinPacking3D(bool deserializing) : base(deserializing) { }
|
---|
| 46 | protected BinPacking3D(BinPacking3D original, Cloner cloner)
|
---|
| 47 | : base(original, cloner) {
|
---|
[15278] | 48 | this.ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
|
---|
| 49 | foreach (var o in original.ResidualSpace)
|
---|
| 50 | this.ResidualSpace.Add(cloner.Clone(o.Key), Tuple.Create(o.Value.Item1, o.Value.Item2, o.Value.Item3));
|
---|
[14162] | 51 | }
|
---|
| 52 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 53 | return new BinPacking3D(this, cloner);
|
---|
| 54 | }
|
---|
| 55 |
|
---|
[15278] | 56 |
|
---|
| 57 | [StorableHook(HookType.AfterDeserialization)]
|
---|
| 58 | private void AfterDeserialization() {
|
---|
| 59 | // BackwardsCompatibility3.3
|
---|
| 60 | #region Backwards compatible code, remove with 3.4
|
---|
| 61 | if (ResidualSpace == null)
|
---|
| 62 | ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>();
|
---|
| 63 | #endregion
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
|
---|
[15392] | 67 | // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
|
---|
| 68 | Items[itemID] = item;
|
---|
| 69 | Positions[itemID] = position;
|
---|
| 70 | ExtremePoints.Remove(position);
|
---|
[15278] | 71 | ResidualSpace.Remove(position);
|
---|
[15392] | 72 | UpdateResidualSpace(item, position);
|
---|
| 73 | foreach (int id in Items.Select(x => x.Key))
|
---|
| 74 | GenerateNewExtremePointsForNewItem(Items[id], Positions[id]);
|
---|
| 75 |
|
---|
| 76 | AddNewItemToOccupationLayers(itemID, item, position);
|
---|
[15278] | 77 | }
|
---|
| 78 |
|
---|
[14162] | 79 | protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
|
---|
| 80 | int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
|
---|
| 81 | int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
|
---|
| 82 |
|
---|
| 83 | //Find ExtremePoints beginning from sourcepointX
|
---|
| 84 | var sourcePointX = new PackingPosition(0, position.X + newWidth, position.Y, position.Z);
|
---|
| 85 | if (sourcePointX.X < BinShape.Width && sourcePointX.Y < BinShape.Height && sourcePointX.Z < BinShape.Depth) {
|
---|
| 86 | //Traversing down the y-axis
|
---|
| 87 | PackingPosition current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
|
---|
| 88 | while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
|
---|
| 89 | current = PackingPosition.MoveDown(current);
|
---|
| 90 | }
|
---|
[15278] | 91 | AddExtremePoint((PackingPosition)current.Clone());
|
---|
[14162] | 92 | while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
|
---|
| 93 | current = PackingPosition.MoveLeft(current);
|
---|
| 94 | }
|
---|
[15278] | 95 | AddExtremePoint(current);
|
---|
[14162] | 96 |
|
---|
| 97 | //Traversing down the z-axis
|
---|
| 98 | current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
|
---|
| 99 | while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
|
---|
| 100 | current = PackingPosition.MoveBack(current);
|
---|
| 101 | }
|
---|
[15278] | 102 | AddExtremePoint((PackingPosition)current.Clone());
|
---|
[14162] | 103 | while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
|
---|
| 104 | current = PackingPosition.MoveDown(current);
|
---|
| 105 | }
|
---|
[15278] | 106 | AddExtremePoint(current);
|
---|
[14162] | 107 | }
|
---|
| 108 |
|
---|
| 109 | //Find ExtremePoints beginning from sourcepointY
|
---|
| 110 | var sourcePointY = new PackingPosition(0, position.X, position.Y + newItem.Height, position.Z);
|
---|
| 111 | if (sourcePointY.X < BinShape.Width && sourcePointY.Y < BinShape.Height && sourcePointY.Z < BinShape.Depth) {
|
---|
| 112 | //Traversing down the x-axis
|
---|
| 113 | PackingPosition current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
|
---|
| 114 | while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
|
---|
| 115 | current = PackingPosition.MoveLeft(current);
|
---|
| 116 | }
|
---|
[15278] | 117 | AddExtremePoint((PackingPosition)current.Clone());
|
---|
[14162] | 118 | while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
|
---|
| 119 | current = PackingPosition.MoveDown(current);
|
---|
| 120 | }
|
---|
[15278] | 121 | AddExtremePoint(current);
|
---|
[14162] | 122 |
|
---|
| 123 | //Traversing down the z-axis
|
---|
| 124 | current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
|
---|
| 125 | while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
|
---|
| 126 | current = PackingPosition.MoveBack(current);
|
---|
| 127 | }
|
---|
[15278] | 128 | AddExtremePoint((PackingPosition)current.Clone());
|
---|
[14162] | 129 | while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
|
---|
| 130 | current = PackingPosition.MoveDown(current);
|
---|
| 131 | }
|
---|
[15278] | 132 | AddExtremePoint(current);
|
---|
[14162] | 133 | }
|
---|
| 134 |
|
---|
| 135 | //Find ExtremePoints beginning from sourcepointZ
|
---|
| 136 | var sourcePointZ = new PackingPosition(0, position.X, position.Y, position.Z + newDepth);
|
---|
| 137 | if (sourcePointZ.X < BinShape.Width && sourcePointZ.Y < BinShape.Height && sourcePointZ.Z < BinShape.Depth) {
|
---|
| 138 | //Traversing down the x-axis
|
---|
| 139 | PackingPosition current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
|
---|
| 140 | while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
|
---|
| 141 | current = PackingPosition.MoveLeft(current);
|
---|
| 142 | }
|
---|
[15278] | 143 | AddExtremePoint((PackingPosition)current.Clone());
|
---|
[14162] | 144 | while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
|
---|
| 145 | current = PackingPosition.MoveDown(current);
|
---|
| 146 | }
|
---|
[15278] | 147 | AddExtremePoint(current);
|
---|
[14162] | 148 |
|
---|
| 149 | //Traversing down the y-axis
|
---|
| 150 | current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
|
---|
| 151 | while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
|
---|
| 152 | current = PackingPosition.MoveDown(current);
|
---|
| 153 | }
|
---|
[15278] | 154 | AddExtremePoint((PackingPosition)current.Clone());
|
---|
[14162] | 155 | while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
|
---|
| 156 | current = PackingPosition.MoveLeft(current);
|
---|
| 157 | }
|
---|
[15278] | 158 | AddExtremePoint(current);
|
---|
[14162] | 159 | }
|
---|
| 160 | }
|
---|
| 161 |
|
---|
[15278] | 162 | private void AddExtremePoint(PackingPosition current) {
|
---|
| 163 | if (ExtremePoints.Add(current)) {
|
---|
| 164 | var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z);
|
---|
| 165 | ResidualSpace.Add(current, tuple);
|
---|
| 166 | }
|
---|
| 167 | }
|
---|
| 168 |
|
---|
[14162] | 169 | public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
|
---|
| 170 | PackingItem newItem = new PackingItem(
|
---|
| 171 | rotated ? item.Depth : item.Width,
|
---|
| 172 | item.Height,
|
---|
| 173 | rotated ? item.Width : item.Depth,
|
---|
[14966] | 174 | item.TargetBin, item.Weight, item.Material);
|
---|
[14162] | 175 |
|
---|
[15278] | 176 | var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)).FirstOrDefault();
|
---|
| 177 | if (ep != null) {
|
---|
| 178 | var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated);
|
---|
[14162] | 179 | return result;
|
---|
| 180 | }
|
---|
| 181 | return null;
|
---|
| 182 | }
|
---|
| 183 |
|
---|
[15278] | 184 | public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
|
---|
| 185 | var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
|
---|
| 186 | return feasible
|
---|
| 187 | && IsSupportedByAtLeastOnePoint(item, position)
|
---|
| 188 | && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
|
---|
| 189 | }
|
---|
| 190 |
|
---|
| 191 | public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
|
---|
[14162] | 192 | //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
|
---|
| 193 | PackingPosition currentPosition = new PackingPosition(0,
|
---|
| 194 | BinShape.Width - (rotated ? item.Depth : item.Width),
|
---|
| 195 | BinShape.Height - item.Height,
|
---|
| 196 | BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
|
---|
| 197 | //Slide the item as far as possible to the bottom
|
---|
[15278] | 198 | while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
|
---|
| 199 | || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
|
---|
| 200 | || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
|
---|
[14162] | 201 | //Slide the item as far as possible to the left
|
---|
[15278] | 202 | while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
|
---|
| 203 | || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
|
---|
[14162] | 204 | //Slide the item as far as possible to the back
|
---|
[15278] | 205 | while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
|
---|
[14162] | 206 | currentPosition = PackingPosition.MoveBack(currentPosition);
|
---|
| 207 | }
|
---|
[15278] | 208 | if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
|
---|
[14162] | 209 | currentPosition = PackingPosition.MoveLeft(currentPosition);
|
---|
| 210 | }
|
---|
[15278] | 211 | if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
|
---|
[14162] | 212 | currentPosition = PackingPosition.MoveDown(currentPosition);
|
---|
| 213 | }
|
---|
| 214 |
|
---|
[15278] | 215 | return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
|
---|
[14162] | 216 | }
|
---|
| 217 |
|
---|
[15278] | 218 | public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
|
---|
[14162] | 219 | var temp = new List<int>(sequence);
|
---|
| 220 | for (int i = 0; i < temp.Count; i++) {
|
---|
| 221 | var item = items[temp[i]];
|
---|
[15278] | 222 | var position = FindPositionBySliding(item, false, stackingConstraints);
|
---|
[14162] | 223 | if (position != null) {
|
---|
| 224 | PackItem(temp[i], item, position);
|
---|
| 225 | sequence.Remove(temp[i]);
|
---|
| 226 | }
|
---|
| 227 | }
|
---|
| 228 | }
|
---|
[15278] | 229 | public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
|
---|
[14162] | 230 | var temp = new List<int>(sequence);
|
---|
| 231 | for (int i = 0; i < temp.Count; i++) {
|
---|
| 232 | var item = items[temp[i]];
|
---|
[15278] | 233 | var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
|
---|
[14162] | 234 | if (position != null) {
|
---|
| 235 | PackItem(temp[i], item, position);
|
---|
| 236 | sequence.Remove(temp[i]);
|
---|
| 237 | }
|
---|
| 238 | }
|
---|
| 239 | }
|
---|
| 240 | public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
|
---|
| 241 | var temp = new List<int>(sequence);
|
---|
| 242 | foreach (int itemID in temp) {
|
---|
| 243 | var item = items[itemID];
|
---|
| 244 | var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
|
---|
| 245 | if (positionFound != null) {
|
---|
| 246 | PackItem(itemID, item, positionFound);
|
---|
| 247 | sequence.Remove(itemID);
|
---|
| 248 | }
|
---|
| 249 | }
|
---|
| 250 | }
|
---|
| 251 | public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
|
---|
| 252 | var temp = new List<int>(sequence);
|
---|
| 253 | foreach (int itemID in temp) {
|
---|
| 254 | var item = items[itemID];
|
---|
| 255 | var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
|
---|
| 256 | if (positionFound != null) {
|
---|
| 257 | PackItem(itemID, item, positionFound);
|
---|
| 258 | sequence.Remove(itemID);
|
---|
| 259 | }
|
---|
| 260 | }
|
---|
| 261 | }
|
---|
| 262 | public override int ShortestPossibleSideFromPoint(PackingPosition position) {
|
---|
| 263 |
|
---|
| 264 | int shortestSide = int.MaxValue;
|
---|
| 265 | int width = BinShape.Width;
|
---|
| 266 | int height = BinShape.Height;
|
---|
| 267 | int depth = BinShape.Depth;
|
---|
| 268 |
|
---|
| 269 | if (position.X >= width || position.Y >= height || position.Z >= depth)
|
---|
| 270 | return shortestSide;
|
---|
| 271 |
|
---|
| 272 | PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
|
---|
| 273 | while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
|
---|
| 274 | if (current.X - position.X < shortestSide)
|
---|
| 275 | shortestSide = current.X - position.X;
|
---|
| 276 |
|
---|
| 277 |
|
---|
| 278 | current = new PackingPosition(0, position.X, position.Y, position.Z);
|
---|
| 279 | while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
|
---|
| 280 | if (current.Y - position.Y < shortestSide)
|
---|
| 281 | shortestSide = current.Y - position.Y;
|
---|
| 282 |
|
---|
| 283 |
|
---|
| 284 | current = new PackingPosition(0, position.X, position.Y, position.Z);
|
---|
| 285 | while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
|
---|
| 286 | if (current.Z - position.Z < shortestSide)
|
---|
| 287 | shortestSide = current.Z - position.Z;
|
---|
| 288 |
|
---|
| 289 | return shortestSide;
|
---|
| 290 | }
|
---|
| 291 | public override bool IsStaticStable(PackingItem item, PackingPosition position) {
|
---|
| 292 | //Static stability is given, if item is placed on the ground
|
---|
| 293 | if (position.Y == 0)
|
---|
| 294 | return true;
|
---|
| 295 |
|
---|
| 296 | if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
|
---|
| 297 | && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
|
---|
| 298 | && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
|
---|
| 299 | && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
|
---|
| 300 | return true;
|
---|
| 301 |
|
---|
| 302 | return false;
|
---|
| 303 | }
|
---|
| 304 |
|
---|
| 305 |
|
---|
| 306 | public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
|
---|
| 307 | if (position.Y == 0)
|
---|
| 308 | return true;
|
---|
| 309 |
|
---|
| 310 | int y = position.Y - 1;
|
---|
| 311 | for (int x = position.X; x < position.X + item.Width; x++)
|
---|
| 312 | for (int z = position.Z; z < position.Z + item.Depth; z++)
|
---|
| 313 | if (IsPointOccupied(new PackingPosition(0, x, y, z)))
|
---|
| 314 | return true;
|
---|
| 315 |
|
---|
| 316 | return false;
|
---|
| 317 | }
|
---|
| 318 | public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
|
---|
| 319 | if (ep.Y == 0)
|
---|
| 320 | return true;
|
---|
| 321 |
|
---|
| 322 | if (Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
|
---|
| 323 | && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
|
---|
| 324 | && Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
|
---|
| 325 | && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
|
---|
| 326 | return true;
|
---|
| 327 |
|
---|
| 328 | return false;
|
---|
| 329 | }
|
---|
| 330 |
|
---|
| 331 | protected override void InitializeOccupationLayers() {
|
---|
| 332 | for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
|
---|
| 333 | OccupationLayers[i] = new List<int>();
|
---|
| 334 | }
|
---|
| 335 | }
|
---|
| 336 | protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
|
---|
| 337 | int z1 = position.Z / 10;
|
---|
| 338 | int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
|
---|
| 339 |
|
---|
| 340 | for (int i = z1; i <= z2; i++)
|
---|
| 341 | OccupationLayers[i].Add(itemID);
|
---|
| 342 | }
|
---|
| 343 | protected override List<int> GetLayerItemIDs(PackingPosition position) {
|
---|
| 344 | return OccupationLayers[position.Z / 10];
|
---|
| 345 | }
|
---|
| 346 | protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
|
---|
| 347 | List<int> result = new List<int>();
|
---|
| 348 | int z1 = position.Z / 10;
|
---|
| 349 | int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
|
---|
| 350 |
|
---|
| 351 | for (int i = z1; i <= z2; i++)
|
---|
| 352 | result.AddRange(OccupationLayers[i]);
|
---|
| 353 | return result;
|
---|
| 354 | }
|
---|
[15278] | 355 |
|
---|
| 356 | public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
|
---|
| 357 | foreach (var ep in ExtremePoints) {
|
---|
[15392] | 358 | var rs = ResidualSpace[ep];
|
---|
| 359 | var depth = pos.Rotated ? item.Width : item.Depth;
|
---|
| 360 | var width = pos.Rotated ? item.Depth : item.Width;
|
---|
| 361 | if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
|
---|
| 362 | if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
|
---|
[15278] | 363 | var diff = pos.X - ep.X;
|
---|
[15392] | 364 | var newRSX = Math.Min(rs.Item1, diff);
|
---|
| 365 | ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3);
|
---|
[15278] | 366 | }
|
---|
[15392] | 367 | if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
|
---|
[15278] | 368 | var diff = pos.Y - ep.Y;
|
---|
[15392] | 369 | var newRSY = Math.Min(rs.Item2, diff);
|
---|
| 370 | ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3);
|
---|
[15278] | 371 | }
|
---|
| 372 | }
|
---|
[15392] | 373 | if (ep.Z <= pos.Z &&
|
---|
| 374 | ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
|
---|
| 375 | ep.X >= pos.X && ep.X < pos.X + width) {
|
---|
| 376 | var diff = pos.Z - ep.Z;
|
---|
| 377 | var newRSZ = Math.Min(rs.Item3, diff);
|
---|
| 378 | ResidualSpace[ep] = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
|
---|
[15278] | 379 | }
|
---|
| 380 | }
|
---|
| 381 | }
|
---|
[14162] | 382 | }
|
---|
[15278] | 383 | } |
---|