[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() {}
|
---|
[15554] | 12 |
|
---|
[15520] | 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 |
|
---|
[15554] | 19 | if (!rs1.IsZero()) {
|
---|
| 20 | residualSpaces.Add(rs1);
|
---|
| 21 | }
|
---|
[15520] | 22 |
|
---|
| 23 |
|
---|
[15554] | 24 | if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
|
---|
[15520] | 25 | residualSpaces.Add(rs2);
|
---|
| 26 | }
|
---|
[15554] | 27 | if (!rs3.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs3))) {
|
---|
[15520] | 28 | residualSpaces.Add(rs3);
|
---|
| 29 | }
|
---|
| 30 | return residualSpaces;
|
---|
| 31 | }
|
---|
| 32 |
|
---|
| 33 | private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
|
---|
| 34 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 35 |
|
---|
| 36 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 37 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 38 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 39 | return rs;
|
---|
| 40 | }
|
---|
| 41 |
|
---|
| 42 | private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
|
---|
| 43 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 44 |
|
---|
| 45 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 46 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 47 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 48 | return rs;
|
---|
| 49 | }
|
---|
| 50 |
|
---|
| 51 | private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
|
---|
| 52 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 53 |
|
---|
| 54 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 55 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 56 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 57 | return rs;
|
---|
| 58 | }
|
---|
| 59 |
|
---|
[15554] | 60 | /// <summary>
|
---|
| 61 | /// Returnst true if a given residual space and item overlaps at the x-axis
|
---|
| 62 | /// </summary>
|
---|
| 63 | /// <param name="point"></param>
|
---|
| 64 | /// <param name="residualSpace"></param>
|
---|
| 65 | /// <param name="position"></param>
|
---|
| 66 | /// <param name="item"></param>
|
---|
| 67 | /// <returns></returns>
|
---|
[15520] | 68 | private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 69 | if (point.X > position.X && point.X >= position.X + item.Width) {
|
---|
| 70 | return false;
|
---|
| 71 | }
|
---|
| 72 |
|
---|
| 73 | if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
|
---|
| 74 | return false;
|
---|
| 75 | }
|
---|
| 76 | return true;
|
---|
| 77 | }
|
---|
[15554] | 78 |
|
---|
| 79 | /// <summary>
|
---|
| 80 | /// Returnst true if a given residual space and item overlaps at the y-axis
|
---|
| 81 | /// </summary>
|
---|
| 82 | /// <param name="point"></param>
|
---|
| 83 | /// <param name="residualSpace"></param>
|
---|
| 84 | /// <param name="position"></param>
|
---|
| 85 | /// <param name="item"></param>
|
---|
[15520] | 86 | private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 87 | if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
|
---|
| 88 | return false;
|
---|
| 89 | }
|
---|
| 90 |
|
---|
| 91 | if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
|
---|
| 92 | return false;
|
---|
| 93 | }
|
---|
| 94 | return true;
|
---|
| 95 | }
|
---|
| 96 |
|
---|
[15554] | 97 | /// <summary>
|
---|
| 98 | /// Returnst true if a given residual space and item overlaps at the z-axis
|
---|
| 99 | /// </summary>
|
---|
| 100 | /// <param name="point"></param>
|
---|
| 101 | /// <param name="residualSpace"></param>
|
---|
| 102 | /// <param name="position"></param>
|
---|
| 103 | /// <param name="item"></param>
|
---|
[15520] | 104 | private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 105 | if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
|
---|
| 106 | return false;
|
---|
| 107 | }
|
---|
| 108 |
|
---|
| 109 | if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
|
---|
| 110 | return false;
|
---|
| 111 | }
|
---|
| 112 | return true;
|
---|
| 113 | }
|
---|
| 114 |
|
---|
| 115 | private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
[15554] | 116 | // if point.x >= position.x, the residual space would be located on the left side!
|
---|
[15520] | 117 | if (point.X >= position.X) {
|
---|
| 118 | return false;
|
---|
| 119 | }
|
---|
| 120 | var y = OverlapsY(point, residualSpace, position, item);
|
---|
| 121 | var z = OverlapsZ(point, residualSpace, position, item);
|
---|
| 122 | return y && z;
|
---|
| 123 | }
|
---|
| 124 |
|
---|
| 125 | private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 126 | if (point.Z >= position.Z) {
|
---|
| 127 | return false;
|
---|
| 128 | }
|
---|
| 129 | var x = OverlapsX(point, residualSpace, position, item);
|
---|
| 130 | var y = OverlapsY(point, residualSpace, position, item);
|
---|
| 131 |
|
---|
| 132 | return x && y;
|
---|
| 133 | }
|
---|
| 134 |
|
---|
| 135 | private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
|
---|
| 136 | if (point.Y >= position.Y) {
|
---|
| 137 | return false;
|
---|
| 138 | }
|
---|
| 139 | var x = OverlapsX(point, residualSpace, position, item);
|
---|
| 140 | var z = OverlapsZ(point, residualSpace, position, item);
|
---|
| 141 |
|
---|
| 142 | return x && z;
|
---|
| 143 | }
|
---|
| 144 |
|
---|
| 145 | private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 146 | if (residualSpace.IsZero()) {
|
---|
| 147 | return;
|
---|
| 148 | }
|
---|
| 149 |
|
---|
| 150 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 151 | .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
|
---|
| 152 | if (items.Count() > 0) {
|
---|
| 153 | foreach (var item in items) {
|
---|
| 154 | int newWidth = item.Position.X - point.X;
|
---|
| 155 | if (newWidth <= 0) {
|
---|
| 156 | residualSpace.SetZero();
|
---|
| 157 | return;
|
---|
| 158 | } else if (residualSpace.Width > newWidth) {
|
---|
| 159 | residualSpace.Width = newWidth;
|
---|
| 160 | }
|
---|
| 161 | }
|
---|
| 162 | }
|
---|
| 163 | }
|
---|
| 164 |
|
---|
| 165 | private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 166 | if (residualSpace.IsZero()) {
|
---|
| 167 | return;
|
---|
| 168 | }
|
---|
| 169 |
|
---|
| 170 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 171 | .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
|
---|
| 172 | if (items.Count() > 0) {
|
---|
| 173 | foreach (var item in items) {
|
---|
| 174 | int newDepth = item.Position.Z - point.Z;
|
---|
| 175 | if (newDepth <= 0) {
|
---|
| 176 | residualSpace.SetZero();
|
---|
| 177 | return;
|
---|
| 178 | } else if (residualSpace.Depth > newDepth) {
|
---|
| 179 | residualSpace.Depth = newDepth;
|
---|
| 180 | }
|
---|
| 181 | }
|
---|
| 182 | }
|
---|
| 183 | }
|
---|
| 184 |
|
---|
| 185 | private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 186 | if (residualSpace.IsZero()) {
|
---|
| 187 | return;
|
---|
| 188 | }
|
---|
| 189 |
|
---|
| 190 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 191 | .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
|
---|
| 192 | if (items.Count() > 0) {
|
---|
| 193 | foreach (var item in items) {
|
---|
| 194 | int newHeight = item.Position.Y - point.Y;
|
---|
| 195 | if (newHeight <= 0) {
|
---|
| 196 | residualSpace.SetZero();
|
---|
| 197 | return;
|
---|
| 198 | } else if (residualSpace.Height > newHeight) {
|
---|
| 199 | residualSpace.Height = newHeight;
|
---|
| 200 | }
|
---|
| 201 | }
|
---|
| 202 | }
|
---|
| 203 | }
|
---|
| 204 | }
|
---|
| 205 | }
|
---|