[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.Common;
|
---|
[15488] | 23 | using HeuristicLab.Problems.BinPacking3D.Geometry;
|
---|
[15520] | 24 | using HeuristicLab.Problems.BinPacking3D.ResidualSpaceCalculation;
|
---|
[15488] | 25 | using System;
|
---|
| 26 | using System.Collections.Generic;
|
---|
| 27 | using System.Linq;
|
---|
| 28 | using System.Text;
|
---|
| 29 | using System.Threading.Tasks;
|
---|
| 30 |
|
---|
| 31 | namespace HeuristicLab.Problems.BinPacking3D.ExtremePointCreation {
|
---|
| 32 | public abstract class ExtremePointCreator : IExtremePointCreator {
|
---|
| 33 |
|
---|
| 34 |
|
---|
[15520] | 35 | public void UpdateBinPacking(BinPacking3D binPacking, PackingItem item, PackingPosition position) {
|
---|
| 36 | UpdateExtremePoints(binPacking, item, position);
|
---|
| 37 | UpdateResidualSpace(binPacking, item, position);
|
---|
| 38 | }
|
---|
[15488] | 39 |
|
---|
[15520] | 40 | protected abstract void UpdateExtremePoints(BinPacking3D binPacking, PackingItem item, PackingPosition position);
|
---|
| 41 |
|
---|
| 42 | /// <summary>
|
---|
[15585] | 43 | /// Updates the residual space for a given bin packing.
|
---|
[15520] | 44 | /// </summary>
|
---|
| 45 | /// <param name="binPacking"></param>
|
---|
| 46 | /// <param name="item"></param>
|
---|
| 47 | /// <param name="position"></param>
|
---|
| 48 | protected abstract void UpdateResidualSpace(BinPacking3D binPacking, PackingItem item, PackingPosition position);
|
---|
[15585] | 49 |
|
---|
| 50 | /// <summary>
|
---|
| 51 | /// Adds an extreme point to the bin packing.
|
---|
| 52 | /// </summary>
|
---|
| 53 | /// <param name="binPacking"></param>
|
---|
| 54 | /// <param name="position"></param>
|
---|
| 55 | /// <returns></returns>
|
---|
[15488] | 56 | protected abstract bool AddExtremePoint(BinPacking3D binPacking, PackingPosition position);
|
---|
| 57 |
|
---|
| 58 | /// <summary>
|
---|
| 59 | /// Generates new extreme points for a given item and its position.
|
---|
| 60 | /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.
|
---|
| 61 | /// </summary>
|
---|
| 62 | /// <param name="binPacking"></param>
|
---|
| 63 | /// <param name="newItem"></param>
|
---|
| 64 | /// <param name="position"></param>
|
---|
[15520] | 65 | protected virtual void GenerateNewExtremePointsForItem(BinPacking3D binPacking, PackingItem newItem, PackingPosition position) {
|
---|
[15617] | 66 | int newWidth = newItem.Width;
|
---|
| 67 | int newDepth = newItem.Depth;
|
---|
[15488] | 68 | var binShape = binPacking.BinShape;
|
---|
| 69 |
|
---|
| 70 | var itemPlacement = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] }).ToList();
|
---|
| 71 | // Find ExtremePoints beginning from sourcepointX
|
---|
| 72 | var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };
|
---|
| 73 | if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
|
---|
| 74 | // Projecting onto the XZ-plane
|
---|
| 75 | var below = ProjectDown(binPacking, sourcePoint);
|
---|
[15554] | 76 | var residualSpaces = CalculateResidualSpace(binPacking, below);
|
---|
| 77 | if (residualSpaces.Count() > 0
|
---|
| 78 | && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
|
---|
[15488] | 79 | // add only if the projected point's residual space is not a sub-space
|
---|
| 80 | // of another extreme point's residual space
|
---|
| 81 | var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
|
---|
| 82 | AddExtremePoint(binPacking, belowPoint);
|
---|
| 83 | }
|
---|
| 84 | // Projecting onto the XY-plane
|
---|
| 85 | var back = ProjectBackward(binPacking, sourcePoint);
|
---|
[15554] | 86 | residualSpaces = CalculateResidualSpace(binPacking, back);
|
---|
| 87 | if (residualSpaces.Count() > 0
|
---|
| 88 | && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
|
---|
[15488] | 89 | // add only if the projected point's residual space is not a sub-space
|
---|
| 90 | // of another extreme point's residual space
|
---|
| 91 | var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
|
---|
| 92 | AddExtremePoint(binPacking, backPoint);
|
---|
| 93 | }
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | //Find ExtremePoints beginning from sourcepointY
|
---|
| 97 | sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);
|
---|
| 98 | if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
|
---|
| 99 | // Projecting onto the YZ-plane
|
---|
| 100 | var left = ProjectLeft(binPacking, sourcePoint);
|
---|
[15554] | 101 | var residualSpaces = CalculateResidualSpace(binPacking, left);
|
---|
| 102 | if (residualSpaces.Count() > 0
|
---|
| 103 | && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
|
---|
[15488] | 104 | // add only if the projected point's residual space is not a sub-space
|
---|
| 105 | // of another extreme point's residual space
|
---|
| 106 | var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
|
---|
| 107 | AddExtremePoint(binPacking, leftPoint);
|
---|
| 108 | }
|
---|
| 109 | // Projecting onto the XY-plane
|
---|
| 110 | var back = ProjectBackward(binPacking, sourcePoint);
|
---|
[15554] | 111 | residualSpaces = CalculateResidualSpace(binPacking, back);
|
---|
| 112 | if (residualSpaces.Count() > 0
|
---|
| 113 | && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, back, residualSpaces)) {
|
---|
[15488] | 114 | // add only if the projected point's residual space is not a sub-space
|
---|
| 115 | // of another extreme point's residual space
|
---|
| 116 | var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);
|
---|
| 117 | AddExtremePoint(binPacking, backPoint);
|
---|
| 118 | }
|
---|
| 119 | }
|
---|
| 120 |
|
---|
| 121 | //Find ExtremePoints beginning from sourcepointZ
|
---|
| 122 | sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
|
---|
| 123 | if (sourcePoint.X < binShape.Width && sourcePoint.Y < binShape.Height && sourcePoint.Z < binShape.Depth) {
|
---|
| 124 | // Projecting onto the XZ-plane
|
---|
| 125 | var below = ProjectDown(binPacking, sourcePoint);
|
---|
[15554] | 126 | var residualSpaces = CalculateResidualSpace(binPacking, below);
|
---|
| 127 | if (residualSpaces.Count() > 0
|
---|
| 128 | && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, below, residualSpaces)) {
|
---|
[15488] | 129 | // add only if the projected point's residual space is not a sub-space
|
---|
| 130 | // of another extreme point's residual space
|
---|
| 131 | var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
|
---|
| 132 | AddExtremePoint(binPacking, belowPoint);
|
---|
| 133 | }
|
---|
| 134 | // Projecting onto the YZ-plane
|
---|
| 135 | var left = ProjectLeft(binPacking, sourcePoint);
|
---|
[15554] | 136 | residualSpaces = CalculateResidualSpace(binPacking, left);
|
---|
| 137 | if (residualSpaces.Count() > 0
|
---|
| 138 | && !IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, left, residualSpaces)) {
|
---|
[15488] | 139 | // add only if the projected point's residual space is not a sub-space
|
---|
| 140 | // of another extreme point's residual space
|
---|
| 141 | var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);
|
---|
| 142 | AddExtremePoint(binPacking, leftPoint);
|
---|
| 143 | }
|
---|
| 144 | }
|
---|
| 145 | }
|
---|
| 146 |
|
---|
| 147 | #region Get items
|
---|
| 148 |
|
---|
| 149 | protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(BinPacking3D binPacking, PackingPosition pos) {
|
---|
| 150 | var line = new Line3D(pos, new Vector3D(0, 1, 0));
|
---|
| 151 | return binPacking.Items.Select(x => new {
|
---|
| 152 | Item = x.Value,
|
---|
| 153 | Position = binPacking.Positions[x.Key],
|
---|
| 154 | Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Bottom))
|
---|
| 155 | }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
|
---|
| 156 | .Select(x => Tuple.Create(x.Position, x.Item));
|
---|
| 157 | }
|
---|
| 158 |
|
---|
| 159 | protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(BinPacking3D binPacking, PackingPosition pos) {
|
---|
| 160 | var line = new Line3D(pos, new Vector3D(0, 0, 1));
|
---|
| 161 | return binPacking.Items.Select(x => new {
|
---|
| 162 | Item = x.Value,
|
---|
| 163 | Position = binPacking.Positions[x.Key],
|
---|
| 164 | Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Back))
|
---|
| 165 | }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
|
---|
| 166 | .Select(x => Tuple.Create(x.Position, x.Item));
|
---|
| 167 | }
|
---|
| 168 |
|
---|
| 169 | protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(BinPacking3D binPacking, PackingPosition pos) {
|
---|
| 170 | var line = new Line3D(pos, new Vector3D(1, 0, 0));
|
---|
| 171 | return binPacking.Items.Select(x => new {
|
---|
| 172 | Item = x.Value,
|
---|
| 173 | Position = binPacking.Positions[x.Key],
|
---|
| 174 | Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Left))
|
---|
| 175 | }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
|
---|
| 176 | .Select(x => Tuple.Create(x.Position, x.Item));
|
---|
| 177 | }
|
---|
| 178 |
|
---|
| 179 | protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(BinPacking3D binPacking, PackingPosition pos) {
|
---|
| 180 | var line = new Line3D(pos, new Vector3D(0, 1, 0));
|
---|
| 181 | return binPacking.Items.Select(x => new {
|
---|
| 182 | Item = x.Value,
|
---|
| 183 | Position = binPacking.Positions[x.Key],
|
---|
| 184 | Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Top))
|
---|
| 185 | }).Where(x => x.Intersection != null && x.Intersection.Y <= pos.Y)
|
---|
| 186 | .Select(x => Tuple.Create(x.Position, x.Item));
|
---|
| 187 | }
|
---|
| 188 |
|
---|
| 189 | protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(BinPacking3D binPacking, PackingPosition pos) {
|
---|
| 190 | var line = new Line3D(pos, new Vector3D(0, 0, 1));
|
---|
| 191 | return binPacking.Items.Select(x => new {
|
---|
| 192 | Item = x.Value,
|
---|
| 193 | Position = binPacking.Positions[x.Key],
|
---|
| 194 | Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Front))
|
---|
| 195 | }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
|
---|
| 196 | .Select(x => Tuple.Create(x.Position, x.Item));
|
---|
| 197 | }
|
---|
| 198 |
|
---|
| 199 | protected IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(BinPacking3D binPacking, PackingPosition pos) {
|
---|
| 200 | var line = new Line3D(pos, new Vector3D(1, 0, 0));
|
---|
| 201 | return binPacking.Items.Select(x => new {
|
---|
| 202 | Item = x.Value,
|
---|
| 203 | Position = binPacking.Positions[x.Key],
|
---|
| 204 | Intersection = line.Intersect(new Plane3D(binPacking.Positions[x.Key], x.Value, Side.Right))
|
---|
| 205 | }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)
|
---|
| 206 | .Select(x => Tuple.Create(x.Position, x.Item));
|
---|
| 207 | }
|
---|
| 208 |
|
---|
| 209 | #endregion
|
---|
| 210 |
|
---|
| 211 | #region Residual space
|
---|
| 212 |
|
---|
| 213 |
|
---|
| 214 | /// <summary>
|
---|
| 215 | ///
|
---|
| 216 | /// </summary>
|
---|
| 217 | /// <param name="binPacking"></param>
|
---|
| 218 | /// <param name="pos"></param>
|
---|
| 219 | /// <param name="residualSpace"></param>
|
---|
| 220 | /// <returns></returns>
|
---|
[15554] | 221 | protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, ResidualSpace residualSpace) {
|
---|
| 222 | var eps = binPacking.ExtremePoints.Where(x => !pos.Equals(x.Key) && pos.IsInside(x.Key, x.Value));
|
---|
| 223 | return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x.Key, x.Value));
|
---|
[15488] | 224 | }
|
---|
| 225 |
|
---|
| 226 | /// <summary>
|
---|
[15554] | 227 | ///
|
---|
| 228 | /// </summary>
|
---|
| 229 | /// <param name="binPacking"></param>
|
---|
| 230 | /// <param name="pos"></param>
|
---|
| 231 | /// <param name="residualSpaces"></param>
|
---|
| 232 | /// <returns></returns>
|
---|
| 233 | protected bool IsWithinResidualSpaceOfAnotherExtremePoint(BinPacking3D binPacking, Vector3D pos, IEnumerable<ResidualSpace> residualSpaces) {
|
---|
| 234 | foreach (var residualSpace in residualSpaces) {
|
---|
| 235 | if (IsWithinResidualSpaceOfAnotherExtremePoint(binPacking, pos, residualSpace)) {
|
---|
| 236 | return true;
|
---|
| 237 | }
|
---|
| 238 | }
|
---|
| 239 | return false;
|
---|
| 240 | }
|
---|
| 241 |
|
---|
| 242 |
|
---|
| 243 | /// <summary>
|
---|
[15585] | 244 | /// Returns true, if the given poisition (pos) and the related residual space is within any residual space of the given extreme point (ep).
|
---|
[15488] | 245 | /// </summary>
|
---|
[15585] | 246 | /// <param name="pos">Given poisition</param>
|
---|
[15488] | 247 | /// <param name="rsPos"></param>
|
---|
[15585] | 248 | /// <param name="ep">Given extreme point</param>
|
---|
[15488] | 249 | /// <param name="rsEp"></param>
|
---|
| 250 | /// <returns></returns>
|
---|
[15554] | 251 | protected bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, IEnumerable<ResidualSpace> rsEp) {
|
---|
| 252 | return rsEp.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, rsPos, ep, x));
|
---|
| 253 | }
|
---|
| 254 |
|
---|
| 255 | /// <summary>
|
---|
[15585] | 256 | /// Returns true, if the given poisition (pos) and the related residual space is within the residual space of the given extreme point (ep).
|
---|
[15554] | 257 | /// </summary>
|
---|
[15585] | 258 | /// <param name="pos">Given poisition</param>
|
---|
[15554] | 259 | /// <param name="rsPos"></param>
|
---|
[15585] | 260 | /// <param name="ep">Given extreme point</param>
|
---|
[15554] | 261 | /// <param name="rsEp"></param>
|
---|
| 262 | /// <returns></returns>
|
---|
[15520] | 263 | protected virtual bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, ResidualSpace rsPos, PackingPosition ep, ResidualSpace rsEp) {
|
---|
[15585] | 264 | /*old implementation
|
---|
[15520] | 265 | return rsEp.Width >= pos.X - ep.X + rsPos.Width
|
---|
| 266 | && rsEp.Height >= pos.Y - ep.Y + rsPos.Height
|
---|
[15585] | 267 | && rsEp.Depth >= pos.Z - ep.Z + rsPos.Depth;*/
|
---|
| 268 |
|
---|
| 269 | var x = pos.X >= ep.X && pos.X + rsPos.Width <= ep.X + rsEp.Width;
|
---|
| 270 | var y = pos.Y >= ep.Y && pos.Y + rsPos.Height <= ep.Y + rsEp.Height;
|
---|
| 271 | var z = pos.Z >= ep.Z && pos.Z + rsPos.Depth <= ep.Z + rsEp.Depth;
|
---|
| 272 |
|
---|
| 273 | return x && y && z;
|
---|
[15488] | 274 | }
|
---|
| 275 |
|
---|
| 276 | /// <summary>
|
---|
[15554] | 277 | /// Calculates the residual spaces for a given bin packing and position.
|
---|
| 278 | /// It returns a collection of residual spaces
|
---|
[15488] | 279 | /// </summary>
|
---|
| 280 | /// <param name="binPacking"></param>
|
---|
| 281 | /// <param name="pos"></param>
|
---|
[15554] | 282 | /// <returns></returns>
|
---|
| 283 | protected abstract IEnumerable<ResidualSpace> CalculateResidualSpace(BinPacking3D binPacking, Vector3D pos);
|
---|
| 284 |
|
---|
[15488] | 285 | #endregion
|
---|
| 286 |
|
---|
| 287 | #region Projections
|
---|
| 288 |
|
---|
| 289 | protected Vector3D ProjectBackward(BinPacking3D binPacking, Vector3D pos) {
|
---|
| 290 | var line = new Line3D(pos, new Vector3D(0, 0, -1));
|
---|
| 291 | var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
|
---|
| 292 | .Select(x => new Plane3D(x.Position, x.Item, Side.Front))
|
---|
| 293 | .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Back) })
|
---|
| 294 | .Select(x => x.Intersect(line))
|
---|
| 295 | .Where(x => x != null && x.Z <= pos.Z);
|
---|
| 296 | if (m.Where(x => x != null).Any()) {
|
---|
| 297 | return m.MaxItems(x => x.Y).First();
|
---|
| 298 | }
|
---|
| 299 | return null;
|
---|
| 300 | }
|
---|
| 301 |
|
---|
| 302 | protected Vector3D ProjectLeft(BinPacking3D binPacking, Vector3D pos) {
|
---|
| 303 | var line = new Line3D(pos, new Vector3D(-1, 0, 0));
|
---|
| 304 | var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
|
---|
| 305 | .Select(x => new Plane3D(x.Position, x.Item, Side.Right))
|
---|
| 306 | .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Left) })
|
---|
| 307 | .Select(x => x.Intersect(line))
|
---|
| 308 | .Where(x => x != null && x.X <= pos.X);
|
---|
| 309 | if (m.Where(x => x != null).Any()) {
|
---|
| 310 | return m.MaxItems(x => x.Y).First();
|
---|
| 311 | }
|
---|
| 312 | return null;
|
---|
| 313 | }
|
---|
| 314 |
|
---|
| 315 | protected Vector3D ProjectDown(BinPacking3D binPacking, Vector3D pos) {
|
---|
| 316 | var line = new Line3D(pos, new Vector3D(0, -1, 0));
|
---|
| 317 | var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
|
---|
| 318 | .Select(x => new Plane3D(x.Position, x.Item, Side.Top))
|
---|
| 319 | .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Bottom) })
|
---|
| 320 | .Select(x => x.Intersect(line))
|
---|
| 321 | .Where(x => x != null && x.Y <= pos.Y);
|
---|
| 322 | if (m.Where(x => x != null).Any()) {
|
---|
| 323 | return m.MaxItems(x => x.Y).First();
|
---|
| 324 | }
|
---|
| 325 | return null;
|
---|
| 326 | }
|
---|
| 327 |
|
---|
| 328 | protected Vector3D ProjectForward(BinPacking3D binPacking, Vector3D pos) {
|
---|
| 329 | var line = new Line3D(pos, new Vector3D(0, 0, 1));
|
---|
| 330 | var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
|
---|
| 331 | .Select(x => new Plane3D(x.Position, x.Item, Side.Back))
|
---|
| 332 | .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Front) })
|
---|
| 333 | .Select(x => x.Intersect(line))
|
---|
| 334 | .Where(x => x != null && x.Z >= pos.Z);
|
---|
| 335 | if (m.Where(x => x != null).Any()) {
|
---|
| 336 | return m.MaxItems(x => x.Y).First();
|
---|
| 337 | }
|
---|
| 338 | return null;
|
---|
| 339 | }
|
---|
| 340 |
|
---|
| 341 | protected Vector3D ProjectRight(BinPacking3D binPacking, Vector3D pos) {
|
---|
| 342 | var line = new Line3D(pos, new Vector3D(1, 0, 0));
|
---|
| 343 | var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
|
---|
| 344 | .Select(x => new Plane3D(x.Position, x.Item, Side.Left))
|
---|
| 345 | .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Right) })
|
---|
| 346 | .Select(x => x.Intersect(line))
|
---|
| 347 | .Where(x => x != null && x.X >= pos.X);
|
---|
| 348 | if (m.Where(x => x != null).Any()) {
|
---|
| 349 | return m.MaxItems(x => x.Y).First();
|
---|
| 350 | }
|
---|
| 351 | return null;
|
---|
| 352 | }
|
---|
| 353 |
|
---|
| 354 | protected Vector3D ProjectUp(BinPacking3D binPacking, Vector3D pos) {
|
---|
| 355 | var line = new Line3D(pos, new Vector3D(0, 1, 0));
|
---|
| 356 | var m = binPacking.Items.Select(x => new { Item = x.Value, Position = binPacking.Positions[x.Key] })
|
---|
| 357 | .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))
|
---|
| 358 | .Concat(new[] { new Plane3D(binPacking.BinShape, Side.Top) })
|
---|
| 359 | .Select(x => x.Intersect(line))
|
---|
| 360 | .Where(x => x != null && x.Y >= pos.Y);
|
---|
| 361 | if (m.Where(x => x != null).Any()) {
|
---|
| 362 | return m.MaxItems(x => x.Y).First();
|
---|
| 363 | }
|
---|
| 364 | return null;
|
---|
| 365 | }
|
---|
| 366 | #endregion
|
---|
| 367 | }
|
---|
| 368 | }
|
---|