[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 | /// <summary>
|
---|
| 11 | /// This extreme point creation class uses the line projection based method for creating extreme points.
|
---|
| 12 | /// </summary>
|
---|
| 13 | public class LineProjectionBasedEPCreator : ExtremePointCreator {
|
---|
| 14 |
|
---|
| 15 |
|
---|
| 16 |
|
---|
| 17 |
|
---|
| 18 | public override void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 19 | // Before any extreme point for an item can be created, each residual space must be resized if the new item is in the residual space.
|
---|
| 20 | // If the residual spaces were not updated, it could be that an extreme point won't be generated because it lies in a residual space which
|
---|
| 21 | // size isn't correct anymore.
|
---|
| 22 | RecalculateResidualSpaces(binPacking, item, position);
|
---|
| 23 |
|
---|
| 24 | GenerateNewExtremePointsForNewItem(binPacking, item, position);
|
---|
| 25 |
|
---|
| 26 | foreach (var ep in GetEpsOnLeft(binPacking, item, position)) {
|
---|
| 27 | AddExtremePoint(binPacking, ep);
|
---|
| 28 | }
|
---|
| 29 |
|
---|
| 30 | foreach (var ep in GetEpsBelow(binPacking, item, position)) {
|
---|
| 31 | AddExtremePoint(binPacking, ep);
|
---|
| 32 | }
|
---|
| 33 |
|
---|
| 34 | foreach (var ep in GetEpsBehind(binPacking, item, position)) {
|
---|
| 35 | AddExtremePoint(binPacking, ep);
|
---|
| 36 | }
|
---|
| 37 | }
|
---|
| 38 |
|
---|
| 39 | /// <summary>
|
---|
| 40 | /// Returns true, if the given poisition and the related residual space is within the residual space of the given extreme point
|
---|
| 41 | /// </summary>
|
---|
| 42 | /// <param name="pos">New Position</param>
|
---|
| 43 | /// <param name="rsPos"></param>
|
---|
| 44 | /// <param name="ep"></param>
|
---|
| 45 | /// <param name="rsEp"></param>
|
---|
| 46 | /// <returns></returns>
|
---|
| 47 | protected override bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
|
---|
| 48 | bool x = pos.X >= ep.X && rsPos.Item1 + pos.X <= rsEp.Item1 + ep.X;
|
---|
| 49 | bool y = (pos.Y >= ep.Y && pos.Y == 0 || pos.Y > ep.Y && pos.Y > 0) && rsPos.Item2 + pos.Y <= rsEp.Item2 + ep.Y;
|
---|
| 50 | bool z = pos.Z >= ep.Z && rsPos.Item3 + pos.Z <= rsEp.Item3 + ep.Z;
|
---|
| 51 | return x && y && z;
|
---|
| 52 | }
|
---|
| 53 |
|
---|
| 54 | public override void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 55 | foreach (var ep in binPacking.ExtremePoints.ToList()) {
|
---|
| 56 | var rs = binPacking.ResidualSpace[ep];
|
---|
| 57 | var depth = position.Rotated ? item.Width : item.Depth;
|
---|
| 58 | var width = position.Rotated ? item.Depth : item.Width;
|
---|
| 59 | var changed = false;
|
---|
| 60 | if (ep.Z >= position.Z && ep.Z < position.Z + depth) {
|
---|
| 61 | if (ep.X <= position.X && ep.Y >= position.Y && ep.Y < position.Y + item.Height) {
|
---|
| 62 | var diff = position.X - ep.X;
|
---|
| 63 | var newRSX = Math.Min(rs.Item1, diff);
|
---|
| 64 | rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);
|
---|
| 65 | changed = true;
|
---|
| 66 | }
|
---|
| 67 | if (ep.Y <= position.Y && ep.X >= position.X && ep.X < position.X + width) {
|
---|
| 68 | var diff = position.Y - ep.Y;
|
---|
| 69 | var newRSY = Math.Min(rs.Item2, diff);
|
---|
| 70 | rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);
|
---|
| 71 | changed = true;
|
---|
| 72 | }
|
---|
| 73 | }
|
---|
| 74 |
|
---|
| 75 | if (ep.Z <= position.Z &&
|
---|
| 76 | ep.Y >= position.Y && ep.Y < position.Y + item.Height &&
|
---|
| 77 | ep.X >= position.X && ep.X < position.X + width) {
|
---|
| 78 | var diff = position.Z - ep.Z;
|
---|
| 79 | var newRSZ = Math.Min(rs.Item3, diff);
|
---|
| 80 | rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);
|
---|
| 81 | changed = true;
|
---|
| 82 | }
|
---|
| 83 |
|
---|
| 84 | if (changed) {
|
---|
| 85 | if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, new Vector3D(ep), rs)) {
|
---|
| 86 | binPacking.ResidualSpace[ep] = rs;
|
---|
| 87 | } else {
|
---|
| 88 | binPacking.ExtremePoints.Remove(ep);
|
---|
| 89 | binPacking.ResidualSpace.Remove(ep);
|
---|
| 90 | }
|
---|
| 91 | }
|
---|
| 92 | }
|
---|
| 93 | return;
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | protected override bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position) {
|
---|
| 97 | if (binPacking.ExtremePoints.Add(position)) {
|
---|
| 98 | var rs = CalculateResidualSpace(binPacking, new Vector3D(position));
|
---|
| 99 | binPacking.ResidualSpace.Add(position, rs);
|
---|
| 100 | // Check if the existing extreme points are shadowed by the new point
|
---|
| 101 | // This is, their residual space fit entirely into the residual space of the new point
|
---|
| 102 | foreach (var ep in binPacking.ExtremePoints.Where(x => x != position && new Vector3D(x).IsInside(position, rs)).ToList()) {
|
---|
| 103 | if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), binPacking.ResidualSpace[ep], position, rs)) {
|
---|
| 104 | binPacking.ExtremePoints.Remove(ep);
|
---|
| 105 | binPacking.ResidualSpace.Remove(ep);
|
---|
| 106 | }
|
---|
| 107 | }
|
---|
| 108 | return true;
|
---|
| 109 | }
|
---|
| 110 | return false;
|
---|
| 111 | }
|
---|
| 112 |
|
---|
| 113 | /// <summary>
|
---|
| 114 | /// Returns true if an item is in the residual space of a given extrem point
|
---|
| 115 | /// </summary>
|
---|
| 116 | /// <param name="rs">KeyValuePair with the position of the extreme point and the size of the residual space</param>
|
---|
| 117 | /// <param name="item">Given Item</param>
|
---|
| 118 | /// <param name="position">Given position</param>
|
---|
| 119 | /// <returns></returns>
|
---|
| 120 | private bool ItemIsInRs(KeyValuePair<PackingPosition, Tuple<int, int, int>> rs, PackingItem item, PackingPosition position) {
|
---|
| 121 | return GetVertices(item, position).Where(pos => pos.IsInside(rs.Key, rs.Value)).Any();
|
---|
| 122 | }
|
---|
| 123 |
|
---|
| 124 | /// <summary>
|
---|
| 125 | /// Recalculates the residual spaces if needed.
|
---|
| 126 | /// It checks if an item is in an residual space and if so the residual space will be recalculated
|
---|
| 127 | /// </summary>
|
---|
| 128 | /// <param name="binPacking"></param>
|
---|
| 129 | /// <param name="item"></param>
|
---|
| 130 | /// <param name="position"></param>
|
---|
| 131 | private void RecalculateResidualSpaces(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 132 | var recalculatedSpaces = new Dictionary<PackingPosition, Tuple<int, int, int>>();
|
---|
| 133 | foreach (var rs in binPacking.ResidualSpace) {
|
---|
| 134 | int width = rs.Value.Item1;
|
---|
| 135 | int height = rs.Value.Item2;
|
---|
| 136 | int depth = rs.Value.Item3;
|
---|
| 137 |
|
---|
| 138 | if (ItemIsInRs(rs, item, position)) {
|
---|
| 139 | if (rs.Key.X + rs.Value.Item1 > position.X) {
|
---|
| 140 | width = position.X - rs.Key.X;
|
---|
| 141 | } else if (rs.Key.Y + rs.Value.Item2 > position.Y) {
|
---|
| 142 | height = position.Y - rs.Key.Y;
|
---|
| 143 | } else if (rs.Key.Z + rs.Value.Item3 > position.Z) {
|
---|
| 144 | depth = position.Z - rs.Key.Z;
|
---|
| 145 | }
|
---|
| 146 | }
|
---|
| 147 |
|
---|
| 148 | var newRs = new Tuple<int, int, int>(width, height, depth);
|
---|
| 149 | if (IsNonZero(newRs)) {
|
---|
| 150 | recalculatedSpaces.Add(rs.Key, newRs);
|
---|
| 151 | } else {
|
---|
| 152 | recalculatedSpaces.Add(rs.Key, rs.Value);
|
---|
| 153 | }
|
---|
| 154 | }
|
---|
| 155 | binPacking.ResidualSpace = recalculatedSpaces;
|
---|
| 156 | }
|
---|
| 157 |
|
---|
| 158 | /// <summary>
|
---|
| 159 | /// Returns the extremepoints on the left side of an given item
|
---|
| 160 | /// </summary>
|
---|
| 161 | /// <param name="item"></param>
|
---|
| 162 | /// <param name="position"></param>
|
---|
| 163 | /// <returns></returns>
|
---|
| 164 | private IList<PackingPosition> GetEpsOnLeft(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 165 | IList<PackingPosition> eps = new List<PackingPosition>();
|
---|
| 166 | IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsOnLeft(binPacking, position);
|
---|
| 167 | var edges = GetProjectionEdgesOnLeft(item, position);
|
---|
| 168 |
|
---|
| 169 | foreach (var i in items) {
|
---|
| 170 | foreach (var edge in edges) {
|
---|
| 171 | var newEps = IntersectionsForItem(edge, GetEdgesOnRight(i.Item2, i.Item1));
|
---|
| 172 | foreach (var ep in newEps) {
|
---|
| 173 | try {
|
---|
| 174 | if (ep.X < binPacking.BinShape.Width && ep.Y < binPacking.BinShape.Height && ep.Z < binPacking.BinShape.Depth) {
|
---|
| 175 | var point = ProjectLeft(binPacking, ep);
|
---|
| 176 | var residualSpace = CalculateResidualSpace(binPacking, point);
|
---|
| 177 | if (IsNonZero(residualSpace)) {
|
---|
| 178 | eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
|
---|
| 179 | }
|
---|
| 180 | }
|
---|
| 181 | } catch {
|
---|
| 182 | var s = ep;
|
---|
| 183 | }
|
---|
| 184 | }
|
---|
| 185 | }
|
---|
| 186 | }
|
---|
| 187 | return eps;
|
---|
| 188 | }
|
---|
| 189 |
|
---|
| 190 | /// <summary>
|
---|
| 191 | /// Returns the extremepoints below of an given item
|
---|
| 192 | /// </summary>
|
---|
| 193 | /// <param name="item"></param>
|
---|
| 194 | /// <param name="position"></param>
|
---|
| 195 | /// <returns></returns>
|
---|
| 196 | private IList<PackingPosition> GetEpsBelow(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 197 | IList<PackingPosition> eps = new List<PackingPosition>();
|
---|
| 198 | IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBelow(binPacking, position);
|
---|
| 199 | var edges = GetProjectionEdgesBelow(item, position);
|
---|
| 200 |
|
---|
| 201 | foreach (var i in items) {
|
---|
| 202 | foreach (var edge in edges) {
|
---|
| 203 | var newEps = IntersectionsForItem(edge, GetEdgesOnTop(i.Item2, i.Item1));
|
---|
| 204 | foreach (var ep in newEps) {
|
---|
| 205 | try {
|
---|
| 206 | var point = ProjectDown(binPacking, ep);
|
---|
| 207 | var residualSpace = CalculateResidualSpace(binPacking, point);
|
---|
| 208 | if (IsNonZero(residualSpace)) {
|
---|
| 209 | eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
|
---|
| 210 | }
|
---|
| 211 | } catch {
|
---|
| 212 | var s = ep;
|
---|
| 213 | }
|
---|
| 214 | }
|
---|
| 215 | }
|
---|
| 216 | }
|
---|
| 217 | return eps;
|
---|
| 218 | }
|
---|
| 219 |
|
---|
| 220 | /// <summary>
|
---|
| 221 | /// Returns the extremepoints on the left side of an given item
|
---|
| 222 | /// </summary>
|
---|
| 223 | /// <param name="item"></param>
|
---|
| 224 | /// <param name="position"></param>
|
---|
| 225 | /// <returns></returns>
|
---|
| 226 | private IList<PackingPosition> GetEpsBehind(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 227 | IList<PackingPosition> eps = new List<PackingPosition>();
|
---|
| 228 | IEnumerable<Tuple<PackingPosition, PackingItem>> items = GetItemsBehind(binPacking, position);
|
---|
| 229 | var edges = GetProjectionEdgesBehind(item, position);
|
---|
| 230 |
|
---|
| 231 | foreach (var i in items) {
|
---|
| 232 | foreach (var edge in edges) {
|
---|
| 233 | var newEps = IntersectionsForItem(edge, GetEdgesInFront(i.Item2, i.Item1));
|
---|
| 234 | foreach (var ep in newEps) {
|
---|
| 235 | try {
|
---|
| 236 | var point = ProjectBackward(binPacking, ep);
|
---|
| 237 | var residualSpace = CalculateResidualSpace(binPacking, point);
|
---|
| 238 | if (IsNonZero(residualSpace)) {
|
---|
| 239 | eps.Add(new PackingPosition(position.AssignedBin, point.X, point.Y, point.Z));
|
---|
| 240 | }
|
---|
| 241 | } catch {
|
---|
| 242 | var s = ep;
|
---|
| 243 | }
|
---|
| 244 | }
|
---|
| 245 | }
|
---|
| 246 | }
|
---|
| 247 | return eps;
|
---|
| 248 | }
|
---|
| 249 |
|
---|
| 250 | #region Methods for getting the edges for items
|
---|
| 251 |
|
---|
| 252 | /// <summary>
|
---|
| 253 | /// Returns an array of packing position which represents the vertices of an item.
|
---|
| 254 | /// The position of a vertex in the array is mapped to an item as followed:
|
---|
| 255 | /// 4----------5
|
---|
| 256 | /// /| /|
|
---|
| 257 | /// / | / |
|
---|
| 258 | /// / 0-------/--1
|
---|
| 259 | /// 6--/-------7 /
|
---|
| 260 | /// | / | /
|
---|
| 261 | /// |/ |/
|
---|
| 262 | /// 2----------3
|
---|
| 263 | ///
|
---|
| 264 | /// 0 = (0,0,0)
|
---|
| 265 | /// </summary>
|
---|
| 266 | /// <param name="item"></param>
|
---|
| 267 | /// <param name="position"></param>
|
---|
| 268 | /// <returns></returns>
|
---|
| 269 | private Vector3D[] GetVertices(PackingItem item, PackingPosition position) {
|
---|
| 270 | int width = position.Rotated ? item.Depth : item.Width;
|
---|
| 271 | int depth = position.Rotated ? item.Width : item.Depth;
|
---|
| 272 | return new Vector3D[] {
|
---|
| 273 | new Vector3D(position.X + 0, position.Y + 0, position.Z + 0), // (0,0,0)
|
---|
| 274 | new Vector3D(position.X + width, position.Y + 0, position.Z + 0), // (x,0,0)
|
---|
| 275 | new Vector3D(position.X + 0, position.Y + 0, position.Z + depth), // (0,0,z)
|
---|
| 276 | new Vector3D(position.X + width, position.Y + 0, position.Z + depth), // (x,0,z)
|
---|
| 277 |
|
---|
| 278 | new Vector3D(position.X + 0, position.Y + item.Height, position.Z + 0), // (0,y,0)
|
---|
| 279 | new Vector3D(position.X + width, position.Y + item.Height, position.Z + 0), // (x,y,0)
|
---|
| 280 | new Vector3D(position.X + 0, position.Y + item.Height, position.Z + depth), // (0,y,z)
|
---|
| 281 | new Vector3D(position.X + width, position.Y + item.Height, position.Z + depth), //(x,y,z)
|
---|
| 282 | };
|
---|
| 283 | }
|
---|
| 284 |
|
---|
| 285 | private Edge3D[] GetProjectionEdgesOnLeft(PackingItem item, PackingPosition position) {
|
---|
| 286 | Vector3D[] points = GetVertices(item, position);
|
---|
| 287 |
|
---|
| 288 | return new Edge3D[] {
|
---|
| 289 | new Edge3D(points[2], points[6]),
|
---|
| 290 | new Edge3D(points[6], points[4])
|
---|
| 291 | };
|
---|
| 292 | }
|
---|
| 293 |
|
---|
| 294 | private Edge3D[] GetProjectionEdgesBelow(PackingItem item, PackingPosition position) {
|
---|
| 295 | Vector3D[] points = GetVertices(item, position);
|
---|
| 296 |
|
---|
| 297 | return new Edge3D[] {
|
---|
| 298 | new Edge3D(points[2], points[3]),
|
---|
| 299 | new Edge3D(points[3], points[1])
|
---|
| 300 | };
|
---|
| 301 | }
|
---|
| 302 |
|
---|
| 303 | private Edge3D[] GetProjectionEdgesBehind(PackingItem item, PackingPosition position) {
|
---|
| 304 | Vector3D[] points = GetVertices(item, position);
|
---|
| 305 |
|
---|
| 306 | return new Edge3D[] {
|
---|
| 307 | new Edge3D(points[1], points[5]),
|
---|
| 308 | new Edge3D(points[5], points[4])
|
---|
| 309 | };
|
---|
| 310 | }
|
---|
| 311 |
|
---|
| 312 | /// <summary>
|
---|
| 313 | /// Returns an array of edges which contains all edges of the rigth side of an given item.
|
---|
| 314 | /// </summary>
|
---|
| 315 | /// <param name="item"></param>
|
---|
| 316 | /// <param name="position"></param>
|
---|
| 317 | /// <returns></returns>
|
---|
| 318 | private Edge3D[] GetEdgesOnRight(PackingItem item, PackingPosition position) {
|
---|
| 319 | Vector3D[] points = GetVertices(item, position);
|
---|
| 320 |
|
---|
| 321 | return new Edge3D[] {
|
---|
| 322 | new Edge3D(points[1], points[5]),
|
---|
| 323 | new Edge3D(points[5], points[7]),
|
---|
| 324 | new Edge3D(points[7], points[3]),
|
---|
| 325 | new Edge3D(points[3], points[1])
|
---|
| 326 | };
|
---|
| 327 | }
|
---|
| 328 |
|
---|
| 329 | /// <summary>
|
---|
| 330 | /// Returns an array of edges which contains all edges on the top of an given item.
|
---|
| 331 | /// </summary>
|
---|
| 332 | /// <param name="item"></param>
|
---|
| 333 | /// <param name="position"></param>
|
---|
| 334 | /// <returns></returns>
|
---|
| 335 | private Edge3D[] GetEdgesOnTop(PackingItem item, PackingPosition position) {
|
---|
| 336 | Vector3D[] points = GetVertices(item, position);
|
---|
| 337 |
|
---|
| 338 | return new Edge3D[] {
|
---|
| 339 | new Edge3D(points[4], points[5]),
|
---|
| 340 | new Edge3D(points[5], points[7]),
|
---|
| 341 | new Edge3D(points[7], points[6]),
|
---|
| 342 | new Edge3D(points[6], points[4])
|
---|
| 343 | };
|
---|
| 344 | }
|
---|
| 345 |
|
---|
| 346 | /// <summary>
|
---|
| 347 | /// Returns an array of edges which contains all edges in front of an given item.
|
---|
| 348 | /// </summary>
|
---|
| 349 | /// <param name="item"></param>
|
---|
| 350 | /// <param name="position"></param>
|
---|
| 351 | /// <returns></returns>
|
---|
| 352 | private Edge3D[] GetEdgesInFront(PackingItem item, PackingPosition position) {
|
---|
| 353 | Vector3D[] points = GetVertices(item, position);
|
---|
| 354 |
|
---|
| 355 | return new Edge3D[] {
|
---|
| 356 | new Edge3D(points[2], points[3]),
|
---|
| 357 | new Edge3D(points[3], points[7]),
|
---|
| 358 | new Edge3D(points[7], points[6]),
|
---|
| 359 | new Edge3D(points[6], points[2])
|
---|
| 360 | };
|
---|
| 361 | }
|
---|
| 362 |
|
---|
| 363 | #endregion
|
---|
| 364 |
|
---|
| 365 |
|
---|
| 366 | #region Intersections
|
---|
| 367 |
|
---|
| 368 | /// <summary>
|
---|
| 369 | /// Returns a list of extreme points.
|
---|
| 370 | /// </summary>
|
---|
| 371 | /// <param name="item"></param>
|
---|
| 372 | /// <param name="position"></param>
|
---|
| 373 | /// <param name="projectedEdge3D"></param>
|
---|
| 374 | /// <returns></returns>
|
---|
| 375 | private IEnumerable<Vector3D> IntersectionsForItem(Edge3D projectedEdge, Edge3D[] edges) {
|
---|
| 376 | IList<Vector3D> eps = new List<Vector3D>();
|
---|
| 377 | foreach (var edge in edges) {
|
---|
| 378 | var ep = edge.Intersects(projectedEdge);
|
---|
| 379 | if (ep != null) {
|
---|
| 380 | eps.Add(ep);
|
---|
| 381 | }
|
---|
| 382 | }
|
---|
| 383 | return eps as IEnumerable<Vector3D>;
|
---|
| 384 | }
|
---|
| 385 |
|
---|
| 386 |
|
---|
| 387 | #endregion
|
---|
| 388 |
|
---|
| 389 | }
|
---|
| 390 | }
|
---|