Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/04/17 17:00:16 (7 years ago)
Author:
abeham
Message:

#2817:

  • Drawing extreme points in the visualization (will add a checkbox to the view to enable/disable this)
  • Fixing some bugs:
    • Updating residual space of extreme points before generating new extreme points
    • Fixed calculation of residual space for new extreme points by calculating intersections
    • Fixed bug in UpdateResidualSpace regarding > and >=
Location:
branches/2817-BinPackingSpeedup
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs

    r15167 r15306  
    153153          modelGroup.Children.Add(selectedModel);
    154154        }
     155      }
     156
     157      // draw extreme-points
     158      foreach (var ep in packing.ExtremePoints) {
     159        var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } };
     160        AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, 10, 10, 10);
     161        modelGroup.Children.Add(epModel);
    155162      }
    156163

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

    r15305 r15306  
    6565
    6666    public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
     67      ExtremePoints.Remove(position);
    6768      ResidualSpace.Remove(position);
     69      UpdateResidualSpace(item, position);
    6870      base.PackItem(itemID, item, position);
    6971    }
    … …  
    7880      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    7981        // Projecting onto the XZ-plane
    80         var line = new Line3D(sourcePoint, new Vector3D(0, -1, 0));
    81         var below = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Top))
    82                                  .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })
    83                                  .Select(x => x.Intersect(line))
    84                                  .Where(x => x != null && x.Y <= sourcePoint.Y)
    85                                  .MaxItems(x => x.Y).First();
     82        var below = ProjectDown(sourcePoint);
    8683        var residualSpace = CalculateResidualSpace(below);
    87         var eps = ExtremePoints.Where(x => IsInside(below, x, ResidualSpace[x]));
    88         if (!eps.Any(x => ResidualSpace[x].Item1 >= below.X - x.X + residualSpace.Item1
    89           && ResidualSpace[x].Item2 >= below.Y - x.Y + residualSpace.Item2
    90           && ResidualSpace[x].Item3 >= below.Z - x.Z + residualSpace.Item3)) {
     84        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    9185          // add only if the projected point's residual space is not a sub-space
    9286          // of another extreme point's residual space
    … …  
    9488          AddExtremePoint(belowPoint);
    9589        }
    96         line = new Line3D(sourcePoint, new Vector3D(0, 0, -1));
    9790        // Projecting onto the XY-plane
    98         var back = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Front))
    99                                 .Concat(new[] { new Plane3D(BinShape, Side.Back) })
    100                                 .Select(x => x.Intersect(line))
    101                                 .Where(x => x != null && x.Z <= sourcePoint.Z)
    102                                 .MaxItems(x => x.Y).First();
    103         residualSpace = CalculateResidualSpace(below);
    104         eps = ExtremePoints.Where(x => IsInside(below, x, ResidualSpace[x]));
    105         if (!eps.Any(x => ResidualSpace[x].Item1 >= below.X - x.X + residualSpace.Item1
    106           && ResidualSpace[x].Item2 >= below.Y - x.Y + residualSpace.Item2
    107           && ResidualSpace[x].Item3 >= below.Z - x.Z + residualSpace.Item3)) {
     91        var back = ProjectBackward(sourcePoint);
     92        residualSpace = CalculateResidualSpace(back);
     93        if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
    10894          // add only if the projected point's residual space is not a sub-space
    10995          // of another extreme point's residual space
    … …  
    117103      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    118104        // Projecting onto the YZ-plane
    119         var line = new Line3D(sourcePoint, new Vector3D(-1, 0, 0));
    120         var left = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Right))
    121                                  .Concat(new[] { new Plane3D(BinShape, Side.Left) })
    122                                  .Select(x => x.Intersect(line))
    123                                  .Where(x => x != null && x.X <= sourcePoint.X)
    124                                  .MaxItems(x => x.Y).First();
     105        var left = ProjectLeft(sourcePoint);
    125106        var residualSpace = CalculateResidualSpace(left);
    126         var eps = ExtremePoints.Where(x => IsInside(left, x, ResidualSpace[x]));
    127         if (!eps.Any(x => ResidualSpace[x].Item1 >= left.X - x.X + residualSpace.Item1
    128           && ResidualSpace[x].Item2 >= left.Y - x.Y + residualSpace.Item2
    129           && ResidualSpace[x].Item3 >= left.Z - x.Z + residualSpace.Item3)) {
     107        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    130108          // add only if the projected point's residual space is not a sub-space
    131109          // of another extreme point's residual space
    … …  
    133111          AddExtremePoint(leftPoint);
    134112        }
    135         line = new Line3D(sourcePoint, new Vector3D(0, 0, -1));
    136113        // Projecting onto the XY-plane
    137         var back = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Front))
    138                                 .Concat(new[] { new Plane3D(BinShape, Side.Back) })
    139                                 .Select(x => x.Intersect(line))
    140                                 .Where(x => x != null && x.Z <= sourcePoint.Z)
    141                                 .MaxItems(x => x.Y).First();
    142         residualSpace = CalculateResidualSpace(left);
    143         eps = ExtremePoints.Where(x => IsInside(left, x, ResidualSpace[x]));
    144         if (!eps.Any(x => ResidualSpace[x].Item1 >= left.X - x.X + residualSpace.Item1
    145           && ResidualSpace[x].Item2 >= left.Y - x.Y + residualSpace.Item2
    146           && ResidualSpace[x].Item3 >= left.Z - x.Z + residualSpace.Item3)) {
     114        var back = ProjectBackward(sourcePoint);
     115        residualSpace = CalculateResidualSpace(back);
     116        if (!IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {
    147117          // add only if the projected point's residual space is not a sub-space
    148118          // of another extreme point's residual space
    … …  
    156126      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    157127        // Projecting onto the YZ-plane
    158         var line = new Line3D(sourcePoint, new Vector3D(-1, 0, 0));
    159         var left = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Right))
    160                                  .Concat(new[] { new Plane3D(BinShape, Side.Left) })
    161                                  .Select(x => x.Intersect(line))
    162                                  .Where(x => x != null && x.X <= sourcePoint.X)
    163                                  .MaxItems(x => x.Y).First();
     128        var left = ProjectLeft(sourcePoint);
    164129        var residualSpace = CalculateResidualSpace(left);
    165         var eps = ExtremePoints.Where(x => IsInside(left, x, ResidualSpace[x]));
    166         if (!eps.Any(x => ResidualSpace[x].Item1 >= left.X - x.X + residualSpace.Item1
    167           && ResidualSpace[x].Item2 >= left.Y - x.Y + residualSpace.Item2
    168           && ResidualSpace[x].Item3 >= left.Z - x.Z + residualSpace.Item3)) {
     130        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    169131          // add only if the projected point's residual space is not a sub-space
    170132          // of another extreme point's residual space
    … …  
    173135        }
    174136        // Projecting onto the XZ-plane
    175         line = new Line3D(sourcePoint, new Vector3D(0, -1, 0));
    176         var below = itemPlacement.Select(x => new Plane3D(x.Position, x.Item, Side.Top))
    177                                  .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })
    178                                  .Select(x => x.Intersect(line))
    179                                  .Where(x => x != null && x.Y <= sourcePoint.Y)
    180                                  .MaxItems(x => x.Y).First();
     137        var below = ProjectDown(sourcePoint);
    181138        residualSpace = CalculateResidualSpace(below);
    182         eps = ExtremePoints.Where(x => IsInside(below, x, ResidualSpace[x]));
    183         if (!eps.Any(x => ResidualSpace[x].Item1 >= below.X - x.X + residualSpace.Item1
    184           && ResidualSpace[x].Item2 >= below.Y - x.Y + residualSpace.Item2
    185           && ResidualSpace[x].Item3 >= below.Z - x.Z + residualSpace.Item3)) {
     139        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    186140          // add only if the projected point's residual space is not a sub-space
    187141          // of another extreme point's residual space
    … …  
    192146    }
    193147
    194     private bool IsBelow(PackingPosition lowerPos, PackingItem lowerItem, Vector3D upper) {
    195       return lowerPos.X <= upper.X && lowerPos.X + lowerItem.Width > upper.X
    196         && lowerPos.Z <= upper.Z && lowerPos.Z + lowerItem.Depth > upper.Z
    197         && lowerPos.Y + lowerItem.Height < upper.Y;
    198     }
    199 
    200     private bool IsLeft(PackingPosition leftPos, PackingItem leftItem, Vector3D right) {
    201       return leftPos.Y <= right.Y && leftPos.Y + leftItem.Height > right.Y
    202         && leftPos.Z <= right.Z && leftPos.Z + leftItem.Depth > right.Z
    203         && leftPos.X + leftItem.Width < right.X;
    204     }
    205 
    206     private bool IsBack(PackingPosition backPos, PackingItem backItem, Vector3D front) {
    207       return backPos.Y <= front.Y && backPos.Y + backItem.Height > front.Y
    208         && backPos.X <= front.X && backPos.X + backItem.Width > front.X
    209         && backPos.Z + backItem.Depth < front.Z;
    210     }
    211 
    212     private bool AddExtremePoint(PackingPosition current) {
    213       if (ExtremePoints.Add(current)) {
    214         ResidualSpace.Add(current, CalculateResidualSpace(current));
     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 => ResidualSpace[x].Item1 >= pos.X - x.X + residualSpace.Item1
     151          && ResidualSpace[x].Item2 >= pos.Y - x.Y + residualSpace.Item2
     152          && ResidualSpace[x].Item3 >= pos.Z - x.Z + residualSpace.Item3);
     153    }
     154
     155    private bool AddExtremePoint(PackingPosition pos) {
     156      if (ExtremePoints.Add(pos)) {
     157        ResidualSpace.Add(pos, Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z));
    215158        return true;
    216159      }
    … …  
    219162
    220163    private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) {
    221       return Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
    222     }
    223 
    224     private Tuple<int, int, int> CalculateResidualSpace(PackingPosition pos) {
    225       return Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
    226     }
    227 
    228     private bool IsInside(Vector3D point, PackingPosition pos, PackingItem item) {
    229       return point.X >= pos.X && point.X < pos.X + (pos.Rotated ? item.Depth : item.Width)
    230         && point.Y >= pos.Y && point.Y < pos.Y + item.Height
    231         && point.Z >= pos.Z && point.Z < pos.Z + (pos.Rotated ? item.Width : item.Depth);
    232     }
    233 
    234     private bool IsInside(Vector3D point, Vector3D pos, PackingItem item) {
    235       return point.X >= pos.X && point.X < pos.X + item.Width
    236         && point.Y >= pos.Y && point.Y < pos.Y + item.Height
    237         && point.Z >= pos.Z && point.Z < pos.Z + item.Depth;
    238     }
    239 
    240     private bool IsInside(Vector3D point, PackingPosition pos, Tuple<int, int, int> rs) {
    241       return point.X >= pos.X && point.X < pos.X + rs.Item1
    242         && point.Y >= pos.Y && point.Y < pos.Y + rs.Item2
    243         && point.Z >= pos.Z && point.Z < pos.Z + rs.Item3;
    244     }
    245 
    246     private bool IsInside(Vector3D point, Vector3D pos, Tuple<int, int, int> rs) {
    247       return point.X >= pos.X && point.X < pos.X + rs.Item1
    248         && point.Y >= pos.Y && point.Y < pos.Y + rs.Item2
    249         && point.Z >= pos.Z && point.Z < pos.Z + rs.Item3;
     164      var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] });
     165      var rightLimit = ProjectRight(pos);
     166      var upLimit = ProjectUp(pos);
     167      var forwardLimit = ProjectForward(pos);
     168      return Tuple.Create(rightLimit.X - pos.X, upLimit.Y - pos.Y, forwardLimit.Z - pos.Z);
     169    }
     170
     171    private Vector3D ProjectBackward(Vector3D pos) {
     172      var line = new Line3D(pos, new Vector3D(0, 0, -1));
     173      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
     174                  .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
     175                  .Concat(new[] { new Plane3D(BinShape, Side.Back) })
     176                  .Select(x => x.Intersect(line))
     177                  .Where(x => x != null && x.Z <= pos.Z)
     178                  .MaxItems(x => x.Z).First();
     179    }
     180
     181    private Vector3D ProjectLeft(Vector3D pos) {
     182      var line = new Line3D(pos, new Vector3D(-1, 0, 0));
     183      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
     184                  .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
     185                  .Concat(new[] { new Plane3D(BinShape, Side.Left) })
     186                  .Select(x => x.Intersect(line))
     187                  .Where(x => x != null && x.X <= pos.X)
     188                  .MaxItems(x => x.X).First();
     189    }
     190
     191    private Vector3D ProjectDown(Vector3D pos) {
     192      var line = new Line3D(pos, new Vector3D(0, -1, 0));
     193      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
     194                  .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
     195                  .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })
     196                  .Select(x => x.Intersect(line))
     197                  .Where(x => x != null && x.Y <= pos.Y)
     198                  .MaxItems(x => x.Y).First();
     199    }
     200
     201    private Vector3D ProjectForward(Vector3D pos) {
     202      var line = new Line3D(pos, new Vector3D(0, 0, 1));
     203      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
     204                  .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
     205                  .Concat(new[] { new Plane3D(BinShape, Side.Front) })
     206                  .Select(x => x.Intersect(line))
     207                  .Where(x => x != null && x.Z >= pos.Z)
     208                  .MinItems(x => x.Z).First();
     209    }
     210
     211    private Vector3D ProjectRight(Vector3D pos) {
     212      var line = new Line3D(pos, new Vector3D(1, 0, 0));
     213      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
     214                  .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
     215                  .Concat(new[] { new Plane3D(BinShape, Side.Right) })
     216                  .Select(x => x.Intersect(line))
     217                  .Where(x => x != null && x.X >= pos.X)
     218                  .MinItems(x => x.X).First();
     219    }
     220
     221    private Vector3D ProjectUp(Vector3D pos) {
     222      var line = new Line3D(pos, new Vector3D(0, 1, 0));
     223      return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })
     224                  .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
     225                  .Concat(new[] { new Plane3D(BinShape, Side.Top) })
     226                  .Select(x => x.Intersect(line))
     227                  .Where(x => x != null && x.Y >= pos.Y)
     228                  .MinItems(x => x.Y).First();
    250229    }
    251230
    … …  
    258237
    259238      var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints))
    260                             .OrderBy(x => x.X + x.Y + x.Z) // order by manhattan distance to try those closest to origin first
    261239                            .FirstOrDefault();
    262240      if (ep != null) {
    … …  
    330308        if (positionFound != null) {
    331309          PackItem(itemID, item, positionFound);
    332           if (Items.Count > 1)
    333             UpdateResidualSpace(item, positionFound);
    334310          sequence.Remove(itemID);
    335311        }
    … …  
    390366    }
    391367
    392 
    393368    public bool IsSupportedByAtLeastOnePoint(PackingItem item, PackingPosition position) {
    394369      if (position.Y == 0)
    … …  
    443418    public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {
    444419      foreach (var ep in ExtremePoints) {
    445         if (ep.Z >= pos.Z && ep.Z <= pos.Z + item.Depth) {
    446           if (ep.X <= pos.X && ep.Y > pos.Y && ep.Y < pos.Y + item.Height) {
     420        var rs = ResidualSpace[ep];
     421        var depth = pos.Rotated ? item.Width : item.Depth;
     422        var width = pos.Rotated ? item.Depth : item.Width;
     423        if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {
     424          if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {
    447425            var diff = pos.X - ep.X;
    448             var newRSX = ResidualSpace[ep].Item1 < diff ? ResidualSpace[ep].Item1 : diff;
    449             ResidualSpace[ep] = Tuple.Create(newRSX, ResidualSpace[ep].Item2, ResidualSpace[ep].Item3);
     426            var newRSX = Math.Min(rs.Item1, diff);
     427            ResidualSpace[ep] = Tuple.Create(newRSX, rs.Item2, rs.Item3);
    450428          }
    451           if (ep.Y <= pos.Y && ep.X > pos.X && ep.X < pos.X + item.Width) {
     429          if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {
    452430            var diff = pos.Y - ep.Y;
    453             var newRSY = ResidualSpace[ep].Item2 < diff ? ResidualSpace[ep].Item2 : diff;
    454             ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, newRSY, ResidualSpace[ep].Item3);
     431            var newRSY = Math.Min(rs.Item2, diff);
     432            ResidualSpace[ep] = Tuple.Create(rs.Item1, newRSY, rs.Item3);
    455433          }
    456434        }
    457435        if (ep.Z <= pos.Z &&
    458           ep.Y > pos.Y && ep.Y < pos.Y + item.Height &&
    459           ep.X > pos.X && ep.X < pos.X + item.Width) {
     436          ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&
     437          ep.X >= pos.X && ep.X < pos.X + width) {
    460438            var diff = pos.Z - ep.Z;
    461             var newRSZ = ResidualSpace[ep].Item3 < diff ? ResidualSpace[ep].Item3 : diff;
    462             ResidualSpace[ep] = Tuple.Create(ResidualSpace[ep].Item1, ResidualSpace[ep].Item2, newRSZ);
     439            var newRSZ = Math.Min(rs.Item3, diff);
     440            ResidualSpace[ep] = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
    463441        }
    464442      }
    … …  
    466444    }
    467445
     446    #region Helper classes for vector math
    468447    private class Vector3D {
    469448      public int X;
    … …  
    531510        );
    532511      }
     512
     513      public bool IsInside(PackingPosition pos, Tuple<int, int, int> rs) {
     514        return X >= pos.X && X < pos.X + rs.Item1
     515          && Y >= pos.Y && Y < pos.Y + rs.Item2
     516          && Z >= pos.Z && Z < pos.Z + rs.Item3;
     517      }
     518
    533519      public static int operator *(Vector3D a, Vector3D b) {
    534520        return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
    … …  
    614600
    615601      public Plane3D(PackingPosition pos, PackingItem item, Side side) {
    616         // the directing vectors are chosen such that Normal always points outside the packing item
     602        // the directing vectors are chosen such that normal always points outside the packing item
    617603        switch (side) {
    618604          case Side.Top: // ZX plane
    … …  
    651637      }
    652638
    653       public bool IsElementOf(Vector3D vector) {
    654         return Normal.X * vector.X + Normal.Y * vector.Y + Normal.Z * vector.Z == rhs;
     639      public bool IsElementOf(Vector3D point) {
     640        return Normal.X * point.X + Normal.Y * point.Y + Normal.Z * point.Z == rhs;
    655641      }
    656642
    … …  
    677663
    678664      public bool IsWithinDirectionalVectors(Vector3D point) {
    679         return point.X >= Point.X && (point.X <= Point.X + Direction1.X || point.X <= Point.X + Direction2.X)
    680             && point.Y >= Point.Y && (point.Y <= Point.Y + Direction1.Y || point.Y <= Point.Y + Direction2.Y)
    681             && point.Z >= Point.Z && (point.Z <= Point.Z + Direction1.Z || point.Z <= Point.Z + Direction2.Z);
    682       }
    683     }
     665        return point.X >= Point.X && (Direction1.X + Direction2.X == 0 || (point.X < Point.X + Direction1.X || point.X < Point.X + Direction2.X))
     666            && point.Y >= Point.Y && (Direction1.Y + Direction2.Y == 0 || (point.Y < Point.Y + Direction1.Y || point.Y < Point.Y + Direction2.Y))
     667            && point.Z >= Point.Z && (Direction1.Z + Direction2.Z == 0 || (point.Z < Point.Z + Direction1.Z || point.Z < Point.Z + Direction2.Z));
     668      }
     669    }
     670    #endregion
    684671  }
    685672}
Note: See TracChangeset for help on using the changeset viewer.