Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15305


Ignore:
Timestamp:
08/04/17 12:37:19 (7 years ago)
Author:
abeham
Message:

#2817:

  • Avoided generating unnecessary extreme points
  • Added vector calculation code for line/plane intersection
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r15304 r15305  
    7474
    7575      var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList();
    76       //Find ExtremePoints beginning from sourcepointX
     76      // Find ExtremePoints beginning from sourcepointX
    7777      var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
    7878      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    79         //Traversing down the y-axis 
    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         }
    87         //Traversing down the z-axis
    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));
     79        // 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();
     86        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)) {
     91          // add only if the projected point's residual space is not a sub-space
     92          // of another extreme point's residual space
     93          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
     94          AddExtremePoint(belowPoint);
     95        }
     96        line = new Line3D(sourcePoint, new Vector3D(0, 0, -1));
     97        // 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)) {
     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 backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
     111          AddExtremePoint(backPoint);
     112        }
    102113      }
    103114
    … …  
    105116      sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
    106117      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         }
    115 
    116         //Traversing down the z-axis
    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));
     118        // 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();
     125        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)) {
     130          // add only if the projected point's residual space is not a sub-space
     131          // of another extreme point's residual space
     132          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
     133          AddExtremePoint(leftPoint);
     134        }
     135        line = new Line3D(sourcePoint, new Vector3D(0, 0, -1));
     136        // 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)) {
     147          // add only if the projected point's residual space is not a sub-space
     148          // of another extreme point's residual space
     149          var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
     150          AddExtremePoint(backPoint);
     151        }
    131152      }
    132153
    … …  
    134155      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
    135156      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
    136         //Traversing down the x-axis
    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         }
    144 
    145         //Traversing down the y-axis
    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));
     157        // 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();
     164        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)) {
     169          // add only if the projected point's residual space is not a sub-space
     170          // of another extreme point's residual space
     171          var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
     172          AddExtremePoint(leftPoint);
     173        }
     174        // 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();
     181        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)) {
     186          // add only if the projected point's residual space is not a sub-space
     187          // of another extreme point's residual space
     188          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
     189          AddExtremePoint(belowPoint);
     190        }
    160191      }
    161192    }
    … …  
    181212    private bool AddExtremePoint(PackingPosition current) {
    182213      if (ExtremePoints.Add(current)) {
    183         var tuple = Tuple.Create(BinShape.Width - current.X, BinShape.Height - current.Y, BinShape.Depth - current.Z);
    184         ResidualSpace.Add(current, tuple);
     214        ResidualSpace.Add(current, CalculateResidualSpace(current));
    185215        return true;
    186216      }
    187217      return false;
     218    }
     219
     220    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;
    188250    }
    189251
    … …  
    462524      }
    463525
    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 
    483526      public Vector3D Cross(Vector3D b) {
    484527        return new Vector3D(
    … …  
    504547      }
    505548    }
     549
     550    // A line is given as a point and a directing vector
     551    private class Line3D {
     552      public Vector3D Point;
     553      public Vector3D Direction;
     554
     555      public Line3D(Vector3D point, Vector3D direction) {
     556        Point = point;
     557        Direction = direction;
     558      }
     559
     560      public bool Intersects(Plane3D plane) {
     561        return plane.Intersects(this);
     562      }
     563
     564      public Vector3D Intersect(Plane3D plane) {
     565        return plane.Intersect(this);
     566      }
     567    }
     568
     569    private enum Side { Top, Left, Bottom, Right, Front, Back }
     570    // A plane is given as a point and two directing vectors
     571    private class Plane3D {
     572      public Vector3D Point { get; private set; }
     573      public Vector3D Direction1 { get; private set; }
     574      public Vector3D Direction2 { get; private set; }
     575      public Vector3D Normal { get; private set; }
     576      private int rhs;
     577
     578      public Plane3D(PackingShape bin, Side side) {
     579        switch (side) {
     580          case Side.Top: // ZX plane
     581            Point = new Vector3D(0, bin.Height, 0);
     582            Direction1 = new Vector3D(0, 0, bin.Depth);
     583            Direction2 = new Vector3D(bin.Width, 0, 0);
     584            break;
     585          case Side.Left: // ZY plane
     586            Point = new Vector3D(0, 0, 0);
     587            Direction1 = new Vector3D(0, 0, bin.Depth);
     588            Direction2 = new Vector3D(0, bin.Height, 0);
     589            break;
     590          case Side.Bottom: // XZ plane
     591            Point = new Vector3D(0, 0, 0);
     592            Direction1 = new Vector3D(bin.Width, 0, 0);
     593            Direction2 = new Vector3D(0, 0, bin.Depth);
     594            break;
     595          case Side.Right: // YZ plane
     596            Point = new Vector3D(bin.Width, 0, 0);
     597            Direction1 = new Vector3D(0, bin.Height, 0);
     598            Direction2 = new Vector3D(0, 0, bin.Depth);
     599            break;
     600          case Side.Front: // XY plane
     601            Point = new Vector3D(0, 0, bin.Depth);
     602            Direction1 = new Vector3D(bin.Width, 0, 0);
     603            Direction2 = new Vector3D(0, bin.Height, 0);
     604            break;
     605          case Side.Back: // YX plane
     606            Point = new Vector3D(0, 0, 0);
     607            Direction1 = new Vector3D(0, bin.Height, 0);
     608            Direction2 = new Vector3D(bin.Width, 0, 0);
     609            break;
     610        }
     611        Normal = Direction1.Cross(Direction2);
     612        rhs = 0;
     613      }
     614
     615      public Plane3D(PackingPosition pos, PackingItem item, Side side) {
     616        // the directing vectors are chosen such that Normal always points outside the packing item
     617        switch (side) {
     618          case Side.Top: // ZX plane
     619            Point = new Vector3D(pos.X, pos.Y + item.Height, pos.Z);
     620            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
     621            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
     622            break;
     623          case Side.Left: // ZY plane
     624            Point = new Vector3D(pos.X, pos.Y, pos.Z);
     625            Direction1 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
     626            Direction2 = new Vector3D(0, item.Height, 0);
     627            break;
     628          case Side.Bottom: // XZ plane
     629            Point = new Vector3D(pos.X, pos.Y, pos.Z);
     630            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
     631            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
     632            break;
     633          case Side.Right: // YZ plane
     634            Point = new Vector3D(pos.X + (pos.Rotated ? item.Depth : item.Width), pos.Y, pos.Z);
     635            Direction1 = new Vector3D(0, item.Height, 0);
     636            Direction2 = new Vector3D(0, 0, pos.Rotated ? item.Width : item.Depth);
     637            break;
     638          case Side.Front: // XY plane
     639            Point = new Vector3D(pos.X, pos.Y, pos.Z + (pos.Rotated ? item.Width : item.Depth));
     640            Direction1 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
     641            Direction2 = new Vector3D(0, item.Height, 0);
     642            break;
     643          case Side.Back: // YX plane
     644            Point = new Vector3D(pos.X, pos.Y, pos.Z);
     645            Direction1 = new Vector3D(0, item.Height, 0);
     646            Direction2 = new Vector3D(pos.Rotated ? item.Depth : item.Width, 0, 0);
     647            break;
     648        }
     649        Normal = Direction1.Cross(Direction2);
     650        rhs = Normal.X * Point.X + Normal.Y * Point.Y + Normal.Z * Point.Z;
     651      }
     652
     653      public bool IsElementOf(Vector3D vector) {
     654        return Normal.X * vector.X + Normal.Y * vector.Y + Normal.Z * vector.Z == rhs;
     655      }
     656
     657      public bool Intersects(Line3D line) {
     658        return Intersect(line) != null;
     659      }
     660
     661      public Vector3D Intersect(Line3D line) {
     662        var denom = Normal * line.Direction;
     663        if (denom == 0) {
     664          // dir is perpendicular to the normal vector of the plane
     665          // this means they intersect if p1 is element of the plane
     666          // also the plane does not stretch infinitely, but is bound
     667          // to the parallelogram spanned by the point and the two
     668          // directing vectors
     669          if (IsElementOf(line.Point) && IsWithinDirectionalVectors(line.Point))
     670            return line.Point;
     671          else return null;
     672        }
     673        var intersect = line.Point + ((Normal * (Point - line.Point)) / denom) * line.Direction;
     674        if (IsWithinDirectionalVectors(intersect)) return intersect;
     675        return null;
     676      }
     677
     678      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    }
    506684  }
    507685}
Note: See TracChangeset for help on using the changeset viewer.