#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 HeuristicLab.Common; using HeuristicLab.Problems.BinPacking3D.Geometry; using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation; using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation { public abstract class ExtremePointCreator : IExtremePointCreator { public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) { UpdateExtremePoints(binPacking, item, position); UpdateResidualSpace(binPacking, item, position); } protected abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position); /// /// Updates the residual space for a given bin packing. /// /// /// /// protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position); /// /// Adds an extreme point to the bin packing. /// /// /// /// protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position); /// /// Generates new extreme points for a given item and its position. /// It also recalcualtes the residual space and removes the extreme points which are not needed any more. /// /// /// /// protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) { int newWidth = newItem.Width; int newDepth = newItem.Depth; var binShape = binPacking.BinShape; var itemPlacement = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }).ToList(); // Find ExtremePoints beginning from sourcepointX var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z }; if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) { // Projecting onto the XZ-plane var below = ProjectDown(binPacking, sourcePoint); var residualSpaces = CalculateResidualSpace(binPacking, below); if (residualSpaces.Count() > 0 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) { // add only if the projected point's residual space is not a sub-space // of another extreme point's residual space var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z); AddExtremePoint(binPacking, belowPoint); } // Projecting onto the XY-plane var back = ProjectBackward(binPacking, sourcePoint); residualSpaces = CalculateResidualSpace(binPacking, back); if (residualSpaces.Count() > 0 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) { // add only if the projected point's residual space is not a sub-space // of another extreme point's residual space var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z); AddExtremePoint(binPacking, backPoint); } } //Find ExtremePoints beginning from sourcepointY sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z); if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) { // Projecting onto the YZ-plane var left = ProjectLeft(binPacking, sourcePoint); var residualSpaces = CalculateResidualSpace(binPacking, left); if (residualSpaces.Count() > 0 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) { // add only if the projected point's residual space is not a sub-space // of another extreme point's residual space var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z); AddExtremePoint(binPacking, leftPoint); } // Projecting onto the XY-plane var back = ProjectBackward(binPacking, sourcePoint); residualSpaces = CalculateResidualSpace(binPacking, back); if (residualSpaces.Count() > 0 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) { // add only if the projected point's residual space is not a sub-space // of another extreme point's residual space var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z); AddExtremePoint(binPacking, backPoint); } } //Find ExtremePoints beginning from sourcepointZ sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth); if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) { // Projecting onto the XZ-plane var below = ProjectDown(binPacking, sourcePoint); var residualSpaces = CalculateResidualSpace(binPacking, below); if (residualSpaces.Count() > 0 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) { // add only if the projected point's residual space is not a sub-space // of another extreme point's residual space var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z); AddExtremePoint(binPacking, belowPoint); } // Projecting onto the YZ-plane var left = ProjectLeft(binPacking, sourcePoint); residualSpaces = CalculateResidualSpace(binPacking, left); if (residualSpaces.Count() > 0 && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) { // add only if the projected point's residual space is not a sub-space // of another extreme point's residual space var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z); AddExtremePoint(binPacking, leftPoint); } } } #region Get items protected IEnumerable> GetItemsAbove(BinPacking3D binPacking, PackingPosition pos) { var line = new Line3D(pos, new Vector3D(0, 1, 0)); return binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key], Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Bottom)) }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) .Select(x => Tuple.Create(x.Position, x.Item)); } protected IEnumerable> GetItemsInfront(BinPacking3D binPacking, PackingPosition pos) { var line = new Line3D(pos, new Vector3D(0, 0, 1)); return binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key], Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Back)) }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) .Select(x => Tuple.Create(x.Position, x.Item)); } protected IEnumerable> GetItemsOnRight(BinPacking3D binPacking, PackingPosition pos) { var line = new Line3D(pos, new Vector3D(1, 0, 0)); return binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key], Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Left)) }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) .Select(x => Tuple.Create(x.Position, x.Item)); } protected IEnumerable> GetItemsBelow(BinPacking3D binPacking, PackingPosition pos) { var line = new Line3D(pos, new Vector3D(0, 1, 0)); return binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key], Intersection = line.Intersect(new Plane3D(binPacking.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)); } protected IEnumerable> GetItemsBehind(BinPacking3D binPacking, PackingPosition pos) { var line = new Line3D(pos, new Vector3D(0, 0, 1)); return binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key], Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Front)) }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) .Select(x => Tuple.Create(x.Position, x.Item)); } protected IEnumerable> GetItemsOnLeft(BinPacking3D binPacking, PackingPosition pos) { var line = new Line3D(pos, new Vector3D(1, 0, 0)); return binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key], Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Right)) }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y) .Select(x => Tuple.Create(x.Position, x.Item)); } #endregion #region Residual space /// /// /// /// /// /// /// protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) { var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value)); return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value)); } /// /// /// /// /// /// /// protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable residualSpaces) { foreach (var residualSpace in residualSpaces) { if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) { return true; } } return false; } /// /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep). /// /// Given poisition /// /// Given extreme point /// /// protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable rsEp) { return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x)); } /// /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep). /// /// Given poisition /// /// Given extreme point /// /// protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) { /*old implementation return rsEp.Width >= pos.X - ep.X + rsPos.Width && rsEp.Height >= pos.Y - ep.Y + rsPos.Height && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/ var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width; var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height; var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth; return x && y && z; } /// /// Calculates the residual spaces for a given bin packing and position. /// It returns a collection of residual spaces /// /// /// /// protected abstract IEnumerable CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos); #endregion #region Projections protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) { var line = new Line3D(pos, new Vector3D(0, 0, -1)); var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }) .Select(x => new Plane3D(x.Position, x.Item, Side.Front)) .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) }) .Select(x => x.Intersect(line)) .Where(x => x != null && x.Z <= pos.Z); if (m.Where(x => x != null).Any()) { return m.MaxItems(x => x.Y).First(); } return null; } protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) { var line = new Line3D(pos, new Vector3D(-1, 0, 0)); var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }) .Select(x => new Plane3D(x.Position, x.Item, Side.Right)) .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) }) .Select(x => x.Intersect(line)) .Where(x => x != null && x.X <= pos.X); if (m.Where(x => x != null).Any()) { return m.MaxItems(x => x.Y).First(); } return null; } protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) { var line = new Line3D(pos, new Vector3D(0, -1, 0)); var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }) .Select(x => new Plane3D(x.Position, x.Item, Side.Top)) .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) }) .Select(x => x.Intersect(line)) .Where(x => x != null && x.Y <= pos.Y); if (m.Where(x => x != null).Any()) { return m.MaxItems(x => x.Y).First(); } return null; } protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) { var line = new Line3D(pos, new Vector3D(0, 0, 1)); var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }) .Select(x => new Plane3D(x.Position, x.Item, Side.Back)) .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) }) .Select(x => x.Intersect(line)) .Where(x => x != null && x.Z >= pos.Z); if (m.Where(x => x != null).Any()) { return m.MaxItems(x => x.Y).First(); } return null; } protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) { var line = new Line3D(pos, new Vector3D(1, 0, 0)); var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }) .Select(x => new Plane3D(x.Position, x.Item, Side.Left)) .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) }) .Select(x => x.Intersect(line)) .Where(x => x != null && x.X >= pos.X); if (m.Where(x => x != null).Any()) { return m.MaxItems(x => x.Y).First(); } return null; } protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) { var line = new Line3D(pos, new Vector3D(0, 1, 0)); var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }) .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom)) .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) }) .Select(x => x.Intersect(line)) .Where(x => x != null && x.Y >= pos.Y); if (m.Where(x => x != null).Any()) { return m.MaxItems(x => x.Y).First(); } return null; } #endregion } }