[15520] | 1 | using HeuristicLab.Problems.BinPacking3D.Geometry;
|
---|
| 2 | using System;
|
---|
| 3 | using System.Collections.Generic;
|
---|
| 4 | using System.Linq;
|
---|
| 5 | using System.Text;
|
---|
| 6 | using System.Threading.Tasks;
|
---|
| 7 |
|
---|
| 8 | namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
|
---|
| 9 | internal class ResidualSpaceCalculator : IResidualSpaceCalculator {
|
---|
| 10 |
|
---|
| 11 | internal ResidualSpaceCalculator() {}
|
---|
| 12 |
|
---|
| 13 | public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
|
---|
| 14 | IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
|
---|
| 15 | var rs1 = CalculateXZY(binPacking, point);
|
---|
| 16 | var rs2 = CalculateZYX(binPacking, point);
|
---|
| 17 | var rs3 = CalculateYXZ(binPacking, point);
|
---|
| 18 |
|
---|
| 19 | residualSpaces.Add(rs1);
|
---|
| 20 |
|
---|
| 21 |
|
---|
| 22 | if (!residualSpaces.Any(rs => rs.Equals(rs2))) {
|
---|
| 23 | residualSpaces.Add(rs2);
|
---|
| 24 | }
|
---|
| 25 | if (!residualSpaces.Any(rs => rs.Equals(rs3))) {
|
---|
| 26 | residualSpaces.Add(rs3);
|
---|
| 27 | }
|
---|
| 28 | return residualSpaces;
|
---|
| 29 | }
|
---|
| 30 |
|
---|
| 31 | private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
|
---|
| 32 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 33 |
|
---|
| 34 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 35 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 36 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 37 | return rs;
|
---|
| 38 | }
|
---|
| 39 |
|
---|
| 40 | private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
|
---|
| 41 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 42 |
|
---|
| 43 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 44 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 45 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 46 | return rs;
|
---|
| 47 | }
|
---|
| 48 |
|
---|
| 49 | private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
|
---|
| 50 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 51 |
|
---|
| 52 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 53 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 54 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 55 | return rs;
|
---|
| 56 | }
|
---|
| 57 |
|
---|
| 58 | private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 59 | if (point.X > position.X && point.X >= position.X + item.Width) {
|
---|
| 60 | return false;
|
---|
| 61 | }
|
---|
| 62 |
|
---|
| 63 | if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
|
---|
| 64 | return false;
|
---|
| 65 | }
|
---|
| 66 | return true;
|
---|
| 67 | }
|
---|
| 68 |
|
---|
| 69 | private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 70 | if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
|
---|
| 71 | return false;
|
---|
| 72 | }
|
---|
| 73 |
|
---|
| 74 | if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
|
---|
| 75 | return false;
|
---|
| 76 | }
|
---|
| 77 | return true;
|
---|
| 78 | }
|
---|
| 79 |
|
---|
| 80 | private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 81 | if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
|
---|
| 82 | return false;
|
---|
| 83 | }
|
---|
| 84 |
|
---|
| 85 | if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
|
---|
| 86 | return false;
|
---|
| 87 | }
|
---|
| 88 | return true;
|
---|
| 89 | }
|
---|
| 90 |
|
---|
| 91 | private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 92 | if (point.X >= position.X) {
|
---|
| 93 | return false;
|
---|
| 94 | }
|
---|
| 95 | var y = OverlapsY(point, residualSpace, position, item);
|
---|
| 96 | var z = OverlapsZ(point, residualSpace, position, item);
|
---|
| 97 | return y && z;
|
---|
| 98 | }
|
---|
| 99 |
|
---|
| 100 | private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 101 | if (point.Z >= position.Z) {
|
---|
| 102 | return false;
|
---|
| 103 | }
|
---|
| 104 | var x = OverlapsX(point, residualSpace, position, item);
|
---|
| 105 | var y = OverlapsY(point, residualSpace, position, item);
|
---|
| 106 |
|
---|
| 107 | return x && y;
|
---|
| 108 | }
|
---|
| 109 |
|
---|
| 110 | private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
|
---|
| 111 | if (point.Y >= position.Y) {
|
---|
| 112 | return false;
|
---|
| 113 | }
|
---|
| 114 | var x = OverlapsX(point, residualSpace, position, item);
|
---|
| 115 | var z = OverlapsZ(point, residualSpace, position, item);
|
---|
| 116 |
|
---|
| 117 | return x && z;
|
---|
| 118 | }
|
---|
| 119 |
|
---|
| 120 | private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 121 | if (residualSpace.IsZero()) {
|
---|
| 122 | return;
|
---|
| 123 | }
|
---|
| 124 |
|
---|
| 125 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 126 | .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
|
---|
| 127 | if (items.Count() > 0) {
|
---|
| 128 | foreach (var item in items) {
|
---|
| 129 | int newWidth = item.Position.X - point.X;
|
---|
| 130 | if (newWidth <= 0) {
|
---|
| 131 | residualSpace.SetZero();
|
---|
| 132 | return;
|
---|
| 133 | } else if (residualSpace.Width > newWidth) {
|
---|
| 134 | residualSpace.Width = newWidth;
|
---|
| 135 | }
|
---|
| 136 | }
|
---|
| 137 | }
|
---|
| 138 | }
|
---|
| 139 |
|
---|
| 140 | private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 141 | if (residualSpace.IsZero()) {
|
---|
| 142 | return;
|
---|
| 143 | }
|
---|
| 144 |
|
---|
| 145 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 146 | .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
|
---|
| 147 | if (items.Count() > 0) {
|
---|
| 148 | foreach (var item in items) {
|
---|
| 149 | int newDepth = item.Position.Z - point.Z;
|
---|
| 150 | if (newDepth <= 0) {
|
---|
| 151 | residualSpace.SetZero();
|
---|
| 152 | return;
|
---|
| 153 | } else if (residualSpace.Depth > newDepth) {
|
---|
| 154 | residualSpace.Depth = newDepth;
|
---|
| 155 | }
|
---|
| 156 | }
|
---|
| 157 | }
|
---|
| 158 | }
|
---|
| 159 |
|
---|
| 160 | private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 161 | if (residualSpace.IsZero()) {
|
---|
| 162 | return;
|
---|
| 163 | }
|
---|
| 164 |
|
---|
| 165 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 166 | .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
|
---|
| 167 | if (items.Count() > 0) {
|
---|
| 168 | foreach (var item in items) {
|
---|
| 169 | int newHeight = item.Position.Y - point.Y;
|
---|
| 170 | if (newHeight <= 0) {
|
---|
| 171 | residualSpace.SetZero();
|
---|
| 172 | return;
|
---|
| 173 | } else if (residualSpace.Height > newHeight) {
|
---|
| 174 | residualSpace.Height = newHeight;
|
---|
| 175 | }
|
---|
| 176 | }
|
---|
| 177 | }
|
---|
| 178 | }
|
---|
| 179 | }
|
---|
| 180 | }
|
---|