Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15304


Ignore:
Timestamp:
08/03/17 12:18:10 (7 years ago)
Author:
abeham
Message:

#2817:

  • Improved speed of GenerateNewExtremePointsForNewItem
  • GenerateNewExtremePointsForNewItem previously generated too many extreme points and the points were generated for each item anew each time an item was packed.
  • Some bugs are still present (generation of unnecessary extreme points, e.g. with a residual space that is a sub-space of the residual space of another extreme point)
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed

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

    r15276 r15304  
    7373      int newDepth = position.Rotated ? newItem.Width : newItem.Depth;
    7474
     75      var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList();
    7576      //Find ExtremePoints beginning from sourcepointX
    76       var sourcePointX = new PackingPosition(0, position.X + newWidth, position.Y, position.Z);
    77       if (sourcePointX.X < BinShape.Width && sourcePointX.Y < BinShape.Height && sourcePointX.Z < BinShape.Depth) {
     77      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
     78      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    7879        //Traversing down the y-axis 
    79         PackingPosition current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
    80         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    81           current = PackingPosition.MoveDown(current);
    82         }
    83         AddExtremePoint((PackingPosition)current.Clone());
    84         while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    85           current = PackingPosition.MoveLeft(current);
    86         }
    87         AddExtremePoint(current);
    88 
     80        var below = itemPlacement.Where(x => IsBelow(x.Position, x.Item, sourcePoint))
     81                                 .MaxItems(x => x.Position.Y + x.Item.Height).FirstOrDefault();
     82        var projY = false;
     83        if (below != null) {
     84          var belowPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, below.Position.Y + below.Item.Height, sourcePoint.Z);
     85          projY = AddExtremePoint(belowPoint);
     86        }
    8987        //Traversing down the z-axis
    90         current = new PackingPosition(0, sourcePointX.X, sourcePointX.Y, sourcePointX.Z);
    91         while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
    92           current = PackingPosition.MoveBack(current);
    93         }
    94         AddExtremePoint((PackingPosition)current.Clone());
    95         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    96           current = PackingPosition.MoveDown(current);
    97         }
    98         AddExtremePoint(current);
     88        var back = itemPlacement.Where(x => IsBack(x.Position, x.Item, sourcePoint))
     89                                .MaxItems(x => x.Position.Z + x.Item.Depth).FirstOrDefault();
     90        var projZ = false;
     91        if (back != null) {
     92          var backPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, back.Position.Z + back.Item.Depth);
     93          projZ = AddExtremePoint(backPoint);
     94        }
     95
     96        // only add the source point if both projections added new points
     97        // or if neither of the projections added a point
     98        // if a projection tried to add a point that already exists, then this
     99        // extreme point would be covered by the existing extreme point
     100        if ((below == null && back == null) || (below == null || projY) && (back == null || projZ))
     101          AddExtremePoint(new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, sourcePoint.Z));
    99102      }
    100103
    101104      //Find ExtremePoints beginning from sourcepointY
    102       var sourcePointY = new PackingPosition(0, position.X, position.Y + newItem.Height, position.Z);
    103       if (sourcePointY.X < BinShape.Width && sourcePointY.Y < BinShape.Height && sourcePointY.Z < BinShape.Depth) {
    104         //Traversing down the x-axis         
    105         PackingPosition current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
    106         while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    107           current = PackingPosition.MoveLeft(current);
    108         }
    109         AddExtremePoint((PackingPosition)current.Clone());
    110         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    111           current = PackingPosition.MoveDown(current);
    112         }
    113         AddExtremePoint(current);
     105      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
     106      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
     107        //Traversing down the x-axis   
     108        var left = itemPlacement.Where(x => IsLeft(x.Position, x.Item, sourcePoint))
     109                                .MaxItems(x => x.Position.X + x.Item.Width).FirstOrDefault();
     110        var projX = false;
     111        if (left != null) {
     112          var leftPoint = new PackingPosition(position.AssignedBin, left.Position.X + left.Item.Width, sourcePoint.Y, sourcePoint.Z);
     113          projX = AddExtremePoint(leftPoint);
     114        }
    114115
    115116        //Traversing down the z-axis
    116         current = new PackingPosition(0, sourcePointY.X, sourcePointY.Y, sourcePointY.Z);
    117         while (current.Z > 0 && !IsPointOccupied(PackingPosition.MoveBack(current))) {
    118           current = PackingPosition.MoveBack(current);
    119         }
    120         AddExtremePoint((PackingPosition)current.Clone());
    121         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    122           current = PackingPosition.MoveDown(current);
    123         }
    124         AddExtremePoint(current);
     117        var back = itemPlacement.Where(x => IsBack(x.Position, x.Item, sourcePoint))
     118                                .MaxItems(x => x.Position.Z + x.Item.Depth).FirstOrDefault();
     119        var projZ = false;
     120        if (back != null) {
     121          var backPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, back.Position.Z + back.Item.Depth);
     122          projZ = AddExtremePoint(backPoint);
     123        }
     124
     125        // only add the source point if both projections added new points
     126        // or if neither of the projections added a point
     127        // if a projection tried to add a point that already exists, then this
     128        // extreme point would be covered by the existing extreme point
     129        if ((left == null || projX) && (back == null || projZ))
     130          AddExtremePoint(new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, sourcePoint.Z));
    125131      }
    126132
    127133      //Find ExtremePoints beginning from sourcepointZ
    128       var sourcePointZ = new PackingPosition(0, position.X, position.Y, position.Z + newDepth);
    129       if (sourcePointZ.X < BinShape.Width && sourcePointZ.Y < BinShape.Height && sourcePointZ.Z < BinShape.Depth) {
     134      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
     135      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    130136        //Traversing down the x-axis
    131         PackingPosition current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
    132         while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    133           current = PackingPosition.MoveLeft(current);
    134         }
    135         AddExtremePoint((PackingPosition)current.Clone());
    136         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    137           current = PackingPosition.MoveDown(current);
    138         }
    139         AddExtremePoint(current);
     137        var left = itemPlacement.Where(x => IsLeft(x.Position, x.Item, sourcePoint))
     138                                .MaxItems(x => x.Position.X + x.Item.Width).FirstOrDefault();
     139        var projX = false;
     140        if (left != null) {
     141          var leftPoint = new PackingPosition(position.AssignedBin, left.Position.X + left.Item.Width, sourcePoint.Y, sourcePoint.Z);
     142          projX = AddExtremePoint(leftPoint);
     143        }
    140144
    141145        //Traversing down the y-axis
    142         current = new PackingPosition(0, sourcePointZ.X, sourcePointZ.Y, sourcePointZ.Z);
    143         while (current.Y > 0 && !IsPointOccupied(PackingPosition.MoveDown(current))) {
    144           current = PackingPosition.MoveDown(current);
    145         }
    146         AddExtremePoint((PackingPosition)current.Clone());
    147         while (current.X > 0 && !IsPointOccupied(PackingPosition.MoveLeft(current))) {
    148           current = PackingPosition.MoveLeft(current);
    149         }
    150         AddExtremePoint(current);
    151       }
    152     }
    153 
    154     private void AddExtremePoint(PackingPosition current) {
     146        var below = itemPlacement.Where(x => IsBelow(x.Position, x.Item, sourcePoint))
     147                                 .MaxItems(x => x.Position.Y + x.Item.Height).FirstOrDefault();
     148        var projY = false;
     149        if (below != null) {
     150          var belowPoint = new PackingPosition(position.AssignedBin, sourcePoint.X, below.Position.Y + below.Item.Height, sourcePoint.Z);
     151          projY = AddExtremePoint(belowPoint);
     152        }
     153
     154        // only add the source point if both projections added new points
     155        // or if neither of the projections added a point
     156        // if a projection tried to add a point that already exists, then this
     157        // extreme point would be covered by the existing extreme point
     158        if ((left == null || projX) && (below == null || projY))
     159          AddExtremePoint(new PackingPosition(position.AssignedBin, sourcePoint.X, sourcePoint.Y, sourcePoint.Z));
     160      }
     161    }
     162
     163    private bool IsBelow(PackingPosition lowerPos, PackingItem lowerItem, Vector3D upper) {
     164      return lowerPos.X <= upper.X && lowerPos.X + lowerItem.Width > upper.X
     165        && lowerPos.Z <= upper.Z && lowerPos.Z + lowerItem.Depth > upper.Z
     166        && lowerPos.Y + lowerItem.Height < upper.Y;
     167    }
     168
     169    private bool IsLeft(PackingPosition leftPos, PackingItem leftItem, Vector3D right) {
     170      return leftPos.Y <= right.Y && leftPos.Y + leftItem.Height > right.Y
     171        && leftPos.Z <= right.Z && leftPos.Z + leftItem.Depth > right.Z
     172        && leftPos.X + leftItem.Width < right.X;
     173    }
     174
     175    private bool IsBack(PackingPosition backPos, PackingItem backItem, Vector3D front) {
     176      return backPos.Y <= front.Y && backPos.Y + backItem.Height > front.Y
     177        && backPos.X <= front.X && backPos.X + backItem.Width > front.X
     178        && backPos.Z + backItem.Depth < front.Z;
     179    }
     180
     181    private bool AddExtremePoint(PackingPosition current) {
    155182      if (ExtremePoints.Add(current)) {
    156183        var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z);
    157184        ResidualSpace.Add(current, tuple);
    158       }
     185        return true;
     186      }
     187      return false;
    159188    }
    160189
    … …  
    166195        item.TargetBin, item.Weight, item.Material);
    167196
    168       var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints)).FirstOrDefault();
     197      var ep = ExtremePoints.Where(x => IsPositionFeasible(newItem, x, stackingConstraints))
     198                            .OrderBy(x => x.X + x.Y + x.Z) // order by manhattan distance to try those closest to origin first
     199                            .FirstOrDefault();
    169200      if (ep != null) {
    170201        var result = new PackingPosition(ep.AssignedBin, ep.X, ep.Y, ep.Z, rotated);
    … …  
    372403      return;
    373404    }
     405
     406    private class Vector3D {
     407      public int X;
     408      public int Y;
     409      public int Z;
     410      public Vector3D() { }
     411      public Vector3D(int x, int y, int z) {
     412        X = x;
     413        Y = y;
     414        Z = z;
     415      }
     416      public Vector3D(PackingPosition pos) {
     417        X = pos.X;
     418        Y = pos.Y;
     419        Z = pos.Z;
     420      }
     421      public static Vector3D AlongX(Vector3D pos, PackingItem item) {
     422        return new Vector3D(
     423          pos.X + item.Width,
     424          pos.Y,
     425          pos.Z
     426        );
     427      }
     428      public static Vector3D AlongY(Vector3D pos, PackingItem item) {
     429        return new Vector3D(
     430          pos.X,
     431          pos.Y + item.Height,
     432          pos.Z
     433        );
     434      }
     435      public static Vector3D AlongZ(Vector3D pos, PackingItem item) {
     436        return new Vector3D(
     437          pos.X,
     438          pos.Y,
     439          pos.Z + item.Depth
     440        );
     441      }
     442      public static Vector3D AlongX(PackingPosition pos, PackingItem item) {
     443        return new Vector3D(
     444          pos.X + item.Width,
     445          pos.Y,
     446          pos.Z
     447        );
     448      }
     449      public static Vector3D AlongY(PackingPosition pos, PackingItem item) {
     450        return new Vector3D(
     451          pos.X,
     452          pos.Y + item.Height,
     453          pos.Z
     454        );
     455      }
     456      public static Vector3D AlongZ(PackingPosition pos, PackingItem item) {
     457        return new Vector3D(
     458          pos.X,
     459          pos.Y,
     460          pos.Z + item.Depth
     461        );
     462      }
     463
     464      public static bool Intersects(Vector3D p1, Vector3D dir, Vector3D p2, Vector3D dir2, Vector3D dir3) {
     465        var normal = dir2.Cross(dir3);
     466        var denom = normal * dir;
     467        if (denom == 0) {
     468          // dir is perpendicular to the normal vector of the plane
     469          // this means they intersect if p1 is element of the plane
     470          return p1.X * normal.X + p1.Y * normal.Y + p1.Z * normal.Z == p2.X * normal.X + p2.Y * normal.Y + p2.Z * normal.Z
     471            && IsInPlane(p1, p2, dir2, dir3);
     472        }
     473        var intersect = p1 + ((normal * (p2 - p1)) / denom) * dir;
     474        return IsInPlane(intersect, p2, dir2, dir3);
     475      }
     476
     477      private static bool IsInPlane(Vector3D p1, Vector3D p2, Vector3D dir2, Vector3D dir3) {
     478        return p1.X >= p2.X && (p1.X <= p2.X + dir2.X || p1.X <= p2.X + dir3.X)
     479            && p1.Y >= p2.Y && (p1.Y <= p2.Y + dir2.Y || p1.Y <= p2.Y + dir3.Y)
     480            && p1.Z >= p2.Z && (p1.Z <= p2.Z + dir2.Z || p1.Z <= p2.Z + dir3.Z);
     481      }
     482
     483      public Vector3D Cross(Vector3D b) {
     484        return new Vector3D(
     485          Y * b.Z - Z * b.Y,
     486          -X * b.Z + Z * b.X,
     487          X * b.Y - Y * b.X
     488        );
     489      }
     490      public static int operator *(Vector3D a, Vector3D b) {
     491        return a.X * b.X + a.Y * b.Y + a.Z * b.Z;
     492      }
     493      public static Vector3D operator *(int a, Vector3D b) {
     494        return new Vector3D(a * b.X, a * b.Y, a * b.Z);
     495      }
     496      public static Vector3D operator *(Vector3D a, int b) {
     497        return new Vector3D(a.X * b, a.Y * b, a.Z * b);
     498      }
     499      public static Vector3D operator +(Vector3D a, Vector3D b) {
     500        return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z);
     501      }
     502      public static Vector3D operator -(Vector3D a, Vector3D b) {
     503        return new Vector3D(a.X - b.X, a.Y - b.Y, a.Z - b.Z);
     504      }
     505    }
    374506  }
    375507}

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

    r14162 r15304  
    7676    }
    7777
     78    [Obsolete]
    7879    public static PackingPosition MoveLeft(PackingPosition original) {
    7980      return new PackingPosition(original.AssignedBin, original.X - 1, original.Y, original.Z, original.Rotated);
    8081    }
     82    [Obsolete]
    8183    public static PackingPosition MoveDown(PackingPosition original) {
    8284      return new PackingPosition(original.AssignedBin, original.X, original.Y - 1, original.Z, original.Rotated);
    8385    }
     86    [Obsolete]
    8487    public static PackingPosition MoveBack(PackingPosition original) {
    8588      return new PackingPosition(original.AssignedBin, original.X, original.Y, original.Z - 1, original.Rotated);
    8689    }
    87 
     90    [Obsolete]
    8891    public static PackingPosition MoveRight(PackingPosition original) {
    8992      return new PackingPosition(original.AssignedBin, original.X + 1, original.Y, original.Z, original.Rotated);
    9093    }
     94    [Obsolete]
    9195    public static PackingPosition MoveUp(PackingPosition original) {
    9296      return new PackingPosition(original.AssignedBin, original.X, original.Y + 1, original.Z, original.Rotated);
    9397    }
     98    [Obsolete]
    9499    public static PackingPosition MoveFront(PackingPosition original) {
    95100      return new PackingPosition(original.AssignedBin, original.X, original.Y, original.Z + 1, original.Rotated);

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

    r15241 r15304  
    100100      Positions[itemID] = position;
    101101      ExtremePoints.Remove(position);
    102       foreach (int id in Items.Select(x => x.Key))
    103         GenerateNewExtremePointsForNewItem(Items[id], Positions[id]);
     102      GenerateNewExtremePointsForNewItem(item, position);
    104103     
    105104      AddNewItemToOccupationLayers(itemID, item, position);
Note: See TracChangeset for help on using the changeset viewer.