Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs @ 15307

Last change on this file since 15307 was 15307, checked in by abeham, 7 years ago

#2817:

  • Added checkbox to control showing extreme points in visualization
    • Automatically determine size of extreme point cubes
  • Fixed some bugs in extreme point generation
File size: 30.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Joseph Helm and 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 HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
26using HeuristicLab.Core;
27using HeuristicLab.Common;
28using HeuristicLab.Problems.BinPacking;
29
30namespace 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
35    [Storable]
36    public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; }
37
38    public BinPacking3D(PackingShape binShape)
39      : base(binShape) {
40      ResidualSpace = new Dictionary<PackingPosition, Tuple<int,int,int>>();
41      AddExtremePoint(binShape.Origin);
42      InitializeOccupationLayers();
43    }
44    [StorableConstructor]
45    protected BinPacking3D(bool deserializing) : base(deserializing) { }
46    protected BinPacking3D(BinPacking3D original, Cloner cloner)
47      : base(original, cloner) {
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));
51    }
52    public override IDeepCloneable Clone(Cloner cloner) {
53      return new BinPacking3D(this, cloner);
54    }
55
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) {
67      ExtremePoints.Remove(position);
68      ResidualSpace.Remove(position);
69      UpdateResidualSpace(item, position);
70      base.PackItem(itemID, item, position);
71    }
72
73    protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
74      int newWidth = position.Rotated ? newItem.Depth : newItem.Width;
75      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
76
77      var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList();
78      // Find ExtremePoints beginning from sourcepointX
79      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
80      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
81        // Projecting onto the XZ-plane
82        var below = ProjectDown(sourcePoint);
83        var residualSpace = CalculateResidualSpace(below);
84        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
85          // add only if the projected point's residual space is not a sub-space
86          // of another extreme point's residual space
87          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
88          AddExtremePoint(belowPoint);
89        }
90        // Projecting onto the XY-plane
91        var back = ProjectBackward(sourcePoint);
92        residualSpace = CalculateResidualSpace(back);
93        if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
94          // add only if the projected point's residual space is not a sub-space
95          // of another extreme point's residual space
96          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
97          AddExtremePoint(backPoint);
98        }
99      }
100
101      //Find ExtremePoints beginning from sourcepointY
102      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
103      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
104        // Projecting onto the YZ-plane
105        var left = ProjectLeft(sourcePoint);
106        var residualSpace = CalculateResidualSpace(left);
107        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
108          // add only if the projected point's residual space is not a sub-space
109          // of another extreme point's residual space
110          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
111          AddExtremePoint(leftPoint);
112        }
113        // Projecting onto the XY-plane
114        var back = ProjectBackward(sourcePoint);
115        residualSpace = CalculateResidualSpace(back);
116        if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
117          // add only if the projected point's residual space is not a sub-space
118          // of another extreme point's residual space
119          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
120          AddExtremePoint(backPoint);
121        }
122      }
123
124      //Find ExtremePoints beginning from sourcepointZ
125      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
126      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
127        // Projecting onto the XZ-plane
128        var below = ProjectDown(sourcePoint);
129        var residualSpace = CalculateResidualSpace(below);
130        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
131          // add only if the projected point's residual space is not a sub-space
132          // of another extreme point's residual space
133          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
134          AddExtremePoint(belowPoint);
135        }
136        // Projecting onto the YZ-plane
137        var left = ProjectLeft(sourcePoint);
138        residualSpace = CalculateResidualSpace(left);
139        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
140          // add only if the projected point's residual space is not a sub-space
141          // of another extreme point's residual space
142          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
143          AddExtremePoint(leftPoint);
144        }
145      }
146    }
147
148    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
149      var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x]));
150      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
151    }
152    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
153      return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
154          && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
155          && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
156    }
157
158    private bool AddExtremePoint(PackingPosition pos) {
159      if (ExtremePoints.Add(pos)) {
160        var rs = Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
161        ResidualSpace.Add(pos, rs);
162        // Check if existing extreme points are shadowed by the new point
163        // That is, their residual space fit entirely into the residual space of the new point
164        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
165          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
166            ExtremePoints.Remove(ep);
167            ResidualSpace.Remove(ep);
168          }
169        }
170        return true;
171      }
172      return false;
173    }
174
175    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
176      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
177      var rightLimit = ProjectRight(pos);
178      var upLimit = ProjectUp(pos);
179      var forwardLimit = ProjectForward(pos);
180      return Tuple.Create(rightLimit.X - pos.X, upLimit.Y - pos.Y, forwardLimit.Z - pos.Z);
181    }
182
183    private Vector3D ProjectBackward(Vector3D pos) {
184      var line = new Line3D(pos, new Vector3D(0, 0, -1));
185      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
186                  .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
187                  .Concat(new[] { new Plane3D(BinShape, Side.Back) })
188                  .Select(x => x.Intersect(line))
189                  .Where(x => x != null && x.Z <= pos.Z)
190                  .MaxItems(x => x.Z).First();
191    }
192
193    private Vector3D ProjectLeft(Vector3D pos) {
194      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
195      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
196                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
197                  .Concat(new[] { new Plane3D(BinShape, Side.Left) })
198                  .Select(x => x.Intersect(line))
199                  .Where(x => x != null && x.X <= pos.X)
200                  .MaxItems(x => x.X).First();
201    }
202
203    private Vector3D ProjectDown(Vector3D pos) {
204      var line = new Line3D(pos, new Vector3D(0, -1, 0));
205      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
206                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
207                  .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })
208                  .Select(x => x.Intersect(line))
209                  .Where(x => x != null && x.Y <= pos.Y)
210                  .MaxItems(x => x.Y).First();
211    }
212
213    private Vector3D ProjectForward(Vector3D pos) {
214      var line = new Line3D(pos, new Vector3D(0, 0, 1));
215      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
216                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
217                  .Concat(new[] { new Plane3D(BinShape, Side.Front) })
218                  .Select(x => x.Intersect(line))
219                  .Where(x => x != null && x.Z >= pos.Z)
220                  .MinItems(x => x.Z).First();
221    }
222
223    private Vector3D ProjectRight(Vector3D pos) {
224      var line = new Line3D(pos, new Vector3D(1, 0, 0));
225      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
226                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
227                  .Concat(new[] { new Plane3D(BinShape, Side.Right) })
228                  .Select(x => x.Intersect(line))
229                  .Where(x => x != null && x.X >= pos.X)
230                  .MinItems(x => x.X).First();
231    }
232
233    private Vector3D ProjectUp(Vector3D pos) {
234      var line = new Line3D(pos, new Vector3D(0, 1, 0));
235      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
236                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
237                  .Concat(new[] { new Plane3D(BinShape, Side.Top) })
238                  .Select(x => x.Intersect(line))
239                  .Where(x => x != null && x.Y >= pos.Y)
240                  .MinItems(x => x.Y).First();
241    }
242
243    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
244      PackingItem newItem = new PackingItem(
245        rotated ? item.Depth : item.Width,
246        item.Height,
247        rotated ? item.Width : item.Depth,
248        item.TargetBin, item.Weight, item.Material);
249
250      var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints))
251                            .FirstOrDefault();
252      if (ep != null) {
253        var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated);
254        return result;
255      }
256      return null;
257    }
258
259    public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
260      var feasible = base.IsPositionFeasible(item, position, stackingConstraints);
261      return feasible
262        && IsSupportedByAtLeastOnePoint(item, position)
263        && (!stackingConstraints || (IsStaticStable(item, position) && IsWeightSupported(item, position)));
264    }
265
266    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
267      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
268      PackingPosition currentPosition = new PackingPosition(0,
269        BinShape.Width - (rotated ? item.Depth : item.Width),
270        BinShape.Height - item.Height,
271        BinShape.Depth - (rotated ? item.Width : item.Depth), rotated);
272      //Slide the item as far as possible to the bottom
273      while (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints)
274        || IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
275        || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
276        //Slide the item as far as possible to the left
277        while (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints)
278      || IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
279          //Slide the item as far as possible to the back
280          while (IsPositionFeasible(item, PackingPosition.MoveBack(currentPosition), stackingConstraints)) {
281            currentPosition = PackingPosition.MoveBack(currentPosition);
282          }
283          if (IsPositionFeasible(item, PackingPosition.MoveLeft(currentPosition), stackingConstraints))
284            currentPosition = PackingPosition.MoveLeft(currentPosition);
285        }
286        if (IsPositionFeasible(item, PackingPosition.MoveDown(currentPosition), stackingConstraints))
287          currentPosition = PackingPosition.MoveDown(currentPosition);
288      }
289
290      return IsPositionFeasible(item, currentPosition, stackingConstraints) ? currentPosition : null;
291    }
292
293    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
294      var temp = new List<int>(sequence);
295      for (int i = 0; i < temp.Count; i++) {
296        var item = items[temp[i]];
297        var position = FindPositionBySliding(item, false, stackingConstraints);
298        if (position != null) {
299          PackItem(temp[i], item, position);
300          sequence.Remove(temp[i]);
301        }
302      }
303    }
304    public override void SlidingBasedPacking(ref IList<int> sequence, IList<PackingItem> items, Dictionary<int, bool> rotationArray, bool stackingConstraints) {
305      var temp = new List<int>(sequence);
306      for (int i = 0; i < temp.Count; i++) {
307        var item = items[temp[i]];
308        var position = FindPositionBySliding(item, rotationArray[i], stackingConstraints);
309        if (position != null) {
310          PackItem(temp[i], item, position);
311          sequence.Remove(temp[i]);
312        }
313      }
314    }
315    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
316      var temp = new List<int>(sequence);
317      foreach (int itemID in temp) {
318        var item = items[itemID];
319        var positionFound = FindExtremePointForItem(item, false, stackingConstraints);
320        if (positionFound != null) {
321          PackItem(itemID, item, positionFound);
322          sequence.Remove(itemID);
323        }
324      }
325    }
326    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints, Dictionary<int, bool> rotationArray) {
327      var temp = new List<int>(sequence);
328      foreach (int itemID in temp) {
329        var item = items[itemID];
330        var positionFound = FindExtremePointForItem(item, rotationArray[itemID], stackingConstraints);
331        if (positionFound != null) {
332          PackItem(itemID, item, positionFound);
333          sequence.Remove(itemID);
334        }
335      }
336    }
337    public override int ShortestPossibleSideFromPoint(PackingPosition position) {
338
339      int shortestSide = int.MaxValue;
340      int width = BinShape.Width;
341      int height = BinShape.Height;
342      int depth = BinShape.Depth;
343
344      if (position.X >= width || position.Y >= height || position.Z >= depth)
345        return shortestSide;
346
347      PackingPosition current = new PackingPosition(0, position.X, position.Y, position.Z);
348      while (current.X < width && IsPointOccupied(current)) { current = PackingPosition.MoveRight(current); }
349      if (current.X - position.X < shortestSide)
350        shortestSide = current.X - position.X;
351
352
353      current = new PackingPosition(0, position.X, position.Y, position.Z);
354      while (current.Y < height && IsPointOccupied(current)) { current = PackingPosition.MoveUp(current); }
355      if (current.Y - position.Y < shortestSide)
356        shortestSide = current.Y - position.Y;
357
358
359      current = new PackingPosition(0, position.X, position.Y, position.Z);
360      while (current.Z < depth && IsPointOccupied(current)) { current = PackingPosition.MoveFront(current); }
361      if (current.Z - position.Z < shortestSide)
362        shortestSide = current.Z - position.Z;
363
364      return shortestSide;
365    }
366    public override bool IsStaticStable(PackingItem item, PackingPosition position) {
367      //Static stability is given, if item is placed on the ground
368      if (position.Y == 0)
369        return true;
370
371      if (IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z))
372        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z))
373        && IsPointOccupied(new PackingPosition(0, position.X, position.Y - 1, position.Z + item.Depth - 1))
374        && IsPointOccupied(new PackingPosition(0, position.X + item.Width - 1, position.Y - 1, position.Z + item.Depth - 1)))
375        return true;
376
377      return false;
378    }
379
380    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
381      if (position.Y == 0)
382        return true;
383
384      int y = position.Y - 1;
385      for (int x = position.X; x < position.X + item.Width; x++)
386        for (int z = position.Z; z < position.Z + item.Depth; z++)
387          if (IsPointOccupied(new PackingPosition(0, x, y, z)))
388            return true;
389
390      return false;
391    }
392    public bool IsWeightSupported(PackingItem item, PackingPosition ep) {
393      if (ep.Y == 0)
394        return true;
395
396      if (Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z))].SupportsStacking(item)
397        && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z))].SupportsStacking(item)
398        && Items[PointOccupation(new PackingPosition(0, ep.X, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item)
399        && Items[PointOccupation(new PackingPosition(0, ep.X + item.Width - 1, ep.Y - 1, ep.Z + item.Depth - 1))].SupportsStacking(item))
400        return true;
401
402      return false;
403    }
404
405    protected override void InitializeOccupationLayers() {
406      for (int i = 0; i * 10 <= BinShape.Depth; i += 1) {
407        OccupationLayers[i] = new List<int>();
408      }
409    }
410    protected override void AddNewItemToOccupationLayers(int itemID, PackingItem item, PackingPosition position) {
411      int z1 = position.Z / 10;
412      int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
413
414      for (int i = z1; i <= z2; i++)
415        OccupationLayers[i].Add(itemID);
416    }
417    protected override List<int> GetLayerItemIDs(PackingPosition position) {
418      return OccupationLayers[position.Z / 10];
419    }
420    protected override List<int> GetLayerItemIDs(PackingItem item, PackingPosition position) {
421      List<int> result = new List<int>();
422      int z1 = position.Z / 10;
423      int z2 = (position.Z + (position.Rotated ? item.Width : item.Depth)) / 10;
424
425      for (int i = z1; i <= z2; i++)
426        result.AddRange(OccupationLayers[i]);
427      return result;
428    }
429   
430    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
431      foreach (var ep in ExtremePoints) {
432        var rs = ResidualSpace[ep];
433        var depth = pos.Rotated ? item.Width : item.Depth;
434        var width = pos.Rotated ? item.Depth : item.Width;
435        if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
436          if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
437            var diff = pos.X - ep.X;
438            var newRSX = Math.Min(rs.Item1, diff);
439            ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3);
440          }
441          if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
442            var diff = pos.Y - ep.Y;
443            var newRSY = Math.Min(rs.Item2, diff);
444            ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3);
445          }
446        }
447        if (ep.Z <= pos.Z &&
448          ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
449          ep.X >= pos.X && ep.X < pos.X + width) {
450            var diff = pos.Z - ep.Z;
451            var newRSZ = Math.Min(rs.Item3, diff);
452            ResidualSpace[ep] = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
453        }
454      }
455      return;
456    }
457
458    #region Helper classes for vector math
459    private class Vector3D {
460      public int X;
461      public int Y;
462      public int Z;
463      public Vector3D() { }
464      public Vector3D(int x, int y, int z) {
465        X = x;
466        Y = y;
467        Z = z;
468      }
469      public Vector3D(PackingPosition pos) {
470        X = pos.X;
471        Y = pos.Y;
472        Z = pos.Z;
473      }
474      public static Vector3D AlongX(Vector3D pos, PackingItem item) {
475        return new Vector3D(
476          pos.X + item.Width,
477          pos.Y,
478          pos.Z
479        );
480      }
481      public static Vector3D AlongY(Vector3D pos, PackingItem item) {
482        return new Vector3D(
483          pos.X,
484          pos.Y + item.Height,
485          pos.Z
486        );
487      }
488      public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
489        return new Vector3D(
490          pos.X,
491          pos.Y,
492          pos.Z + item.Depth
493        );
494      }
495      public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
496        return new Vector3D(
497          pos.X + item.Width,
498          pos.Y,
499          pos.Z
500        );
501      }
502      public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
503        return new Vector3D(
504          pos.X,
505          pos.Y + item.Height,
506          pos.Z
507        );
508      }
509      public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
510        return new Vector3D(
511          pos.X,
512          pos.Y,
513          pos.Z + item.Depth
514        );
515      }
516
517      public Vector3D Cross(Vector3D b) {
518        return new Vector3D(
519          Y * b.Z - Z * b.Y,
520          -X * b.Z + Z * b.X,
521          X * b.Y - Y * b.X
522        );
523      }
524
525      public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
526        return X >= pos.X && X < pos.X + rs.Item1
527          && Y >= pos.Y && Y < pos.Y + rs.Item2
528          && Z >= pos.Z && Z < pos.Z + rs.Item3;
529      }
530
531      public static int operator *(Vector3D a, Vector3D b) {
532        return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
533      }
534      public static Vector3D operator *(int a, Vector3D b) {
535        return new Vector3D(a * b.X, a * b.Y, a * b.Z);
536      }
537      public static Vector3D operator *(Vector3D a, int b) {
538        return new Vector3D(a.X * b, a.Y * b, a.Z * b);
539      }
540      public static Vector3D operator +(Vector3D a, Vector3D b) {
541        return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
542      }
543      public static Vector3D operator -(Vector3D a, Vector3D b) {
544        return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
545      }
546    }
547
548    // A line is given as a point and a directing vector
549    private class Line3D {
550      public Vector3D Point;
551      public Vector3D Direction;
552
553      public Line3D(Vector3D point, Vector3D direction) {
554        Point = point;
555        Direction = direction;
556      }
557
558      public bool Intersects(Plane3D plane) {
559        return plane.Intersects(this);
560      }
561
562      public Vector3D Intersect(Plane3D plane) {
563        return plane.Intersect(this);
564      }
565    }
566
567    private enum Side { Top, Left, Bottom, Right, Front, Back }
568    // A plane is given as a point and two directing vectors
569    private class Plane3D {
570      public Vector3D Point { get; private set; }
571      public Vector3D Direction1 { get; private set; }
572      public Vector3D Direction2 { get; private set; }
573      public Vector3D Normal { get; private set; }
574      private int rhs;
575
576      public Plane3D(PackingShape bin, Side side) {
577        switch (side) {
578          case Side.Top: // ZX plane
579            Point = new Vector3D(0, bin.Height, 0);
580            Direction1 = new Vector3D(0, 0, bin.Depth);
581            Direction2 = new Vector3D(bin.Width, 0, 0);
582            break;
583          case Side.Left: // ZY plane
584            Point = new Vector3D(0, 0, 0);
585            Direction1 = new Vector3D(0, 0, bin.Depth);
586            Direction2 = new Vector3D(0, bin.Height, 0);
587            break;
588          case Side.Bottom: // XZ plane
589            Point = new Vector3D(0, 0, 0);
590            Direction1 = new Vector3D(bin.Width, 0, 0);
591            Direction2 = new Vector3D(0, 0, bin.Depth);
592            break;
593          case Side.Right: // YZ plane
594            Point = new Vector3D(bin.Width, 0, 0);
595            Direction1 = new Vector3D(0, bin.Height, 0);
596            Direction2 = new Vector3D(0, 0, bin.Depth);
597            break;
598          case Side.Front: // XY plane
599            Point = new Vector3D(0, 0, bin.Depth);
600            Direction1 = new Vector3D(bin.Width, 0, 0);
601            Direction2 = new Vector3D(0, bin.Height, 0);
602            break;
603          case Side.Back: // YX plane
604            Point = new Vector3D(0, 0, 0);
605            Direction1 = new Vector3D(0, bin.Height, 0);
606            Direction2 = new Vector3D(bin.Width, 0, 0);
607            break;
608        }
609        Normal = Direction1.Cross(Direction2);
610        rhs = 0;
611      }
612
613      public Plane3D(PackingPosition pos, PackingItem item, Side side) {
614        // the directing vectors are chosen such that normal always points outside the packing item
615        switch (side) {
616          case Side.Top: // ZX plane
617            Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
618            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
619            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
620            break;
621          case Side.Left: // ZY plane
622            Point = new Vector3D(pos.X, pos.Y, pos.Z);
623            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
624            Direction2 = new Vector3D(0, item.Height, 0);
625            break;
626          case Side.Bottom: // XZ plane
627            Point = new Vector3D(pos.X, pos.Y, pos.Z);
628            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
629            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
630            break;
631          case Side.Right: // YZ plane
632            Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
633            Direction1 = new Vector3D(0, item.Height, 0);
634            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
635            break;
636          case Side.Front: // XY plane
637            Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
638            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
639            Direction2 = new Vector3D(0, item.Height, 0);
640            break;
641          case Side.Back: // YX plane
642            Point = new Vector3D(pos.X, pos.Y, pos.Z);
643            Direction1 = new Vector3D(0, item.Height, 0);
644            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
645            break;
646        }
647        Normal = Direction1.Cross(Direction2);
648        rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
649      }
650
651      public bool IsElementOf(Vector3D point) {
652        return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
653      }
654
655      public bool Intersects(Line3D line) {
656        return Intersect(line) != null;
657      }
658
659      public Vector3D Intersect(Line3D line) {
660        var denom = Normal * line.Direction;
661        if (denom == 0) {
662          // dir is perpendicular to the normal vector of the plane
663          // this means they intersect if p1 is element of the plane
664          // also the plane does not stretch infinitely, but is bound
665          // to the parallelogram spanned by the point and the two
666          // directing vectors
667          if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
668            return line.Point;
669          else return null;
670        }
671        var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
672        if (IsWithinDirectionalVectors(intersect)) return intersect;
673        return null;
674      }
675
676      public bool IsWithinDirectionalVectors(Vector3D point) {
677        return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
678            && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
679            && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
680      }
681    }
682    #endregion
683  }
684}
Note: See TracBrowser for help on using the repository browser.