Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/ExtremePointPruning/ExtremePointPruning.cs @ 15618

Last change on this file since 15618 was 15618, checked in by rhanghof, 6 years ago

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File size: 3.0 KB
Line 
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
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using System.Threading.Tasks;
27
28namespace HeuristicLab.Problems.BinPacking3D.ExtremePointPruning {
29  internal class ExtremePointPruning : IExtremePointPruning {
30    public void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions) {
31      if (pruningMethod == ExtremePointPruningMethod.PruneBehind) {
32        PruneExtremePointsBehind(bin, positions);
33      }
34    }
35
36    public void PruneExtremePoints(ExtremePointPruningMethod pruningMethod, IList<BinPacking3D> binPackings) {
37      if (binPackings.Count <= 0) {
38        return;
39      }
40      var fixedPositions = new Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>>();
41      foreach (BinPacking3D bp in binPackings) {
42        var list = new List<KeyValuePair<int, PackingPosition>>();
43        fixedPositions.Add(bp, list);
44        foreach (var p in bp.Positions) {
45          list.Add(p);
46        }
47      }
48      PruneExtremePointsBehind(binPackings[0].BinShape, fixedPositions);
49    }
50
51
52    /// <summary>
53    /// Prunes all extreme point behind the given positions.
54    /// </summary>
55    /// <param name="bin"></param>
56    /// <param name="positions"></param>
57    private static void PruneExtremePointsBehind(PackingShape bin, Dictionary<BinPacking3D, List<KeyValuePair<int, PackingPosition>>> positions) {
58      int binHeight = bin.Height;
59      foreach (var kvp in positions) {
60        var bp = kvp.Key;
61        foreach (var item in kvp.Value.OrderByDescending(x => x.Value.Z).ThenByDescending(x => x.Value.X)) {
62          // everything behind the item
63          var limit = new {
64            X = item.Value.X + bp.Items[item.Key].Width,
65            Y = item.Value.Y + binHeight,
66            Z = item.Value.Z
67          };
68          var eps = bp.ExtremePoints.Where(x => x.Key.X < limit.X && x.Key.Y < limit.Y && x.Key.Z < limit.Z).ToList();
69          foreach (var ep in eps) {
70            bp.ExtremePoints.Remove(ep);
71          }
72        }
73      }
74    }
75   
76  }
77}
Note: See TracBrowser for help on using the repository browser.