source: branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking/3.3/Decoders/PackingHeuristics.cs @ 9348

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Collections;
using HeuristicLab.Core;
using HeuristicLab.Problems.BinPacking.Dimensions;
using HeuristicLab.Problems.BinPacking.PackingBin;
using HeuristicLab.Problems.BinPacking.PackingItem;

namespace HeuristicLab.Problems.BinPacking.Decoders {
  public static class PackingHeuristics {
    public static TwoDimensionalPacking BottomLeftPosition(RectangularPackingBin binMeasures, int binNr, RectangularPackingItem currentItem, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, ItemList<RectangularPackingItem> itemMeasures) {
      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
      TwoDimensionalPacking currentPosition = new TwoDimensionalPacking(binNr, binMeasures.Width - currentItem.Width, binMeasures.Height - currentItem.Height);
      //Slide the item as far as possible to the left
      while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures)
        || IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures)) {
        //Slide the item as far as possible to the bottom
        while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures)) {
          currentPosition = MoveDown(currentPosition);
        }
        if (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures))
          currentPosition = MoveLeft(currentPosition);
      }

      return IsPositionFeasible(binMeasures, binNr, currentItem, currentPosition, itemPositions, itemMeasures) ? currentPosition : null;
    }

    private static bool IsPositionFeasible(RectangularPackingBin binMeasures, int binNr, RectangularPackingItem currentItem,
      TwoDimensionalPacking currentPosition, ObservableDictionary<int, TwoDimensionalPacking> itemPositions, ItemList<RectangularPackingItem> itemMeasures) {
      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
      if (!binMeasures.Encloses(currentPosition, currentItem))
        return false;
      var itemsWithPositions = itemMeasures.
        Select((Value, Index) => new { Value, Index }).
        Where(s => itemPositions.ContainsKey(s.Index)).
        Select((s) => new { Measures = itemMeasures[s.Index], Position = itemPositions[s.Index] });

      foreach (var itemWithPosition in itemsWithPositions) {
        if (itemWithPosition.Position.AssignedBin == binNr && itemWithPosition.Measures.Overlaps(itemWithPosition.Position, currentPosition, currentItem))
          return false;
      }

      return true;
    }

    private static TwoDimensionalPacking MoveLeft(TwoDimensionalPacking original) {
      return new TwoDimensionalPacking(original.AssignedBin, original.X - 1, original.Y);
    }
    private static TwoDimensionalPacking MoveDown(TwoDimensionalPacking original) {
      return new TwoDimensionalPacking(original.AssignedBin, original.X, original.Y - 1);
    }






    public static ThreeDimensionalPacking DeepestLeftBottomPosition(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> itemMeasures) {
      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
      ThreeDimensionalPacking currentPosition = new ThreeDimensionalPacking(binNr, binMeasures.Width - currentItem.Width, binMeasures.Height - currentItem.Height, binMeasures.Depth - currentItem.Depth);

      //Slide the item as far as possible to the bottom
      while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures)
        || IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures)
        || IsPositionFeasible(binMeasures, binNr, currentItem, MoveBack(currentPosition), itemPositions, itemMeasures)) {
        //Slide the item as far as possible to the left
        while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures)
          || IsPositionFeasible(binMeasures, binNr, currentItem, MoveBack(currentPosition), itemPositions, itemMeasures)) {
          //Slide the item as far as possible to the back
          while (IsPositionFeasible(binMeasures, binNr, currentItem, MoveBack(currentPosition), itemPositions, itemMeasures)) {
            currentPosition = MoveBack(currentPosition);
          }
          if (IsPositionFeasible(binMeasures, binNr, currentItem, MoveLeft(currentPosition), itemPositions, itemMeasures))
            currentPosition = MoveLeft(currentPosition);
        }
        if (IsPositionFeasible(binMeasures, binNr, currentItem, MoveDown(currentPosition), itemPositions, itemMeasures))
          currentPosition = MoveDown(currentPosition);
      }

      return IsPositionFeasible(binMeasures, binNr, currentItem, currentPosition, itemPositions, itemMeasures) ? currentPosition : null;
    }

    private static bool IsPositionFeasible(CuboidPackingBin binMeasures, int binNr, CuboidPackingItem currentItem,
      ThreeDimensionalPacking currentPosition, ObservableDictionary<int, ThreeDimensionalPacking> itemPositions, ItemList<CuboidPackingItem> itemMeasures) {
      //In this case feasability is defined as following: 1. the item fits into the bin-borders; 2. the item does not collide with another already packed item
      if (!binMeasures.Encloses(currentPosition, currentItem))
        return false;

      var itemsWithPositions = itemMeasures.
        Select((Value, Index) => new { Value, Index }).
        Where(s => itemPositions.ContainsKey(s.Index)).
        Select((s) => new { Measures = itemMeasures[s.Index], Position = itemPositions[s.Index] });

      foreach (var itemWithPosition in itemsWithPositions) {
        if (itemWithPosition.Position.AssignedBin == binNr && itemWithPosition.Measures.Overlaps(itemWithPosition.Position, currentPosition, currentItem))
          return false;
      }

      return true;
    }

    private static ThreeDimensionalPacking MoveLeft(ThreeDimensionalPacking original) {
      return new ThreeDimensionalPacking(original.AssignedBin, original.X - 1, original.Y, original.Z);
    }
    private static ThreeDimensionalPacking MoveDown(ThreeDimensionalPacking original) {
      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y - 1, original.Z);
    }
    private static ThreeDimensionalPacking MoveBack(ThreeDimensionalPacking original) {
      return new ThreeDimensionalPacking(original.AssignedBin, original.X, original.Y, original.Z - 1);
    }
  }
}