[15617] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
| 3 | * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
| 4 | *
|
---|
| 5 | * This file is part of HeuristicLab.
|
---|
| 6 | *
|
---|
| 7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
| 8 | * it under the terms of the GNU General Public License as published by
|
---|
| 9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
| 10 | * (at your option) any later version.
|
---|
| 11 | *
|
---|
| 12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
| 13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
| 14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
| 15 | * GNU General Public License for more details.
|
---|
| 16 | *
|
---|
| 17 | * You should have received a copy of the GNU General Public License
|
---|
| 18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
| 19 | */
|
---|
| 20 | #endregion
|
---|
| 21 |
|
---|
| 22 | using HeuristicLab.Problems.BinPacking3D.Geometry;
|
---|
[15520] | 23 | using System;
|
---|
| 24 | using System.Collections.Generic;
|
---|
| 25 | using System.Linq;
|
---|
| 26 | using System.Text;
|
---|
| 27 | using System.Threading.Tasks;
|
---|
| 28 |
|
---|
| 29 | namespace HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation {
|
---|
| 30 | internal class ResidualSpaceCalculator : IResidualSpaceCalculator {
|
---|
| 31 |
|
---|
| 32 | internal ResidualSpaceCalculator() {}
|
---|
[15554] | 33 |
|
---|
[15520] | 34 | public IEnumerable<ResidualSpace> CalculateResidualSpaces(BinPacking3D binPacking, Vector3D point) {
|
---|
| 35 | IList<ResidualSpace> residualSpaces = new List<ResidualSpace>();
|
---|
| 36 | var rs1 = CalculateXZY(binPacking, point);
|
---|
| 37 | var rs2 = CalculateZYX(binPacking, point);
|
---|
| 38 | var rs3 = CalculateYXZ(binPacking, point);
|
---|
| 39 |
|
---|
[15554] | 40 | if (!rs1.IsZero()) {
|
---|
| 41 | residualSpaces.Add(rs1);
|
---|
[15585] | 42 | }
|
---|
[15520] | 43 |
|
---|
[15554] | 44 | if (!rs2.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs2))) {
|
---|
[15520] | 45 | residualSpaces.Add(rs2);
|
---|
| 46 | }
|
---|
[15554] | 47 | if (!rs3.IsZero() && !residualSpaces.Any(rs => rs.Equals(rs3))) {
|
---|
[15520] | 48 | residualSpaces.Add(rs3);
|
---|
| 49 | }
|
---|
| 50 | return residualSpaces;
|
---|
| 51 | }
|
---|
| 52 |
|
---|
[15585] | 53 | /// <summary>
|
---|
| 54 | /// Calculates a resiual space by expanding to the limits of the axis in the following order:
|
---|
| 55 | /// 1. x
|
---|
| 56 | /// 2. z
|
---|
| 57 | /// 3. y
|
---|
| 58 | /// </summary>
|
---|
| 59 | /// <param name="binPacking"></param>
|
---|
| 60 | /// <param name="point"></param>
|
---|
| 61 | /// <returns></returns>
|
---|
[15520] | 62 | private ResidualSpace CalculateXZY(BinPacking3D binPacking, Vector3D point) {
|
---|
| 63 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 64 |
|
---|
| 65 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 66 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 67 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 68 | return rs;
|
---|
| 69 | }
|
---|
| 70 |
|
---|
[15585] | 71 | /// <summary>
|
---|
| 72 | /// Calculates a resiual space by expanding to the limits of the axis in the following order:
|
---|
| 73 | /// 1. z
|
---|
| 74 | /// 2. y
|
---|
| 75 | /// 3. x
|
---|
| 76 | /// </summary>
|
---|
| 77 | /// <param name="binPacking"></param>
|
---|
| 78 | /// <param name="point"></param>
|
---|
| 79 | /// <returns></returns>
|
---|
[15520] | 80 | private ResidualSpace CalculateZYX(BinPacking3D binPacking, Vector3D point) {
|
---|
| 81 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 82 |
|
---|
| 83 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 84 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 85 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 86 | return rs;
|
---|
| 87 | }
|
---|
| 88 |
|
---|
[15585] | 89 | /// <summary>
|
---|
| 90 | /// Calculates a resiual space by expanding to the limits of the axis in the following order:
|
---|
| 91 | /// 1. y
|
---|
| 92 | /// 2. x
|
---|
| 93 | /// 3. z
|
---|
| 94 | /// </summary>
|
---|
| 95 | /// <param name="binPacking"></param>
|
---|
| 96 | /// <param name="point"></param>
|
---|
| 97 | /// <returns></returns>
|
---|
[15520] | 98 | private ResidualSpace CalculateYXZ(BinPacking3D binPacking, Vector3D point) {
|
---|
| 99 | ResidualSpace rs = new ResidualSpace(binPacking, point);
|
---|
| 100 |
|
---|
| 101 | LimitResidualSpaceAbove(binPacking, point, rs);
|
---|
| 102 | LimitResidualSpaceOnRight(binPacking, point, rs);
|
---|
| 103 | LimitResidualSpaceInFront(binPacking, point, rs);
|
---|
| 104 | return rs;
|
---|
| 105 | }
|
---|
| 106 |
|
---|
[15554] | 107 | /// <summary>
|
---|
| 108 | /// Returnst true if a given residual space and item overlaps at the x-axis
|
---|
| 109 | /// </summary>
|
---|
| 110 | /// <param name="point"></param>
|
---|
| 111 | /// <param name="residualSpace"></param>
|
---|
| 112 | /// <param name="position"></param>
|
---|
| 113 | /// <param name="item"></param>
|
---|
| 114 | /// <returns></returns>
|
---|
[15520] | 115 | private bool OverlapsX(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 116 | if (point.X > position.X && point.X >= position.X + item.Width) {
|
---|
| 117 | return false;
|
---|
| 118 | }
|
---|
| 119 |
|
---|
| 120 | if (point.X <= position.X && position.X >= point.X + residualSpace.Width) {
|
---|
| 121 | return false;
|
---|
| 122 | }
|
---|
| 123 | return true;
|
---|
| 124 | }
|
---|
[15554] | 125 |
|
---|
| 126 | /// <summary>
|
---|
| 127 | /// Returnst true if a given residual space and item overlaps at the y-axis
|
---|
| 128 | /// </summary>
|
---|
| 129 | /// <param name="point"></param>
|
---|
| 130 | /// <param name="residualSpace"></param>
|
---|
| 131 | /// <param name="position"></param>
|
---|
| 132 | /// <param name="item"></param>
|
---|
[15520] | 133 | private bool OverlapsY(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 134 | if (point.Y > position.Y && point.Y >= position.Y + item.Height) {
|
---|
| 135 | return false;
|
---|
| 136 | }
|
---|
| 137 |
|
---|
| 138 | if (point.Y <= position.Y && position.Y >= point.Y + residualSpace.Height) {
|
---|
| 139 | return false;
|
---|
| 140 | }
|
---|
| 141 | return true;
|
---|
| 142 | }
|
---|
| 143 |
|
---|
[15554] | 144 | /// <summary>
|
---|
| 145 | /// Returnst true if a given residual space and item overlaps at the z-axis
|
---|
| 146 | /// </summary>
|
---|
| 147 | /// <param name="point"></param>
|
---|
| 148 | /// <param name="residualSpace"></param>
|
---|
| 149 | /// <param name="position"></param>
|
---|
| 150 | /// <param name="item"></param>
|
---|
[15520] | 151 | private bool OverlapsZ(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 152 | if (point.Z > position.Z && point.Z >= position.Z + item.Depth) {
|
---|
| 153 | return false;
|
---|
| 154 | }
|
---|
| 155 |
|
---|
| 156 | if (point.Z <= position.Z && position.Z >= point.Z + residualSpace.Depth) {
|
---|
| 157 | return false;
|
---|
| 158 | }
|
---|
| 159 | return true;
|
---|
| 160 | }
|
---|
| 161 |
|
---|
| 162 | private bool OverlapsOnRight(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
[15585] | 163 | // if point.x >= position.x => the residual space is being located on the left side!
|
---|
[15520] | 164 | if (point.X >= position.X) {
|
---|
| 165 | return false;
|
---|
| 166 | }
|
---|
| 167 | var y = OverlapsY(point, residualSpace, position, item);
|
---|
| 168 | var z = OverlapsZ(point, residualSpace, position, item);
|
---|
| 169 | return y && z;
|
---|
| 170 | }
|
---|
| 171 |
|
---|
| 172 | private bool OverlapsInFront(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item) {
|
---|
| 173 | if (point.Z >= position.Z) {
|
---|
| 174 | return false;
|
---|
| 175 | }
|
---|
| 176 | var x = OverlapsX(point, residualSpace, position, item);
|
---|
| 177 | var y = OverlapsY(point, residualSpace, position, item);
|
---|
| 178 |
|
---|
| 179 | return x && y;
|
---|
| 180 | }
|
---|
| 181 |
|
---|
[15585] | 182 |
|
---|
[15520] | 183 | private bool OverlapsAbove(Vector3D point, ResidualSpace residualSpace, PackingPosition position, PackingItem item ) {
|
---|
| 184 | if (point.Y >= position.Y) {
|
---|
| 185 | return false;
|
---|
| 186 | }
|
---|
| 187 | var x = OverlapsX(point, residualSpace, position, item);
|
---|
| 188 | var z = OverlapsZ(point, residualSpace, position, item);
|
---|
| 189 |
|
---|
| 190 | return x && z;
|
---|
| 191 | }
|
---|
[15585] | 192 |
|
---|
| 193 | /// <summary>
|
---|
| 194 | /// Recalculates the width of a given residual space.
|
---|
| 195 | /// The new width is being limited by any item right of the residual space or the dimension of the bin shape.
|
---|
| 196 | /// If the new width is zero, the whole residual space is being set to zero.
|
---|
| 197 | /// </summary>
|
---|
| 198 | /// <param name="binPacking"></param>
|
---|
| 199 | /// <param name="point"></param>
|
---|
| 200 | /// <param name="residualSpace"></param>
|
---|
[15520] | 201 | private void LimitResidualSpaceOnRight(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 202 | if (residualSpace.IsZero()) {
|
---|
| 203 | return;
|
---|
| 204 | }
|
---|
| 205 |
|
---|
| 206 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 207 | .Where(item => OverlapsOnRight(point, residualSpace, item.Position, item.Dimension));
|
---|
| 208 | if (items.Count() > 0) {
|
---|
| 209 | foreach (var item in items) {
|
---|
| 210 | int newWidth = item.Position.X - point.X;
|
---|
| 211 | if (newWidth <= 0) {
|
---|
| 212 | residualSpace.SetZero();
|
---|
| 213 | return;
|
---|
| 214 | } else if (residualSpace.Width > newWidth) {
|
---|
| 215 | residualSpace.Width = newWidth;
|
---|
| 216 | }
|
---|
| 217 | }
|
---|
| 218 | }
|
---|
| 219 | }
|
---|
| 220 |
|
---|
[15585] | 221 | /// <summary>
|
---|
| 222 | /// Recalculates the depth of a given residual space.
|
---|
| 223 | /// The new depth is being limited by any item in front of the residual space or the dimension of the bin shape.
|
---|
| 224 | /// If the new depth is zero, the whole residual space is being set to zero.
|
---|
| 225 | /// </summary>
|
---|
| 226 | /// <param name="binPacking"></param>
|
---|
| 227 | /// <param name="point"></param>
|
---|
| 228 | /// <param name="residualSpace"></param>
|
---|
[15520] | 229 | private void LimitResidualSpaceInFront(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 230 | if (residualSpace.IsZero()) {
|
---|
| 231 | return;
|
---|
| 232 | }
|
---|
| 233 |
|
---|
| 234 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 235 | .Where(item => OverlapsInFront(point, residualSpace, item.Position, item.Dimension));
|
---|
| 236 | if (items.Count() > 0) {
|
---|
| 237 | foreach (var item in items) {
|
---|
| 238 | int newDepth = item.Position.Z - point.Z;
|
---|
| 239 | if (newDepth <= 0) {
|
---|
| 240 | residualSpace.SetZero();
|
---|
| 241 | return;
|
---|
| 242 | } else if (residualSpace.Depth > newDepth) {
|
---|
| 243 | residualSpace.Depth = newDepth;
|
---|
| 244 | }
|
---|
| 245 | }
|
---|
| 246 | }
|
---|
| 247 | }
|
---|
| 248 |
|
---|
[15585] | 249 | /// <summary>
|
---|
| 250 | /// Recalculates the height of a given residual space.
|
---|
| 251 | /// The new height is being limited by any item above the residual space or the dimension of the bin shape.
|
---|
| 252 | /// If the new height is zero, the whole residual space is being set to zero.
|
---|
| 253 | /// </summary>
|
---|
| 254 | /// <param name="binPacking"></param>
|
---|
| 255 | /// <param name="point"></param>
|
---|
| 256 | /// <param name="residualSpace"></param>
|
---|
[15520] | 257 | private void LimitResidualSpaceAbove(BinPacking3D binPacking, Vector3D point, ResidualSpace residualSpace) {
|
---|
| 258 | if (residualSpace.IsZero()) {
|
---|
| 259 | return;
|
---|
| 260 | }
|
---|
| 261 |
|
---|
| 262 | var items = binPacking.Items.Select(item => new { Dimension = item.Value, Position = binPacking.Positions[item.Key] })
|
---|
| 263 | .Where(item => OverlapsAbove(point, residualSpace, item.Position, item.Dimension));
|
---|
| 264 | if (items.Count() > 0) {
|
---|
| 265 | foreach (var item in items) {
|
---|
| 266 | int newHeight = item.Position.Y - point.Y;
|
---|
| 267 | if (newHeight <= 0) {
|
---|
| 268 | residualSpace.SetZero();
|
---|
| 269 | return;
|
---|
| 270 | } else if (residualSpace.Height > newHeight) {
|
---|
| 271 | residualSpace.Height = newHeight;
|
---|
| 272 | }
|
---|
| 273 | }
|
---|
| 274 | }
|
---|
| 275 | }
|
---|
| 276 | }
|
---|
| 277 | }
|
---|