[15488] | 1 | using HeuristicLab.Common;
|
---|
| 2 | using HeuristicLab.Problems.BinPacking3D.Geometry;
|
---|
| 3 | using System;
|
---|
| 4 | using System.Collections.Generic;
|
---|
| 5 | using System.Linq;
|
---|
| 6 | using System.Text;
|
---|
| 7 | using System.Threading.Tasks;
|
---|
| 8 |
|
---|
| 9 | namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
|
---|
| 10 |
|
---|
| 11 | /// <summary>
|
---|
| 12 | /// This extreme point creation class uses the point projection based method by Crainic, T. G., Perboli, G., & Tadei, R. for creating extreme points.
|
---|
| 13 | /// Each extreme point of an item is being projectet backwards, downwards and to the left.
|
---|
| 14 | /// A new extreme point will be created where this projections instersects with another item or the bin boundins.
|
---|
| 15 | /// </summary>
|
---|
| 16 | public class PointProjectionBasedEPCreator : ExtremePointCreator {
|
---|
[15520] | 17 | protected override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 18 | GenerateNewExtremePointsForItem(binPacking, item, position);
|
---|
[15488] | 19 |
|
---|
| 20 | // if an item is fit in below, before, or left of another its extreme points have to be regenerated
|
---|
| 21 | foreach (var above in GetItemsAbove(binPacking, position)) {
|
---|
[15520] | 22 | GenerateNewExtremePointsForItem(binPacking, above.Item2, above.Item1);
|
---|
[15488] | 23 | }
|
---|
| 24 | foreach (var front in GetItemsInfront(binPacking, position)) {
|
---|
[15520] | 25 | GenerateNewExtremePointsForItem(binPacking, front.Item2, front.Item1);
|
---|
[15488] | 26 | }
|
---|
| 27 | foreach (var right in GetItemsOnRight(binPacking, position)) {
|
---|
[15520] | 28 | GenerateNewExtremePointsForItem(binPacking, right.Item2, right.Item1);
|
---|
[15488] | 29 | }
|
---|
| 30 | }
|
---|
| 31 |
|
---|
[15520] | 32 | protected override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
[15488] | 33 | foreach (var ep in binPacking.ExtremePoints.ToList()) {
|
---|
[15520] | 34 | var rs = binPacking.ResidualSpaces[ep];
|
---|
[15488] | 35 | var depth = position.Rotated ? item.Width : item.Depth;
|
---|
| 36 | var width = position.Rotated ? item.Depth : item.Width;
|
---|
| 37 | var changed = false;
|
---|
| 38 | if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
|
---|
| 39 | if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
|
---|
| 40 | var diff = position.X - ep.X;
|
---|
[15520] | 41 | var newRSX = Math.Min(rs.Width, diff);
|
---|
| 42 | rs = ResidualSpace.Create(newRSX, rs.Height, rs.Depth);
|
---|
[15488] | 43 | changed = true;
|
---|
| 44 | }
|
---|
| 45 | if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
|
---|
| 46 | var diff = position.Y - ep.Y;
|
---|
[15520] | 47 | var newRSY = Math.Min(rs.Height, diff);
|
---|
| 48 | rs = ResidualSpace.Create(rs.Width, newRSY, rs.Depth);
|
---|
[15488] | 49 | changed = true;
|
---|
| 50 | }
|
---|
| 51 | }
|
---|
| 52 |
|
---|
| 53 | if (ep.Z <= position.Z &&
|
---|
| 54 | ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
|
---|
| 55 | ep.X >= position.X && ep.X < position.X + width) {
|
---|
| 56 | var diff = position.Z - ep.Z;
|
---|
[15520] | 57 | var newRSZ = Math.Min(rs.Depth, diff);
|
---|
| 58 | rs = ResidualSpace.Create(rs.Width, rs.Height, newRSZ);
|
---|
[15488] | 59 | changed = true;
|
---|
| 60 | }
|
---|
| 61 |
|
---|
| 62 | if (changed) {
|
---|
[15520] | 63 | if (!rs.IsZero() && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
|
---|
| 64 | binPacking.ResidualSpaces[ep] = rs;
|
---|
[15488] | 65 | } else {
|
---|
| 66 | binPacking.ExtremePoints.Remove(ep);
|
---|
[15520] | 67 | binPacking.ResidualSpaces.Remove(ep);
|
---|
[15488] | 68 | }
|
---|
| 69 | }
|
---|
| 70 | }
|
---|
| 71 | return;
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | /// <summary>
|
---|
| 75 | /// Adds an extreme point to a given bin packing.
|
---|
| 76 | /// It also adds the residual space for the new extreme point
|
---|
| 77 | /// and removes the extreme point and the related residual space for the given position which are not needed anymore.
|
---|
| 78 | /// </summary>
|
---|
| 79 | /// <param name="binPacking"></param>
|
---|
| 80 | /// <param name="position"></param>
|
---|
| 81 | /// <returns></returns>
|
---|
| 82 | protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
|
---|
| 83 | if (binPacking.ExtremePoints.Add(position)) {
|
---|
| 84 | var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
|
---|
[15520] | 85 | binPacking.ResidualSpaces.Add(position, rs);
|
---|
[15488] | 86 | // Check if the existing extreme points are shadowed by the new point
|
---|
| 87 | // This is, their residual space fit entirely into the residual space of the new point
|
---|
| 88 | foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
|
---|
[15520] | 89 | if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpaces[ep], position, rs)) {
|
---|
[15488] | 90 | binPacking.ExtremePoints.Remove(ep);
|
---|
[15520] | 91 | binPacking.ResidualSpaces.Remove(ep);
|
---|
[15488] | 92 | }
|
---|
| 93 | }
|
---|
| 94 | return true;
|
---|
| 95 | }
|
---|
| 96 | return false;
|
---|
| 97 | }
|
---|
| 98 | }
|
---|
| 99 | }
|
---|