using HeuristicLab.Common;
using HeuristicLab.Problems.BinPacking3D.Geometry;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
///
/// This extreme point creation class uses the point projection based method by Crainic, T. G., Perboli, G., & Tadei, R. for creating extreme points.
/// Each extreme point of an item is being projectet backwards, downwards and to the left.
/// A new extreme point will be created where this projections instersects with another item or the bin boundins.
///
public class PointProjectionBasedEPCreator : ExtremePointCreator {
protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
GenerateNewExtremePointsForItem(binPacking, item, position);
// if an item is fit in below, before, or left of another its extreme points have to be regenerated
foreach (var above in GetItemsAbove(binPacking, position)) {
GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
}
foreach (var front in GetItemsInfront(binPacking, position)) {
GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
}
foreach (var right in GetItemsOnRight(binPacking, position)) {
GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
}
}
protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
foreach (var ep in binPacking.ExtremePoints.ToList()) {
var rs = binPacking.ResidualSpaces[ep];
var depth = position.Rotated ? item.Width : item.Depth;
var width = position.Rotated ? item.Depth : item.Width;
var changed = false;
if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
var diff = position.X - ep.X;
var newRSX = Math.Min(rs.Width, diff);
rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
changed = true;
}
if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
var diff = position.Y - ep.Y;
var newRSY = Math.Min(rs.Height, diff);
rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
changed = true;
}
}
if (ep.Z <= position.Z &&
ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
ep.X >= position.X && ep.X < position.X + width) {
var diff = position.Z - ep.Z;
var newRSZ = Math.Min(rs.Depth, diff);
rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
changed = true;
}
if (changed) {
if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
binPacking.ResidualSpaces[ep] = rs;
} else {
binPacking.ExtremePoints.Remove(ep);
binPacking.ResidualSpaces.Remove(ep);
}
}
}
return;
}
///
/// Adds an extreme point to a given bin packing.
/// It also adds the residual space for the new extreme point
/// and removes the extreme point and the related residual space for the given position which are not needed anymore.
///
///
///
///
protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
if (binPacking.ExtremePoints.Add(position)) {
var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
binPacking.ResidualSpaces.Add(position, rs);
// Check if the existing extreme points are shadowed by the new point
// This is, their residual space fit entirely into the residual space of the new point
foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
binPacking.ExtremePoints.Remove(ep);
binPacking.ResidualSpaces.Remove(ep);
}
}
return true;
}
return false;
}
}
}