Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/20/17 16:15:38 (6 years ago)
Author:
rhanghof
Message:

#2817:

  • Unittests
  • Bugfixes on the line projection based extreme point creation method
File:
1 edited

Legend:

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

    r15520 r15554  
    3131   
    3232    protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
    33       foreach (var ep in binPacking.ExtremePoints.ToList()) {
    34         var rs = binPacking.ResidualSpaces[ep];
    35         var depth = position.Rotated ? item.Width : item.Depth;
    36         var width = position.Rotated ? item.Depth : item.Width;
    37         var changed = false;
    38         if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
    39           if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
    40             var diff = position.X - ep.X;
    41             var newRSX = Math.Min(rs.Width, diff);
    42             rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
     33      foreach (var extremePoint in binPacking.ExtremePoints.ToList()) {
     34        var ep = extremePoint.Key;
     35        var residualSpaces = extremePoint.Value as IList<ResidualSpace>;
     36        for (int i = 0; i < residualSpaces.Count(); i++) {
     37          var rs = residualSpaces[i];
     38          var depth = position.Rotated ? item.Width : item.Depth;
     39          var width = position.Rotated ? item.Depth : item.Width;
     40          var changed = false;
     41          if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
     42            if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
     43              var diff = position.X - ep.X;
     44              var newRSX = Math.Min(rs.Width, diff);
     45              rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
     46              changed = true;
     47            }
     48            if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
     49              var diff = position.Y - ep.Y;
     50              var newRSY = Math.Min(rs.Height, diff);
     51              rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
     52              changed = true;
     53            }
     54          }
     55
     56          if (ep.Z <= position.Z &&
     57              ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
     58              ep.X >= position.X && ep.X < position.X + width) {
     59            var diff = position.Z - ep.Z;
     60            var newRSZ = Math.Min(rs.Depth, diff);
     61            rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    4362            changed = true;
    4463          }
    45           if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
    46             var diff = position.Y - ep.Y;
    47             var newRSY = Math.Min(rs.Height, diff);
    48             rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
    49             changed = true;
     64
     65          if (changed) {
     66            if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
     67              residualSpaces[i] = rs;
     68            } else {
     69              binPacking.ExtremePoints.Remove(ep);
     70              break;
     71            }
    5072          }
    51         }
    52 
    53         if (ep.Z <= position.Z &&
    54             ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
    55             ep.X >= position.X && ep.X < position.X + width) {
    56           var diff = position.Z - ep.Z;
    57           var newRSZ = Math.Min(rs.Depth, diff);
    58           rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
    59           changed = true;
    60         }
    61 
    62         if (changed) {
    63           if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
    64             binPacking.ResidualSpaces[ep] = rs;
    65           } else {
    66             binPacking.ExtremePoints.Remove(ep);
    67             binPacking.ResidualSpaces.Remove(ep);
    68           }
    69         }
     73        }       
    7074      }
    7175      return;
     
    8185    /// <returns></returns>
    8286    protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
    83       if (binPacking.ExtremePoints.Add(position)) {
    84         var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
    85         binPacking.ResidualSpaces.Add(position, rs);
    86         // Check if the existing extreme points are shadowed by the new point
    87         // This is, their residual space fit entirely into the residual space of the new point
    88         foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
    89           if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
     87      if (binPacking.ExtremePoints.ContainsKey(position)) {
     88        return false;
     89      }
     90
     91      var residualSpaces = CalculateResidualSpace(binPacking, new Vector3D(position));
     92      binPacking.ExtremePoints.Add(position, residualSpaces);
     93      // Check if the existing extreme points are shadowed by the new point
     94      // This is, their residual space fit entirely into the residual space of the new point
     95      foreach (var ep in binPacking.ExtremePoints.Where(x => x.Key != position && new Vector3D(x.Key).IsInside(position, residualSpaces)).ToList()) {
     96        foreach (var residualSpace in ep.Value) {
     97          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep.Key), residualSpace, position, residualSpaces)) {
    9098            binPacking.ExtremePoints.Remove(ep);
    91             binPacking.ResidualSpaces.Remove(ep);
     99            break;
    92100          }
     101        }         
     102      }
     103      return true;
     104    }
     105
     106    /// <summary>
     107    /// Calculates the residual space for a given bin packing and position.
     108    /// It returns the residual space as a tuple which contains the dimensions
     109    /// </summary>
     110    /// <param name="binPacking"></param>
     111    /// <param name="pos"></param>
     112    /// <returns>A Tuple(width, Height, Depth)</width></returns>
     113    protected override IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos) {
     114      var residualSpaces = new List<ResidualSpace>();
     115      var residualSpace = new ResidualSpace(CalculateResidualSpaceOld(binPacking, pos));
     116      if (!residualSpace.IsZero()) {
     117        residualSpaces.Add(residualSpace);
     118      }
     119      return residualSpaces;
     120    }
     121
     122    protected Tuple<int, int, int> CalculateResidualSpaceOld(BinPacking3D binPacking, Vector3D pos) {
     123
     124      if (pos == null) {
     125        return Tuple.Create(0, 0, 0);
     126      }
     127      var itemPos = binPacking.Items.Select(x => new {
     128        Item = x.Value,
     129        Position = binPacking.Positions[x.Key]
     130      });
     131      Vector3D limit = new Vector3D() {
     132        X = binPacking.BinShape.Width,
     133        Y = binPacking.BinShape.Height,
     134        Z = binPacking.BinShape.Depth
     135      };
     136
     137      if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) {
     138        var rightLimit = ProjectRight(binPacking, pos);
     139        var upLimit = ProjectUp(binPacking, pos);
     140        var forwardLimit = ProjectForward(binPacking, pos);
     141        if (rightLimit.X > 0) {
     142          limit.X = rightLimit.X;
    93143        }
    94         return true;
     144        if (upLimit.Y > 0) {
     145          limit.Y = upLimit.Y;
     146        }
     147        if (forwardLimit.Z > 0) {
     148          limit.Z = forwardLimit.Z;
     149        }
    95150      }
    96       return false;
     151
     152      if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) {
     153        return Tuple.Create(0, 0, 0);
     154      }
     155      return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z);
    97156    }
    98157  }
Note: See TracChangeset for help on using the changeset viewer.