Changeset 15308


Ignore:
Timestamp:
08/06/17 23:04:05 (2 months ago)
Author:
abeham
Message:

#2817:

  • fixed remaining bugs
File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15307 r15308  
    6565
    6666    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
     67      // base call is deliberately omitted, because UpdateResidualSpace needs to be fitted in before
     68      // generating new extreme points
     69      Items[itemID] = item;
     70      Positions[itemID] = position;
    6771      ExtremePoints.Remove(position);
    6872      ResidualSpace.Remove(position);
    6973      UpdateResidualSpace(item, position);
    70       base.PackItem(itemID, item, position);
     74      GenerateNewExtremePointsForNewItem(item, position);
     75      // if an item is fit in below, before, or left of another its extreme points have to be regenerated
     76      foreach (var above in GetItemsAbove(position))
     77        GenerateNewExtremePointsForNewItem(above.Item2, above.Item1);
     78      foreach (var front in GetItemsInfront(position))
     79        GenerateNewExtremePointsForNewItem(front.Item2, front.Item1);
     80      foreach (var right in GetItemsOnRight(position))
     81        GenerateNewExtremePointsForNewItem(right.Item2, right.Item1);
     82      AddNewItemToOccupationLayers(itemID, item, position);
    7183    }
    7284
     
    8294        var below = ProjectDown(sourcePoint);
    8395        var residualSpace = CalculateResidualSpace(below);
    84         if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
     96        if (IsNonZero(residualSpace)
     97          && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    8598          // add only if the projected point's residual space is not a sub-space
    8699          // of another extreme point's residual space
     
    91104        var back = ProjectBackward(sourcePoint);
    92105        residualSpace = CalculateResidualSpace(back);
    93         if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
     106        if (IsNonZero(residualSpace)
     107          && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
    94108          // add only if the projected point's residual space is not a sub-space
    95109          // of another extreme point's residual space
     
    105119        var left = ProjectLeft(sourcePoint);
    106120        var residualSpace = CalculateResidualSpace(left);
    107         if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
     121        if (IsNonZero(residualSpace)
     122          && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    108123          // add only if the projected point's residual space is not a sub-space
    109124          // of another extreme point's residual space
     
    114129        var back = ProjectBackward(sourcePoint);
    115130        residualSpace = CalculateResidualSpace(back);
    116         if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
     131        if (IsNonZero(residualSpace)
     132          && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
    117133          // add only if the projected point's residual space is not a sub-space
    118134          // of another extreme point's residual space
     
    128144        var below = ProjectDown(sourcePoint);
    129145        var residualSpace = CalculateResidualSpace(below);
    130         if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
     146        if (IsNonZero(residualSpace)
     147          && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    131148          // add only if the projected point's residual space is not a sub-space
    132149          // of another extreme point's residual space
     
    137154        var left = ProjectLeft(sourcePoint);
    138155        residualSpace = CalculateResidualSpace(left);
    139         if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
     156        if (IsNonZero(residualSpace)
     157          && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    140158          // add only if the projected point's residual space is not a sub-space
    141159          // of another extreme point's residual space
     
    146164    }
    147165
     166    private bool IsNonZero(Tuple<int, int, int> rs) {
     167      return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0;
     168    }
     169
    148170    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    149       var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x]));
     171      var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));
    150172      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
    151173    }
     
    158180    private bool AddExtremePoint(PackingPosition pos) {
    159181      if (ExtremePoints.Add(pos)) {
    160         var rs = Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
     182        var rs = CalculateResidualSpace(new Vector3D(pos));
    161183        ResidualSpace.Add(pos, rs);
    162184        // Check if existing extreme points are shadowed by the new point
     
    239261                  .Where(x => x != null && x.Y >= pos.Y)
    240262                  .MinItems(x => x.Y).First();
     263    }
     264
     265    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
     266      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     267      return Items.Select(x => new {
     268        Item = x.Value,
     269        Position = Positions[x.Key],
     270        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Bottom))
     271      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     272        .Select(x => Tuple.Create(x.Position, x.Item));
     273    }
     274
     275    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(PackingPosition pos) {
     276      var line = new Line3D(pos, new Vector3D(0, 0, 1));
     277      return Items.Select(x => new {
     278        Item = x.Value,
     279        Position = Positions[x.Key],
     280        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Back))
     281      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     282        .Select(x => Tuple.Create(x.Position, x.Item));
     283    }
     284
     285    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(PackingPosition pos) {
     286      var line = new Line3D(pos, new Vector3D(1, 0, 0));
     287      return Items.Select(x => new {
     288        Item = x.Value,
     289        Position = Positions[x.Key],
     290        Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Left))
     291      }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
     292        .Select(x => Tuple.Create(x.Position, x.Item));
    241293    }
    242294
     
    429481   
    430482    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    431       foreach (var ep in ExtremePoints) {
     483      foreach (var ep in ExtremePoints.ToList()) {
    432484        var rs = ResidualSpace[ep];
    433485        var depth = pos.Rotated ? item.Width : item.Depth;
    434486        var width = pos.Rotated ? item.Depth : item.Width;
     487        var changed = false;
    435488        if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
    436489          if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
    437490            var diff = pos.X - ep.X;
    438491            var newRSX = Math.Min(rs.Item1, diff);
    439             ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3);
     492            rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
     493            changed = true;
    440494          }
    441495          if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
    442496            var diff = pos.Y - ep.Y;
    443497            var newRSY = Math.Min(rs.Item2, diff);
    444             ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3);
     498            rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
     499            changed = true;
    445500          }
    446501        }
    447502        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);
     503            ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
     504            ep.X >= pos.X && ep.X < pos.X + width) {
     505          var diff = pos.Z - ep.Z;
     506          var newRSZ = Math.Min(rs.Item3, diff);
     507          rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
     508          changed = true;
     509        }
     510        if (changed) {
     511          if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {
     512            ResidualSpace[ep] = rs;
     513          } else {
     514            ExtremePoints.Remove(ep);
     515            ResidualSpace.Remove(ep);
     516          }
    453517        }
    454518      }
     
    544608        return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
    545609      }
     610
     611      public override bool Equals(object obj) {
     612        var packPos = obj as PackingPosition;
     613        if (packPos != null) {
     614          return X == packPos.X && Y == packPos.Y && Z == packPos.Z;
     615        }
     616        var vec = obj as Vector3D;
     617        if (vec != null) {
     618          return X == vec.X && Y == vec.Y && Z == vec.Z;
     619        }
     620        return false;
     621      }
    546622    }
    547623
     
    553629      public Line3D(Vector3D point, Vector3D direction) {
    554630        Point = point;
     631        Direction = direction;
     632      }
     633      public Line3D(PackingPosition position, Vector3D direction) {
     634        Point = new Vector3D(position);
    555635        Direction = direction;
    556636      }
Note: See TracChangeset for help on using the changeset viewer.