#region License Information
/* HeuristicLab
* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Problems.BinPacking;
using HeuristicLab.Problems.BinPacking3D.Geometry;
using HeuristicLab.Collections;
using HeuristicLab.Problems.BinPacking3D.Graph;
namespace HeuristicLab.Problems.BinPacking3D {
[Item("BinPacking3D", "Represents a single-bin packing for a 3D bin-packing problem.")]
[StorableClass]
public class BinPacking3D : BinPacking {
[Storable]
public IDictionary> ExtremePoints { get; protected set; }
[Storable]
public IDirectedGraph WeightDistirbution { get; protected set; }
public BinPacking3D(PackingShape binShape)
: base(binShape) {
ExtremePoints = new SortedList>();
ExtremePoints.Add(binShape.Origin, new List() { ResidualSpace.Create(binShape.Width, binShape.Height, binShape.Depth) });
WeightDistirbution = new DirectedGraph();
}
[StorableConstructor]
protected BinPacking3D(bool deserializing) : base(deserializing) { }
protected BinPacking3D(BinPacking3D original, Cloner cloner)
: base(original, cloner) {
this.ExtremePoints = new SortedList>();
foreach (var extremePoint in original.ExtremePoints) {
var residualSpaces = new List();
foreach (var residualSpace in extremePoint.Value) {
residualSpaces.Add(cloner.Clone(residualSpace));
}
ExtremePoints.Add(cloner.Clone(extremePoint.Key), residualSpaces);
}
WeightDistirbution = original.WeightDistirbution.Clone() as IDirectedGraph;
}
public override IDeepCloneable Clone(Cloner cloner) {
return new BinPacking3D(this, cloner);
}
///
/// Puts a given item into the bin packing at the given position.
///
/// Offset in the internal item array
/// Item
/// Position of the item in the bin packing
public override void PackItem(int itemID, PackingItem item, PackingPosition position) {
Items[itemID] = item;
Positions[itemID] = position;
ExtremePoints.Remove(position);
AddToGraph(itemID, item, position);
}
#region Graph for the calculating the weight distirbution
///
/// The given item is added to the graph as the source vertex.
/// Its items below are the target vertices.
///
///
///
///
private void AddToGraph(int itemId, PackingItem item, PackingPosition position) {
var sourceVertex = new VertexWithItemId(itemId);
WeightDistirbution.AddVertex(sourceVertex);
var itemsBelow = GetItemsUnderAnItem(position, item);
foreach (var itemBelow in itemsBelow) {
var targetVertex = GetVertexForItemBelow(itemBelow);
if (targetVertex == null) {
continue;
}
double overlay = CalculateOverlay(itemBelow, Tuple.Create(position, item));
double area = (item.Width * item.Depth);
var arc = new Arc(sourceVertex, targetVertex) {
Weight = overlay / area
};
WeightDistirbution.AddArc(arc);
}
}
///
/// Returns a vertex related to the given tuple of an item and packing position.
/// If there is no related vertex the method returns null.
///
///
///
private IVertex GetVertexForItemBelow(Tuple itemBelow) {
var filteredItems = Items.Where(x => x.Value == itemBelow.Item2);
if (filteredItems.Count() <= 0) {
return null;
}
var itemIdBelow = filteredItems.First().Key;
var targetVertex = WeightDistirbution.Vertices.Where(x => {
if (x is VertexWithItemId) {
return ((VertexWithItemId)x).ItemId == itemIdBelow;
}
return false;
}).FirstOrDefault();
return targetVertex;
}
#endregion
#region Calculation of the stacked weight
public double GetStackedWeightForItemId(int itemId) {
return GetStackedWeightForItemIdRec(itemId);
}
private double GetStackedWeightForItemIdRec(int itemId) {
var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Target).ItemId == itemId);
var stackedWeight = 0.0;
foreach (var arc in arcs) {
var sourceItemId = ((VertexWithItemId)arc.Source).ItemId;
var sourceItem = Items[sourceItemId];
stackedWeight += (GetStackedWeightForItemIdRec(sourceItemId) + sourceItem.Weight) * arc.Weight;
}
return stackedWeight;
}
#endregion
#region MassPoint
///
/// This property contains the value of the mass point for the current bin packing.
///
public Tuple MassPoint { get { return CalculateMassPoint(); } }
private Tuple CalculateMassPoint() {
var packingMassPoint = new { X = 0.0, Y = 0.0, Z = 0.0 };
var totalWeight = 0.0;
foreach (var item in Items) {
var position = Positions[item.Key];
var w = item.Value.Width;
var h = item.Value.Height;
var d = item.Value.Depth;
var massPoint = new { X = position.X + w / 2.0, Y = position.Y + h / 2.0, Z = position.Z + d / 2.0 };
var weight = Math.Max(item.Value.Weight, 1);
if (packingMassPoint == null) {
packingMassPoint = massPoint;
totalWeight += weight;
} else {
var newTotalWeight = totalWeight + weight;
packingMassPoint = new {
X = (massPoint.X * weight + packingMassPoint.X * totalWeight) / newTotalWeight,
Y = (massPoint.Y * weight + packingMassPoint.Y * totalWeight) / newTotalWeight,
Z = (massPoint.Z * weight + packingMassPoint.Z * totalWeight) / newTotalWeight
};
totalWeight = newTotalWeight;
}
}
return Tuple.Create(packingMassPoint.X, packingMassPoint.Y, packingMassPoint.Z);
}
#endregion
#region Position feasability
///
/// In this case feasability is defined as following:
/// 1. the point is supported by something;
/// 2. the item does not collide with another already packed item
///
///
///
///
///
public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) {
return ItemCanBePlaced(item, position) && CheckStackingConstraints(item, position, stackingConstraints);
}
///
/// Returns true if a given item can be placed in the current bin
///
///
///
///
private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) {
// Check if the boundings of the bin would injured
if (givenItemPosition.X + givenItem.Width > BinShape.Width ||
givenItemPosition.Y + givenItem.Height > BinShape.Height ||
givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {
return false;
}
//if the given item collides with any other item, it can not be placed
foreach (var item in Items) {
if (ItemsCollides(new Tuple(Positions[item.Key], item.Value),
new Tuple(givenItemPosition, givenItem))) {
return false;
}
}
return true;
}
///
/// Checks if two given items in a space collides
///
///
///
///
private bool ItemsCollides(Tuple t1, Tuple t2) {
var position1 = t1.Item1;
var item1 = t1.Item2;
var position2 = t2.Item1;
var item2 = t2.Item2;
var cx = (position2.X == position1.X) || (position2.X < position1.X && position2.X + item2.Width > position1.X) || (position2.X > position1.X && position1.X + item1.Width > position2.X);
var cy = (position2.Y == position1.Y) || (position2.Y < position1.Y && position2.Y + item2.Height > position1.Y) || (position2.Y > position1.Y && position1.Y + item1.Height > position2.Y);
var cz = (position2.Z == position1.Z) || (position2.Z < position1.Z && position2.Z + item2.Depth > position1.Z) || (position2.Z > position1.Z && position1.Z + item1.Depth > position2.Z);
return cx && cy && cz;
}
///
/// Checks the stacking constraints. This method depends that the given item can be placed at this position
///
///
///
///
///
private bool CheckStackingConstraints(PackingItem item, PackingPosition position, bool stackingConstraints) {
if (position.Y == 0 || !stackingConstraints && HasOnePointWithAnItemBelow(item, position)) {
return true;
}
return IsStaticStable(item, position) && IsWeightSupported(item, position);
}
///
/// Checks if a given item has any point lieing on another item.
///
///
///
///
private bool HasOnePointWithAnItemBelow(PackingItem item, PackingPosition position) {
bool p1, p2, p3, p4;
PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
return p1 || p2 || p3 || p4;
}
///
/// Checks if a given item is static stable.
/// A item is static stable if all edges have an object below.
///
///
///
///
public override bool IsStaticStable(PackingItem item, PackingPosition position) {
bool p1, p2, p3, p4;
PointsLiesOnAnStackableItem(item, position, out p1, out p2, out p3, out p4);
return p1 && p2 && p3 && p4;
}
///
/// This method sets the out parameters p1 ... p4 if the point lies on another item.
/// p1 ... p3 represents one point on the bottom side of an given item.
/// +---------+
/// |p1 p2|
/// | |
/// |p4 p3|
/// +---------+
///
/// Given item
/// Given item position
///
///
///
///
private void PointsLiesOnAnStackableItem(PackingItem item, PackingPosition position, out bool p1, out bool p2, out bool p3, out bool p4) {
IEnumerable> itemsP1;
IEnumerable> itemsP2;
IEnumerable> itemsP3;
IEnumerable> itemsP4;
GetItemsUnderItemWithContact(item, position, out itemsP1, out itemsP2, out itemsP3, out itemsP4);
p1 = itemsP1.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z < x.Item1.Z + x.Item2.Depth).Any();
p2 = itemsP2.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z < x.Item1.Z + x.Item2.Depth).Any();
p3 = itemsP3.Where(x => x.Item2.IsStackabel && position.X + item.Width > x.Item1.X && position.Z + item.Depth > x.Item1.Z).Any();
p4 = itemsP4.Where(x => x.Item2.IsStackabel && position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any();
}
///
/// This method returns a collection for the out parameters itemsP1 ... itemsP4 with the items below
/// itemsP1 ... itemsP4 represents one point on the bottom side of an given item.
/// +---------+
/// |p1 p2|
/// | |
/// |p4 p3|
/// +---------+
///
///
///
///
///
///
///
private void GetItemsUnderItemWithContact(PackingItem item, PackingPosition position,
out IEnumerable> itemsP1,
out IEnumerable> itemsP2,
out IEnumerable> itemsP3,
out IEnumerable> itemsP4) {
itemsP1 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z, false));
itemsP2 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z, false));
itemsP3 = GetItemsBelowForPosition(new PackingPosition(0, position.X, position.Y, position.Z + item.Depth - 1, false));
itemsP4 = GetItemsBelowForPosition(new PackingPosition(0, position.X + item.Width - 1, position.Y, position.Z + item.Depth - 1, false));
}
///
/// Returns a collection of items which are below a given point.
/// The top side of every item is at the same level as the Y-coordinate of the given position.
///
///
///
private IEnumerable> GetItemsBelowForPosition(PackingPosition position) {
return GetItemsBelow(position).Where(x => (x.Item1.Y + x.Item2.Height) == position.Y);
}
#region Weight supported
//old implementation
///
/// Checks if a given the weight of an given item is supported by the items below.
///
///
///
///
private bool IsWeightSupported(PackingItem item, PackingPosition position) {
if (position.Y == 0) {
return true;
}
var itemsBelow = Items.Where(x => Positions[x.Key].Y + x.Value.Height == position.Y)
.Select(x => new {
ItemId = x.Key,
Item = Tuple.Create(Positions[x.Key], x.Value),
Overlay = CalculateOverlay(Tuple.Create(Positions[x.Key], x.Value),
Tuple.Create(position, item))
})
.Where(x=> x.Overlay > 0);
var area = item.Width * item.Depth;
foreach (var itemBelow in itemsBelow) {
var factor = itemBelow.Overlay / area;
if (itemBelow.Item.Item2.SupportedWeightPerSquareMeter < item.Weight / area) {
return false;
}
if (!IsWeightSupportedRec(itemBelow.Item.Item2, itemBelow.ItemId, item.Weight, factor)) {
return false;
}
}
return true;
}
private bool IsWeightSupportedRec(PackingItem item, int itemId, double weigth, double factor) {
var stackedWeight = GetStackedWeightForItemId(itemId);
if (!item.SupportWeight(weigth * factor + stackedWeight)) {
return false;
}
var arcs = WeightDistirbution.Arcs.Where(x => ((VertexWithItemId)x.Source).ItemId == itemId);
foreach (var arc in arcs) {
var targetItemId = ((VertexWithItemId)arc.Target).ItemId;
var targetItem = Items[targetItemId];
if (!IsWeightSupportedRec(targetItem, targetItemId, weigth, factor * arc.Weight)) {
return false;
}
}
return true;
}
private double CalculateOverlay(Tuple item1, Tuple item2) {
var left = item1.Item1.X <= item2.Item1.X ? item1 : item2;
var right = item1.Item1.X <= item2.Item1.X ? item2 : item1;
var behind = item1.Item1.Z <= item2.Item1.Z ? item1 : item2;
var inFront = item1.Item1.Z <= item2.Item1.Z ? item2 : item1;
var overlayX = right.Item2.Width;
if (left.Item1.X + left.Item2.Width < right.Item1.X + right.Item2.Width) {
overlayX = left.Item1.X + left.Item2.Width - right.Item1.X;
}
var overlayZ = inFront.Item2.Depth;
if (behind.Item1.Z + behind.Item2.Depth < inFront.Item1.Z + inFront.Item2.Depth) {
overlayZ = behind.Item1.Z + behind.Item2.Depth - inFront.Item1.Z;
}
return overlayX * overlayZ;
}
private IEnumerable> GetItemsAboveAnItem(PackingPosition position, PackingItem item) {
var selected = Items.Select(x => new {
Item = x.Value,
Position = Positions[x.Key]
}).Where(x => x.Position.Y == position.Y + item.Height)
.Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
x.Position.X > position.X && x.Position.X < position.X + item.Width)
.Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Height > position.Z ||
x.Position.Z > position.Z && x.Position.Z < position.Z + item.Height);
return selected.Select(x => Tuple.Create(x.Position, x.Item));
}
///
/// Returns a collection of items and its position which have contact to an given item below
///
///
///
///
private IEnumerable> GetItemsUnderAnItem(PackingPosition position, PackingItem item) {
var selected = Items.Select(x => new {
Item = x.Value,
Position = Positions[x.Key]
}).Where(x => x.Position.Y + x.Item.Height == position.Y)
.Where(x => x.Position.X <= position.X && x.Position.X + x.Item.Width > position.X ||
x.Position.X > position.X && x.Position.X < position.X + item.Width)
.Where(x => x.Position.Z <= position.Z && x.Position.Z + x.Item.Depth > position.Z ||
x.Position.Z > position.Z && x.Position.Z < position.Z + item.Depth);
return selected.Select(x => Tuple.Create(x.Position, x.Item));
}
#endregion
#endregion
protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {
throw new NotImplementedException();
}
#region Get items
private IEnumerable> GetItemsBelow(PackingPosition pos) {
var line = new Line3D(pos, new Vector3D(0, 1, 0));
return Items.Select(x => new {
Item = x.Value,
Position = Positions[x.Key],
Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Top))
}).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
.Select(x => Tuple.Create(x.Position, x.Item));
}
public IEnumerable GetItemsBelow(int itemId) {
var item = Items[itemId];
var position = Positions[itemId];
var itemsBelow = Items.Where(x => Positions[x.Key].Y + x.Value.Height == position.Y &&
CalculateOverlay(Tuple.Create(Positions[x.Key], x.Value),
Tuple.Create(position, item)) > 0)
.Select(x => x.Value);
return itemsBelow;
}
#endregion
}
}