- Timestamp:
- 11/28/17 16:10:31 (7 years ago)
- Location:
- branches/2817-BinPackingSpeedup
- Files:
-
- 12 added
- 1 deleted
- 15 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml
r15307 r15488 33 33 > 34 34 <Grid Margin="0,0,-64,-57"> 35 <CheckBox Name="showExtremePointsCheckBox" Content="Show extreme points" VerticalAlignment="Top" HorizontalAlignment="Left" Margin="10,6,0,0" Unchecked="showExtremePointsCheckBoxOnUnchecked" Checked="showExtremePointsCheckBoxOnChecked"/> 36 <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,30,0,0"> 35 <StackPanel> 36 <CheckBox Name="showExtremePointsCheckBox" 37 Content="Show extreme points" 38 VerticalAlignment="Top" 39 HorizontalAlignment="Left" 40 Margin="10,6,0,0" 41 Unchecked="ShowExtremePointsCheckBoxOnUnchecked" 42 Checked="ShowExtremePointsCheckBoxOnChecked"/> 43 <CheckBox Name="showResidualSpaceCheckBox" 44 Content="Show residual spaces" 45 VerticalAlignment="Top" 46 HorizontalAlignment="Left" 47 Margin="10,6,0,0" 48 Unchecked="ShowResidualSpacesCheckBoxOnUnchecked" 49 Checked="ShowResidualSpacesCheckBoxOnChecked"/> 50 </StackPanel> 51 <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}" Margin="0,52,0,0"> 37 52 <Viewport3D Name="viewport3D1" Margin="0,-1,0,0" > 38 53 <Viewport3D.Camera> -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs
r15307 r15488 27 27 using System.Windows.Media.Media3D; 28 28 using HeuristicLab.Problems.BinPacking3D; 29 using HeuristicLab.Collections; 29 30 30 31 namespace HeuristicLab.Problems.BinPacking.Views { … … 49 50 private static readonly Color hiddenColor = Color.FromArgb(0x1A, 0xAA, 0xAA, 0xAA); 50 51 private static readonly Color containerColor = Color.FromArgb(0x7F, 0xAA, 0xAA, 0xAA); 52 private static readonly Color residualSpaceColor = Color.FromArgb(0x7F, 0xAA, 0xAA, 0x00); 51 53 52 54 private Point startPos; … … 55 57 private double startAngleY; 56 58 private int selectedItemKey; 59 private int selectedExtremePointIndex; 57 60 private bool showExtremePoints; 61 private bool showResidualSpaces; 58 62 59 63 private BinPacking<BinPacking3D.PackingPosition, PackingShape, PackingItem> packing; … … 70 74 private Dictionary<int, DiffuseMaterial> materials; 71 75 76 public ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>> ResidualSpaces { get; set; } 77 public ObservableCollection<BinPacking3D.PackingPosition> ExtremePoints { get; set; } 78 72 79 public Container3DView() { 73 80 InitializeComponent(); 74 81 camMain.Position = new Point3D(0.5, 3, 3); // for design time we use a different camera position 75 82 materials = new Dictionary<int, DiffuseMaterial>(); 83 ResidualSpaces = new ObservableDictionary<BinPacking3D.PackingPosition, Tuple<int, int, int>>(); 84 ExtremePoints = new ObservableCollection<BinPacking3D.PackingPosition>(); 85 selectedExtremePointIndex = -1; 76 86 Clear(); 77 87 } … … 85 95 } 86 96 97 /// <summary> 98 /// Selects another extreme point 99 /// </summary> 100 /// <param name="index"></param> 101 public void SelectExtremePoint(int index) { 102 selectedExtremePointIndex = index; 103 UpdateVisualization(); 104 } 105 87 106 public void SelectItem(int itemKey) { 88 107 // selection of an item should make all other items semi-transparent … … 90 109 UpdateVisualization(); 91 110 } 111 92 112 public void ClearSelection() { 93 113 // remove all transparency 94 114 selectedItemKey = -1; 115 selectedExtremePointIndex = -1; 95 116 UpdateVisualization(); 96 117 } … … 98 119 private void UpdateVisualization() { 99 120 Clear(); 100 if (packing == null) return; // nothing to display 121 if (packing == null) 122 return; // nothing to display 101 123 102 124 var modelGroup = (Model3DGroup)MyModel.Content; … … 108 130 109 131 var colorIdx = selectedItem.Value.Material; 110 while (colorIdx < 0) colorIdx += colors.Length; 132 while (colorIdx < 0) 133 colorIdx += colors.Length; 111 134 colorIdx = colorIdx % colors.Length; 112 135 var color = colors[colorIdx]; … … 132 155 modelGroup.Children.Add(model); 133 156 } 157 158 134 159 } else { 135 160 foreach (var item in packing.Items) { … … 144 169 if (!materials.TryGetValue(item.Value.Material, out material)) { 145 170 var colorIdx = item.Value.Material; 146 while (colorIdx < 0) colorIdx += colors.Length; 171 while (colorIdx < 0) 172 colorIdx += colors.Length; 147 173 colorIdx = colorIdx % colors.Length; 148 174 var color = colors[colorIdx]; … … 156 182 } 157 183 158 if (showExtremePoints) { 159 // draw extreme-points 160 var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width))); 161 var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1); 162 foreach (var ep in packing.ExtremePoints) { 163 var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } }; 164 AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize); 165 modelGroup.Children.Add(epModel); 166 } 167 } 184 185 AddExtremePoints(modelGroup); 168 186 169 187 var container = packing.BinShape; … … 191 209 } 192 210 211 private void AddExtremePoints(Model3DGroup modelGroup) { 212 if (showExtremePoints) { 213 // draw extreme-points 214 var maxMag = (int)Math.Log10(Math.Max(packing.BinShape.Depth, Math.Max(packing.BinShape.Height, packing.BinShape.Width))); 215 var cubeSize = (int)Math.Max(Math.Pow(10, maxMag - 2), 1); 216 BinPacking3D.PackingPosition selectedExtremePoint = null; 217 if (selectedExtremePointIndex < 0) { 218 foreach (var ep in ExtremePoints) { 219 AddResidualSpacesForExtremePoint(modelGroup, ep); 220 } 221 } else { 222 selectedExtremePoint = ExtremePoints.ToList()[selectedExtremePointIndex]; 223 AddResidualSpacesForExtremePoint(modelGroup, selectedExtremePoint); 224 } 225 226 foreach (var ep in ExtremePoints) { 227 Color color; 228 if (ep.Equals(selectedExtremePoint)) { 229 color = Colors.Yellow; 230 } else { 231 color = Colors.Red; 232 } 233 var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(color) } }; 234 AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, cubeSize, cubeSize, cubeSize); 235 modelGroup.Children.Add(epModel); 236 } 237 } 238 } 239 240 private void AddResidualSpacesForExtremePoint(Model3DGroup modelGroup, BinPacking3D.PackingPosition extremePoint) { 241 if (showResidualSpaces) { 242 var rs = ResidualSpaces[extremePoint]; 243 var containerModel1 = new GeometryModel3D(new MeshGeometry3D(), new DiffuseMaterial(new SolidColorBrush(residualSpaceColor))); 244 245 modelGroup.Children.Add(containerModel1); 246 AddWireframeCube((MeshGeometry3D)containerModel1.Geometry, 247 extremePoint.X, 248 extremePoint.Y, 249 extremePoint.Z, 250 rs.Item1, 251 rs.Item2, 252 rs.Item3); 253 254 } 255 } 256 193 257 194 258 private void Clear() { … … 202 266 203 267 private void Container3DView_MouseMove(object sender, MouseEventArgs e) { 204 if (!mouseDown) return; 268 if (!mouseDown) 269 return; 205 270 var pos = e.GetPosition((IInputElement)this); 206 271 … … 235 300 Focus(); // for mouse wheel events 236 301 } 237 private void showExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {302 private void ShowExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) { 238 303 showExtremePoints = true; 239 304 UpdateVisualization(); 240 305 } 241 private void showExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {306 private void ShowExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) { 242 307 showExtremePoints = false; 308 UpdateVisualization(); 309 } 310 311 private void ShowResidualSpacesCheckBoxOnChecked(object sender, RoutedEventArgs e) { 312 showResidualSpaces = true; 313 UpdateVisualization(); 314 } 315 private void ShowResidualSpacesCheckBoxOnUnchecked(object sender, RoutedEventArgs e) { 316 showResidualSpaces = false; 243 317 UpdateVisualization(); 244 318 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.Designer.cs
r14162 r15488 49 49 this.elementHost = new System.Windows.Forms.Integration.ElementHost(); 50 50 this.packingPlan3D = new HeuristicLab.Problems.BinPacking.Views.Container3DView(); 51 this.extremePointsSelection = new System.Windows.Forms.ListBox(); 51 52 this.SuspendLayout(); 52 53 // … … 58 59 this.binSelection.Location = new System.Drawing.Point(3, 3); 59 60 this.binSelection.Name = "binSelection"; 60 this.binSelection.Size = new System.Drawing.Size(54, 2 90);61 this.binSelection.Size = new System.Drawing.Size(54, 264); 61 62 this.binSelection.TabIndex = 4; 62 63 this.binSelection.SelectedIndexChanged += new System.EventHandler(this.binSelection_SelectedIndexChanged); … … 69 70 this.itemSelection.Location = new System.Drawing.Point(58, 3); 70 71 this.itemSelection.Name = "itemSelection"; 71 this.itemSelection.Size = new System.Drawing.Size(55, 2 90);72 this.itemSelection.Size = new System.Drawing.Size(55, 264); 72 73 this.itemSelection.TabIndex = 5; 73 74 this.itemSelection.SelectedIndexChanged += new System.EventHandler(this.itemSelection_SelectedIndexChanged); … … 78 79 | System.Windows.Forms.AnchorStyles.Left) 79 80 | System.Windows.Forms.AnchorStyles.Right))); 80 this.elementHost.Location = new System.Drawing.Point(1 19, 3);81 this.elementHost.Location = new System.Drawing.Point(198, 3); 81 82 this.elementHost.Name = "elementHost"; 82 this.elementHost.Size = new System.Drawing.Size(2 29, 290);83 this.elementHost.Size = new System.Drawing.Size(273, 264); 83 84 this.elementHost.TabIndex = 6; 84 85 this.elementHost.Text = "elementHost"; 85 86 this.elementHost.Child = this.packingPlan3D; 87 // 88 // extremePointsSelection 89 // 90 this.extremePointsSelection.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Bottom) 91 | System.Windows.Forms.AnchorStyles.Left))); 92 this.extremePointsSelection.FormattingEnabled = true; 93 this.extremePointsSelection.Location = new System.Drawing.Point(115, 3); 94 this.extremePointsSelection.Name = "extremePointsSelection"; 95 this.extremePointsSelection.Size = new System.Drawing.Size(77, 264); 96 this.extremePointsSelection.TabIndex = 7; 97 this.extremePointsSelection.SelectedIndexChanged += new System.EventHandler(this.extremePointsSelection_SelectedIndexChanged); 86 98 // 87 99 // PackingPlan3DView … … 89 101 this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F); 90 102 this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font; 103 this.Controls.Add(this.extremePointsSelection); 91 104 this.Controls.Add(this.elementHost); 92 105 this.Controls.Add(this.itemSelection); 93 106 this.Controls.Add(this.binSelection); 94 107 this.Name = "PackingPlan3DView"; 95 this.Size = new System.Drawing.Size( 351, 299);108 this.Size = new System.Drawing.Size(489, 278); 96 109 this.ResumeLayout(false); 97 110 … … 104 117 private System.Windows.Forms.Integration.ElementHost elementHost; 105 118 private Container3DView packingPlan3D; 119 private System.Windows.Forms.ListBox extremePointsSelection; 106 120 } 107 121 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/PackingPlan3DView.cs
r14167 r15488 47 47 } else { 48 48 int i = 0; 49 foreach (var bp in Content.Bins) 49 foreach (var bp in Content.Bins) { 50 50 binSelection.Items.Add(i++ + " (" + Math.Round(bp.PackingDensity * 100, 2) + "%)"); 51 } 52 51 53 52 54 binSelection.SelectedIndex = 0; … … 63 65 itemSelection.SelectedIndex = -1; 64 66 itemSelection.Items.Clear(); 67 extremePointsSelection.Items.Clear(); 68 packingPlan3D.ResidualSpaces.Clear(); 69 packingPlan3D.ExtremePoints.Clear(); 65 70 66 71 // add items of this container … … 69 74 foreach (var item in packing.Items) { 70 75 itemSelection.Items.Add(item.Key); 76 } 77 foreach (var ep in packing.ExtremePoints) { 78 var rs = ((BinPacking3D.BinPacking3D)packing).ResidualSpace[ep]; 79 extremePointsSelection.Items.Add($"({ep.X}, {ep.Y}, {ep.Z})"); 80 packingPlan3D.ExtremePoints.Add(ep); 81 packingPlan3D.ResidualSpaces.Add(ep, rs); 71 82 } 72 83 … … 81 92 packingPlan3D.ClearSelection(); 82 93 } 94 95 private void extremePointsSelection_SelectedIndexChanged(object sender, EventArgs e) { 96 if (extremePointsSelection != null && extremePointsSelection.SelectedIndex >= 0) { 97 packingPlan3D.SelectExtremePoint(extremePointsSelection.SelectedIndex); 98 } else { 99 packingPlan3D.ClearSelection(); 100 } 101 } 83 102 } 84 103 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs
r15473 r15488 42 42 public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit } 43 43 44 public enum ExtremePointCreationMethod { All, PointProjection, LineProjection } 45 44 46 [Item("Extreme-point-based Bin Packing (3d)", "An implementation of the extreme-point based packing described in Crainic, T. G., Perboli, G., & Tadei, R. (2008). Extreme point-based heuristics for three-dimensional bin packing. Informs Journal on computing, 20(3), 368-384.")] 45 47 [StorableClass] … … 83 85 public IValueParameter<BoolValue> SortByMaterialParameter { 84 86 get { return sortByMaterialParameter; } 85 } 87 } 88 89 [Storable] 90 private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter; 91 public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter { 92 get { return extremePointCreationMethodParameter; } 93 } 86 94 87 95 [StorableConstructor] … … 100 108 "FittingMethod", "Which method to fit should be used.", new EnumValue<FittingMethod>(FittingMethod.All))); 101 109 110 Parameters.Add(extremePointCreationMethodParameter = new ValueParameter<EnumValue<ExtremePointCreationMethod>>( 111 "ExtremePointCreationMethod", "Which method should be used for creatomg extreme points.", new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.All))); 112 102 113 Parameters.Add(deltaParameter = new ValueParameter<PercentValue>( 103 114 "Delta", "[1;100]% Clustered sorting methods use a delta parameter to determine the clusters.", new PercentValue(.1))); … … 124 135 var items = Problem.Items; 125 136 var bin = Problem.BinShape; 137 126 138 var sorting = new[] { SortingMethodParameter.Value.Value }; 127 139 if (sorting[0] == SortingMethod.All) { 128 140 sorting = Enum.GetValues(typeof(SortingMethod)).Cast<SortingMethod>().Where(x => x != SortingMethod.All).ToArray(); 129 141 } 142 130 143 var fitting = new[] { fittingMethodParameter.Value.Value }; 131 144 if (fitting[0] == FittingMethod.All) { … … 133 146 } 134 147 148 var extremePointCreation = new[] { ExtremePointCreationMethodParameter.Value.Value }; 149 if (extremePointCreation[0] == ExtremePointCreationMethod.All) { 150 extremePointCreation = Enum.GetValues(typeof(ExtremePointCreationMethod)) 151 .Cast<ExtremePointCreationMethod>() 152 .Where(x => x != ExtremePointCreationMethod.All) 153 .ToArray(); 154 } 155 135 156 // 136 var result = GetBest(bin, items, sorting, fitting, token);157 var result = GetBest(bin, items, sorting, fitting, extremePointCreation, token); 137 158 if (result == null) { 138 159 throw new InvalidOperationException("No result obtained!"); … … 162 183 new EnumValue<FittingMethod>(result.Item4.Value))); 163 184 } 185 186 if (result.Item5.HasValue && extremePointCreation.Length > 1) { 187 Results.Add(new Result("Best extreme point creation method", 188 "The extreme point creation method that found the best solution", 189 new EnumValue<ExtremePointCreationMethod>(result.Item5.Value))); 190 } 164 191 } 165 192 … … 173 200 /// <param name="token"></param> 174 201 /// <returns></returns> 175 private Tuple<Solution, double, SortingMethod?, FittingMethod?> GetBest(PackingShape bin, IList<PackingItem> items, SortingMethod[] sortings, FittingMethod[] fittings, CancellationToken token) { 202 private Tuple<Solution, double, SortingMethod?, FittingMethod?, ExtremePointCreationMethod?> 203 GetBest(PackingShape bin, 204 IList<PackingItem> items, 205 SortingMethod[] sortings, 206 FittingMethod[] fittings, 207 ExtremePointCreationMethod[] ePGeneration, 208 CancellationToken token) { 176 209 SortingMethod? bestSorting = null; 177 210 FittingMethod? bestFitting = null; 211 ExtremePointCreationMethod? bestEPCreation = null; 178 212 var best = double.NaN; 179 213 Solution bestSolution = null; 180 214 foreach (var fit in fittings) { 181 215 foreach (var sort in sortings) { 182 IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder(BinPackerFactory.CreateBinPacker(fit)); 183 Permutation sortedItems; 216 foreach (var epCreation in ePGeneration) { 217 IDecoder<Permutation> decoder = new ExtremePointPermutationDecoder() { 218 FittingMethod = fit, 219 ExtremePointCreationMethod = epCreation 220 }; 221 Permutation sortedItems; 184 222 185 if (SortByMaterialParameter.Value.Value) { 186 sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value); 187 } else { 188 sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value); 189 } 223 if (SortByMaterialParameter.Value.Value) { 224 sortedItems = SortItemsByMaterialAndSortingMethod(bin, items, sort, DeltaParameter.Value.Value); 225 } else { 226 sortedItems = SortItemsBySortingMethod(bin, items, sort, DeltaParameter.Value.Value); 227 } 228 229 var result = Optimize(new OptimaizationParamters() { 230 SortedItems = sortedItems, 231 Bin = bin, 232 Items = items, 233 StackingConstraints = Problem.UseStackingConstraints, 234 Decoder = decoder, 235 Evaluator = Problem.SolutionEvaluator, 236 ExtremePointGeneration = epCreation 237 }); 190 238 191 var result = Optimize(sortedItems, bin, items, Problem.UseStackingConstraints, decoder, Problem.SolutionEvaluator);192 193 if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) {194 continue; 195 }196 197 if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) {198 bestSolution = result.Item1;199 best = result.Item2;200 bestSorting = sort;201 bestFitting = fit;202 }203 if (token.IsCancellationRequested) {204 return Tuple.Create(bestSolution, best, bestSorting, bestFitting);239 if (double.IsNaN(result.Item2) || double.IsInfinity(result.Item2)) { 240 continue; 241 } 242 243 if (double.IsNaN(best) || Problem.Maximization && result.Item2 > best || !Problem.Maximization && result.Item2 < best) { 244 bestSolution = result.Item1; 245 best = result.Item2; 246 bestSorting = sort; 247 bestFitting = fit; 248 bestEPCreation = epCreation; 249 } 250 if (token.IsCancellationRequested) { 251 return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation); 252 } 205 253 } 206 254 } … … 209 257 return null; 210 258 } 211 return Tuple.Create(bestSolution, best, bestSorting, bestFitting );259 return Tuple.Create(bestSolution, best, bestSorting, bestFitting, bestEPCreation); 212 260 } 213 261 … … 215 263 /// Returns a tuple with the solution and the packing ratio depending on the given parameters 216 264 /// </summary> 217 /// <param name="sortedItems"></param> 218 /// <param name="bin"></param> 219 /// <param name="items"></param> 220 /// <param name="stackingConstraints"></param> 221 /// <param name="decoder"></param> 222 /// <param name="evaluator"></param> 265 /// <param name="parameters"></param> 223 266 /// <returns></returns> 224 private static Tuple<Solution, double> Optimize( Permutation sortedItems, PackingShape bin, IList<PackingItem> items, bool stackingConstraints, IDecoder<Permutation> decoder, IEvaluator evaluator) {267 private static Tuple<Solution, double> Optimize(OptimaizationParamters parameters) { 225 268 226 var sol = decoder.Decode(sortedItems, bin, items, stackingConstraints);227 var fit = evaluator.Evaluate(sol);269 var sol = parameters.Decoder.Decode(parameters.SortedItems, parameters.Bin, parameters.Items, parameters.StackingConstraints); 270 var fit = parameters.Evaluator.Evaluate(sol); 228 271 229 272 return Tuple.Create(sol, fit); 273 } 274 275 private class OptimaizationParamters { 276 public Permutation SortedItems { get; set; } 277 public PackingShape Bin { get; set; } 278 public IList<PackingItem> Items { get; set; } 279 public bool StackingConstraints { get; set; } 280 public IDecoder<Permutation> Decoder { get; set; } 281 public IEvaluator Evaluator { get; set; } 282 public ExtremePointCreationMethod ExtremePointGeneration { get; set; } 230 283 } 231 284 -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs
r15473 r15488 28 28 using HeuristicLab.Problems.BinPacking; 29 29 using HeuristicLab.Problems.BinPacking3D.Geometry; 30 using HeuristicLab.Collections; 30 31 31 32 namespace HeuristicLab.Problems.BinPacking3D { … … 35 36 36 37 [Storable] 37 public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; protected set; } 38 public Dictionary<PackingPosition, Tuple<int, int, int>> ResidualSpace { get; set; } 39 40 41 38 42 39 43 public BinPacking3D(PackingShape binShape) 40 44 : base(binShape) { 41 45 ResidualSpace = new Dictionary<PackingPosition, Tuple<int, int, int>>(); 42 AddExtremePoint(binShape.Origin); 46 47 ExtremePoints.Add(binShape.Origin); 48 ResidualSpace.Add(binShape.Origin, new Tuple<int, int, int>(BinShape.Width, BinShape.Height, BinShape.Depth)); 49 50 // AddExtremePoint(binShape.Origin); 43 51 } 44 52 [StorableConstructor] … … 63 71 #endregion 64 72 } 73 74 75 65 76 66 77 /// <summary> … … 77 88 } 78 89 90 /* 79 91 /// <summary> 80 92 /// Updates the extreme points of the bin … … 89 101 UpdateExtremePointsWithoutStackingConstriants(item, position); 90 102 } 91 } 92 103 }*/ 104 105 106 /* 93 107 /// <summary> 94 108 /// Updates the extreme points of the bin. … … 98 112 /// <param name="position"></param> 99 113 private void UpdateExtremePointsWithStackingConstriants(PackingItem newItem, PackingPosition position) { 100 101 //UpdateExtremePointsWithoutStackingConstriants(newItem, position);102 //return;103 104 114 int newWidth = position.Rotated ? newItem.Depth : newItem.Width; 105 115 int newDepth = position.Rotated ? newItem.Width : newItem.Depth; … … 110 120 AddExtremePoint(ep2); 111 121 AddExtremePoint(ep3); 112 } 113 114 private Tuple<int, int, int> CalculateResidualSpace(Vector3D pos) { 115 var itemPos = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }); 116 Vector3D limit = new Vector3D() { X = BinShape.Width, Y = BinShape.Height, Z = BinShape.Depth }; 117 if (pos.X < limit.X && pos.Y < limit.Y && pos.Z < limit.Z) { 118 var rightLimit = ProjectRight(pos); 119 var upLimit = ProjectUp(pos); 120 var forwardLimit = ProjectForward(pos); 121 if (rightLimit.X > 0) { 122 limit.X = rightLimit.X; 123 } 124 if (upLimit.Y > 0) { 125 limit.Y = upLimit.Y; 126 } 127 if (forwardLimit.Z > 0) { 128 limit.Z = forwardLimit.Z; 129 } 130 } 131 132 if (limit.X - pos.X <= 0 || limit.Y - pos.Y <= 0 || limit.Z - pos.Z <= 0) { 133 return Tuple.Create(0, 0, 0); 134 } 135 return Tuple.Create(limit.X - pos.X, limit.Y - pos.Y, limit.Z - pos.Z); 136 } 137 138 139 private Vector3D CreateRs(PackingPosition position) { 140 return new Vector3D() { X = position.X, Y = position.Y, Z = position.Z }; 141 } 142 143 private void UpdateExtremePointsWithoutStackingConstriants(PackingItem item, PackingPosition position) { 144 GenerateNewExtremePointsForNewItem(item, position); 145 146 // if an item is fit in below, before, or left of another its extreme points have to be regenerated 147 foreach (var above in GetItemsAbove(position)) { 148 GenerateNewExtremePointsForNewItem(above.Item2, above.Item1); 149 } 150 foreach (var front in GetItemsInfront(position)) { 151 GenerateNewExtremePointsForNewItem(front.Item2, front.Item1); 152 } 153 foreach (var right in GetItemsOnRight(position)) { 154 GenerateNewExtremePointsForNewItem(right.Item2, right.Item1); 155 } 156 } 157 158 122 }*/ 123 124 125 126 #region Position feasability 159 127 160 128 /// <summary> 161 129 /// In this case feasability is defined as following: 162 /// 1. the item fits into the bin-borders; 163 /// 2. the point is supported by something; 164 /// 3. the item does not collide with another already packed item 165 /// 166 /// Unfortunatelly this method does not support item rotation 130 /// 1. the point is supported by something; 131 /// 2. the item does not collide with another already packed item 167 132 /// </summary> 168 133 /// <param name="item"></param> … … 171 136 /// <returns></returns> 172 137 public override bool IsPositionFeasible(PackingItem item, PackingPosition position, bool stackingConstraints) { 173 var b1 = CheckItemDimensions(item);138 //var b1 = CheckItemDimensions(item, position); 174 139 var b2 = ItemCanBePlaced(item, position); 175 140 var b3 = CheckStackingConstraints(item, position, stackingConstraints); 176 141 177 return b1 && b2 && b3; 178 } 179 180 /// <summary> 181 /// Compares the dimensions of a given item and the current bin. 182 /// </summary> 183 /// <param name="item"></param> 184 /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns> 185 private bool CheckItemDimensions(PackingItem item) { 186 return BinShape.Width >= item.Width && BinShape.Height >= item.Height && BinShape.Depth >= item.Depth; 142 return b2 && b3; 187 143 } 188 144 … … 194 150 /// <returns></returns> 195 151 private bool ItemCanBePlaced(PackingItem givenItem, PackingPosition givenItemPosition) { 152 var width = givenItemPosition.Rotated ? givenItem.Depth : givenItem.Width; 153 var depth = givenItemPosition.Rotated ? givenItem.Width : givenItem.Depth; 196 154 // Check if the boundings of the bin would injured 197 if (givenItemPosition.X + givenItem.Width > BinShape.Width ||155 if (givenItemPosition.X + width > BinShape.Width || 198 156 givenItemPosition.Y + givenItem.Height > BinShape.Height || 199 givenItemPosition.Z + givenItem.Depth > BinShape.Depth) {157 givenItemPosition.Z + depth > BinShape.Depth) { 200 158 return false; 201 159 } … … 242 200 return IsStaticStable(item, position) && IsWeightSupported(item, position); 243 201 } 244 245 202 246 203 /// <summary> … … 298 255 p4 = itemsP4.Where(x => position.X < x.Item1.X + x.Item2.Width && position.Z + item.Depth > x.Item1.Z).Any(); 299 256 } 300 301 257 302 258 /// <summary> … … 337 293 } 338 294 339 340 295 /// <summary> 341 296 /// Checks if a given the weight of an given item is supportet by the items below. … … 360 315 itemsP4.Where(x => x.Item2.SupportsStacking(item)).Any(); 361 316 } 317 318 #endregion 319 320 protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) { 321 throw new NotImplementedException(); 322 } 323 324 #region Get items 362 325 363 364 /// <summary>365 /// Generates new extreme points for a given item and its position.366 /// It also recalcualtes the residual space and removes the extreme points which are not needed any more.367 /// </summary>368 /// <param name="newItem"></param>369 /// <param name="position"></param>370 protected override void GenerateNewExtremePointsForNewItem(PackingItem newItem, PackingPosition position) {371 int newWidth = position.Rotated ? newItem.Depth : newItem.Width;372 int newDepth = position.Rotated ? newItem.Width : newItem.Depth;373 374 var itemPlacement = Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] }).ToList();375 // Find ExtremePoints beginning from sourcepointX376 var sourcePoint = new Vector3D() { X = position.X + newWidth, Y = position.Y, Z = position.Z };377 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {378 // Projecting onto the XZ-plane379 var below = ProjectDown(sourcePoint);380 var residualSpace = CalculateResidualSpace(below);381 if (IsNonZero(residualSpace)382 && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {383 // add only if the projected point's residual space is not a sub-space384 // of another extreme point's residual space385 var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);386 AddExtremePoint(belowPoint);387 }388 // Projecting onto the XY-plane389 var back = ProjectBackward(sourcePoint);390 residualSpace = CalculateResidualSpace(back);391 if (IsNonZero(residualSpace)392 && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {393 // add only if the projected point's residual space is not a sub-space394 // of another extreme point's residual space395 var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);396 AddExtremePoint(backPoint);397 }398 }399 400 //Find ExtremePoints beginning from sourcepointY401 sourcePoint = new Vector3D(position.X, position.Y + newItem.Height, position.Z);402 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {403 // Projecting onto the YZ-plane404 var left = ProjectLeft(sourcePoint);405 var residualSpace = CalculateResidualSpace(left);406 if (IsNonZero(residualSpace)407 && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {408 // add only if the projected point's residual space is not a sub-space409 // of another extreme point's residual space410 var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);411 AddExtremePoint(leftPoint);412 }413 // Projecting onto the XY-plane414 var back = ProjectBackward(sourcePoint);415 residualSpace = CalculateResidualSpace(back);416 if (IsNonZero(residualSpace)417 && !IsWithinResidualSpaceOfAnotherExtremePoint(back, residualSpace)) {418 // add only if the projected point's residual space is not a sub-space419 // of another extreme point's residual space420 var backPoint = new PackingPosition(position.AssignedBin, back.X, back.Y, back.Z);421 AddExtremePoint(backPoint);422 }423 }424 425 //Find ExtremePoints beginning from sourcepointZ426 sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);427 if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {428 // Projecting onto the XZ-plane429 var below = ProjectDown(sourcePoint);430 var residualSpace = CalculateResidualSpace(below);431 if (IsNonZero(residualSpace)432 && !IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {433 // add only if the projected point's residual space is not a sub-space434 // of another extreme point's residual space435 var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);436 AddExtremePoint(belowPoint);437 }438 // Projecting onto the YZ-plane439 var left = ProjectLeft(sourcePoint);440 residualSpace = CalculateResidualSpace(left);441 if (IsNonZero(residualSpace)442 && !IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {443 // add only if the projected point's residual space is not a sub-space444 // of another extreme point's residual space445 var leftPoint = new PackingPosition(position.AssignedBin, left.X, left.Y, left.Z);446 AddExtremePoint(leftPoint);447 }448 }449 }450 451 /// <summary>452 /// Returns true if all values of a given tuple are not zero453 /// </summary>454 /// <param name="rs">Tuple with three integer values which represents a residual space</param>455 /// <returns></returns>456 private bool IsNonZero(Tuple<int, int, int> rs) {457 return rs.Item1 > 0 && rs.Item2 > 0 && rs.Item3 > 0;458 }459 460 /// <summary>461 ///462 /// </summary>463 /// <param name="pos"></param>464 /// <param name="residualSpace"></param>465 /// <returns></returns>466 private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {467 var eps = ExtremePoints.Where(x => !pos.Equals(x) && pos.IsInside(x, ResidualSpace[x]));468 return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));469 }470 private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {471 return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1472 && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2473 && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;474 }475 476 /// <summary>477 /// Adds an extrem point to the extreme point collection of the bin packing.478 /// </summary>479 /// <param name="pos">Position of the new extreme point</param>480 /// <returns>Retruns true if the extreme point could be added</returns>481 private bool AddExtremePoint(PackingPosition pos) {482 if (ExtremePoints.Add(pos)) {483 var rs = CalculateResidualSpace(new Vector3D(pos));484 ResidualSpace.Add(pos, rs);485 // Check if the existing extreme points are shadowed by the new point486 // This is, their residual space fit entirely into the residual space of the new point487 foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {488 if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {489 ExtremePoints.Remove(ep);490 ResidualSpace.Remove(ep);491 }492 }493 return true;494 }495 return false;496 }497 498 #region Projections499 500 private Vector3D ProjectBackward(Vector3D pos) {501 var line = new Line3D(pos, new Vector3D(0, 0, -1));502 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })503 .Select(x => new Plane3D(x.Position, x.Item, Side.Front))504 .Concat(new[] { new Plane3D(BinShape, Side.Back) })505 .Select(x => x.Intersect(line))506 .Where(x => x != null && x.Z <= pos.Z)507 .MaxItems(x => x.Z).First();508 }509 510 private Vector3D ProjectLeft(Vector3D pos) {511 var line = new Line3D(pos, new Vector3D(-1, 0, 0));512 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })513 .Select(x => new Plane3D(x.Position, x.Item, Side.Right))514 .Concat(new[] { new Plane3D(BinShape, Side.Left) })515 .Select(x => x.Intersect(line))516 .Where(x => x != null && x.X <= pos.X)517 .MaxItems(x => x.X).First();518 }519 520 private Vector3D ProjectDown(Vector3D pos) {521 var line = new Line3D(pos, new Vector3D(0, -1, 0));522 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })523 .Select(x => new Plane3D(x.Position, x.Item, Side.Top))524 .Concat(new[] { new Plane3D(BinShape, Side.Bottom) })525 .Select(x => x.Intersect(line))526 .Where(x => x != null && x.Y <= pos.Y)527 .MaxItems(x => x.Y).First();528 }529 530 private Vector3D ProjectForward(Vector3D pos) {531 var line = new Line3D(pos, new Vector3D(0, 0, 1));532 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })533 .Select(x => new Plane3D(x.Position, x.Item, Side.Back))534 .Concat(new[] { new Plane3D(BinShape, Side.Front) })535 .Select(x => x.Intersect(line))536 .Where(x => x != null && x.Z >= pos.Z)537 .MinItems(x => x.Z).First();538 }539 540 private Vector3D ProjectRight(Vector3D pos) {541 var line = new Line3D(pos, new Vector3D(1, 0, 0));542 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })543 .Select(x => new Plane3D(x.Position, x.Item, Side.Left))544 .Concat(new[] { new Plane3D(BinShape, Side.Right) })545 .Select(x => x.Intersect(line))546 .Where(x => x != null && x.X >= pos.X)547 .MinItems(x => x.X).First();548 }549 550 private Vector3D ProjectUp(Vector3D pos) {551 var line = new Line3D(pos, new Vector3D(0, 1, 0));552 return Items.Select(x => new { Item = x.Value, Position = Positions[x.Key] })553 .Select(x => new Plane3D(x.Position, x.Item, Side.Bottom))554 .Concat(new[] { new Plane3D(BinShape, Side.Top) })555 .Select(x => x.Intersect(line))556 .Where(x => x != null && x.Y >= pos.Y)557 .MinItems(x => x.Y).First();558 }559 #endregion560 561 #region Get items562 563 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {564 var line = new Line3D(pos, new Vector3D(0, 1, 0));565 return Items.Select(x => new {566 Item = x.Value,567 Position = Positions[x.Key],568 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Bottom))569 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)570 .Select(x => Tuple.Create(x.Position, x.Item));571 }572 573 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsInfront(PackingPosition pos) {574 var line = new Line3D(pos, new Vector3D(0, 0, 1));575 return Items.Select(x => new {576 Item = x.Value,577 Position = Positions[x.Key],578 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Back))579 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)580 .Select(x => Tuple.Create(x.Position, x.Item));581 }582 583 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnRight(PackingPosition pos) {584 var line = new Line3D(pos, new Vector3D(1, 0, 0));585 return Items.Select(x => new {586 Item = x.Value,587 Position = Positions[x.Key],588 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Left))589 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)590 .Select(x => Tuple.Create(x.Position, x.Item));591 }592 593 326 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBelow(PackingPosition pos) { 594 327 var line = new Line3D(pos, new Vector3D(0, 1, 0)); … … 601 334 } 602 335 603 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsBehind(PackingPosition pos) {604 var line = new Line3D(pos, new Vector3D(0, 0, 1));605 return Items.Select(x => new {606 Item = x.Value,607 Position = Positions[x.Key],608 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Front))609 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)610 .Select(x => Tuple.Create(x.Position, x.Item));611 }612 613 private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsOnLeft(PackingPosition pos) {614 var line = new Line3D(pos, new Vector3D(1, 0, 0));615 return Items.Select(x => new {616 Item = x.Value,617 Position = Positions[x.Key],618 Intersection = line.Intersect(new Plane3D(Positions[x.Key], x.Value, Side.Right))619 }).Where(x => x.Intersection != null && x.Intersection.Y >= pos.Y)620 .Select(x => Tuple.Create(x.Position, x.Item));621 }622 623 336 #endregion 624 625 626 627 /// <summary>628 /// Updates the resiual space for a packing item.629 /// </summary>630 /// <param name="item"></param>631 /// <param name="pos"></param>632 public void UpdateResidualSpace(PackingItem item, PackingPosition pos) {633 foreach (var ep in ExtremePoints.ToList()) {634 var rs = ResidualSpace[ep];635 var depth = pos.Rotated ? item.Width : item.Depth;636 var width = pos.Rotated ? item.Depth : item.Width;637 var changed = false;638 if (ep.Z >= pos.Z && ep.Z < pos.Z + depth) {639 if (ep.X <= pos.X && ep.Y >= pos.Y && ep.Y < pos.Y + item.Height) {640 var diff = pos.X - ep.X;641 var newRSX = Math.Min(rs.Item1, diff);642 rs = Tuple.Create(newRSX, rs.Item2, rs.Item3);643 changed = true;644 }645 if (ep.Y <= pos.Y && ep.X >= pos.X && ep.X < pos.X + width) {646 var diff = pos.Y - ep.Y;647 var newRSY = Math.Min(rs.Item2, diff);648 rs = Tuple.Create(rs.Item1, newRSY, rs.Item3);649 changed = true;650 }651 }652 653 if (ep.Z <= pos.Z &&654 ep.Y >= pos.Y && ep.Y < pos.Y + item.Height &&655 ep.X >= pos.X && ep.X < pos.X + width) {656 var diff = pos.Z - ep.Z;657 var newRSZ = Math.Min(rs.Item3, diff);658 rs = Tuple.Create(rs.Item1, rs.Item2, newRSZ);659 changed = true;660 }661 662 if (changed) {663 if (IsNonZero(rs) && !IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), rs)) {664 ResidualSpace[ep] = rs;665 } else {666 ExtremePoints.Remove(ep);667 ResidualSpace.Remove(ep);668 }669 }670 }671 return;672 }673 337 } 674 338 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/ExtremePointPermutationDecoder.cs
r15473 r15488 30 30 using HeuristicLab.Common; 31 31 using HeuristicLab.Problems.BinPacking3D.Packer; 32 using HeuristicLab.Parameters; 33 using HeuristicLab.Data; 32 34 33 35 namespace HeuristicLab.Problems.BinPacking3D.Encoding { … … 38 40 [Item("Extreme-point Permutation Decoder (3d) Base", "Base class for 3d decoders")] 39 41 [StorableClass] 40 public class ExtremePointPermutationDecoder : Item, IDecoder<Permutation> 41 //where TBinPacker : BinPacker, new () 42 { 42 public class ExtremePointPermutationDecoder : ParameterizedNamedItem, IDecoder<Permutation> { 43 44 [Storable] 45 private IValueParameter<EnumValue<FittingMethod>> fittingMethodParameter; 46 public IValueParameter<EnumValue<FittingMethod>> FittingMethodParameter { 47 get { return fittingMethodParameter; } 48 } 49 50 public FittingMethod FittingMethod { 51 get { return fittingMethodParameter.Value.Value; } 52 set { fittingMethodParameter.Value.Value = value; } 53 } 54 55 [Storable] 56 private readonly IValueParameter<EnumValue<ExtremePointCreationMethod>> extremePointCreationMethodParameter; 57 public IValueParameter<EnumValue<ExtremePointCreationMethod>> ExtremePointCreationMethodParameter { 58 get { return extremePointCreationMethodParameter; } 59 } 60 61 public ExtremePointCreationMethod ExtremePointCreationMethod { 62 get { return extremePointCreationMethodParameter.Value.Value; } 63 set { extremePointCreationMethodParameter.Value.Value = value; } 64 } 43 65 44 66 [StorableConstructor] … … 46 68 protected ExtremePointPermutationDecoder(ExtremePointPermutationDecoder original, Cloner cloner) 47 69 : base(original, cloner) { 70 fittingMethodParameter = cloner.Clone(original.fittingMethodParameter); 71 //_binPacker = cloner.Clone(original._binPacker); 48 72 } 73 public ExtremePointPermutationDecoder() { 74 Parameters.Add(fittingMethodParameter = 75 new ValueParameter<EnumValue<FittingMethod>>("Fitting Method", 76 "The fitting method that the decoder uses.", 77 new EnumValue<FittingMethod>(FittingMethod.FirstFit))); 49 78 50 /// <summary> 51 /// Creates an extrem point based permutation decoder 52 /// </summary> 53 /// <param name="binPacker">Contains the packing algorithm for packing the items</param> 54 public ExtremePointPermutationDecoder(BinPacker binPacker) : base() { 55 _binPacker = binPacker; 79 Parameters.Add(extremePointCreationMethodParameter = 80 new ValueParameter<EnumValue<ExtremePointCreationMethod>>("Extreme Point Generation Method", 81 "The Extreme point generation method that the decoder uses.", 82 new EnumValue<ExtremePointCreationMethod>(ExtremePointCreationMethod.PointProjection))); 56 83 } 57 84 … … 60 87 } 61 88 89 /*[Storable] 62 90 BinPacker _binPacker; 63 91 */ 64 92 /// <summary> 65 93 /// Creates a solution for displaying it on the HEAL gui … … 70 98 /// <param name="useStackingConstraints"></param> 71 99 /// <returns></returns> 72 public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) { 100 public Solution Decode(Permutation permutation, PackingShape binShape, IList<PackingItem> items,bool useStackingConstraints) { 101 var binPacker = BinPackerFactory.CreateBinPacker(FittingMethod); 73 102 Solution solution = new Solution(binShape, useExtremePoints: true, stackingConstraints: useStackingConstraints); 74 foreach (var packedBin in _binPacker.PackItems(permutation, binShape, items, useStackingConstraints)) {103 foreach (var packedBin in binPacker.PackItems(permutation, binShape, items, ExtremePointCreationMethod, useStackingConstraints)) { 75 104 solution.Bins.Add(packedBin); 76 105 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Encoding/PermutationProblem.cs
r15473 r15488 50 50 public PermutationProblem() 51 51 : base() { 52 Decoder = new ExtremePointPermutationDecoder( new BinPackerFirstFit()); // default decoder52 Decoder = new ExtremePointPermutationDecoder(); // default decoder 53 53 54 54 Encoding = new Encodings.PermutationEncoding.PermutationEncoding(EncodedSolutionName, Items.Count, PermutationTypes.Absolute); -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Line3D.cs
r15454 r15488 29 29 return plane.Intersect(this); 30 30 } 31 32 public Vector3D Intersect(Line3D line) { 33 double r = 0; 34 double s = 0; 35 36 if (Direction.X != 0) { 37 r = (line.Point.X - this.Point.X) / (double)Direction.X; 38 } else if (Direction.Y != 0) { 39 r = (line.Point.Y - this.Point.Y) / (double)Direction.Y; 40 } else if (Direction.Z != 0) { 41 r = (line.Point.Z - this.Point.Z) / (double)Direction.Z; 42 } 43 44 if (line.Direction.X != 0) { 45 s = (this.Point.X - line.Point.X) / (double)line.Direction.X; 46 } else if (line.Direction.Y != 0) { 47 s = (this.Point.Y - line.Point.Y) / (double)line.Direction.Y; 48 } else if (line.Direction.Z != 0) { 49 s = (this.Point.Z - line.Point.Z) / (double)line.Direction.Z; 50 } 51 52 var a = r * this.Direction + this.Point; 53 var b = s * line.Direction + line.Point; 54 var c = a.Equals(b); 55 if (s!=0 && r!=0 && a.Equals(b)) { 56 57 return a; 58 } 59 60 return null; 61 } 31 62 } 32 63 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Geometry/Vector3D.cs
r15454 r15488 6 6 7 7 namespace HeuristicLab.Problems.BinPacking3D.Geometry { 8 internalclass Vector3D {8 public class Vector3D { 9 9 10 10 public int X { get; set; } … … 23 23 Z = pos.Z; 24 24 } 25 26 public PackingPosition ToPackingPosition(int assignedBin) { 27 return new PackingPosition(assignedBin, X, Y, Z); 28 } 29 25 30 public static Vector3D AlongX(Vector3D pos, PackingItem item) { 26 31 return new Vector3D( … … 86 91 return new Vector3D(a * b.X, a * b.Y, a * b.Z); 87 92 } 93 94 public static Vector3D operator *(double a, Vector3D b) { 95 return new Vector3D((int)(a * b.X), (int)(a * b.Y), (int)(a * b.Z)); 96 } 97 88 98 public static Vector3D operator *(Vector3D a, int b) { 89 99 return new Vector3D(a.X * b, a.Y * b, a.Z * b); 90 100 } 101 102 public static Vector3D operator *(Vector3D a, double b) { 103 return new Vector3D((int)(b * a.X), (int)(b * a.Y), (int)(b * a.Z)); 104 } 105 91 106 public static Vector3D operator +(Vector3D a, Vector3D b) { 92 107 return new Vector3D(a.X + b.X, a.Y + b.Y, a.Z + b.Z); -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPacker.cs
r15473 r15488 20 20 #endregion 21 21 22 using HeuristicLab.Common; 22 23 using HeuristicLab.Core; 23 24 using HeuristicLab.Encodings.PermutationEncoding; 24 25 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 25 26 using HeuristicLab.Problems.BinPacking3D; 27 using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation; 26 28 using System; 27 29 using System.Collections.Generic; … … 31 33 32 34 namespace HeuristicLab.Problems.BinPacking3D.Packer { 33 [Item("BinPacker", "A class for packing bins for the 3D bin-packer problem.")] 34 [StorableClass] 35 public abstract class BinPacker { 35 public abstract class BinPacker : Item { 36 37 /* 38 [Storable] 39 IPositionFinder PositionFinder 36 40 41 */ 42 43 #region Constructors for HEAL 44 45 46 [StorableConstructor] 47 protected BinPacker(bool deserializing) : base(deserializing) { } 48 49 protected BinPacker(BinPacker original, Cloner cloner) 50 : base(original, cloner) { 51 //this.PositionFinder = original.PositionFinder; 52 } 53 54 #endregion 55 37 56 public BinPacker() { } 38 57 … … 45 64 /// <param name="useStackingConstraints">Flag for using stacking constraints</param> 46 65 /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns> 47 public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints);66 public abstract IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints); 48 67 49 68 /// <summary> … … 54 73 /// <param name="packingItem"></param> 55 74 /// <param name="position"></param> 56 protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, bool useStackingConstraints) { 57 75 protected virtual void PackItem(BinPacking3D packingBin, int itemId, PackingItem packingItem, PackingPosition position, IExtremePointCreator extremePointCreator, bool useStackingConstraints) { 76 if (!CheckItemDimensions(packingBin, packingItem, position)) { 77 throw new BinPacking3DException($"The dimensions of the given item exceeds the bin dimensions. " + 78 $"Bin: ({packingBin.BinShape.Width} {packingBin.BinShape.Depth} {packingBin.BinShape.Height})" + 79 $"Item: ({packingItem.Width} {packingItem.Depth} {packingItem.Height})"); 80 } 58 81 packingBin.PackItem(itemId, packingItem, position); 59 packingBin.UpdateResidualSpace(packingItem, position);60 packingBin.UpdateExtremePoints(packingItem, position, useStackingConstraints);82 extremePointCreator.UpdateExtremePoints(packingBin, packingItem, position); 83 extremePointCreator.UpdateResidualSpace(packingBin, packingItem, position); 61 84 } 62 85 … … 79 102 return packingBin.ExtremePoints.Where(x => packingBin.IsPositionFeasible(newItem, x, useStackingConstraints)).FirstOrDefault(); 80 103 } 104 105 /// <summary> 106 /// Compares the dimensions of a given item and the current bin. 107 /// </summary> 108 /// <param name="item"></param> 109 /// <returns>Returns true if the dimensions of an given item are less or equal to the bin.</returns> 110 private bool CheckItemDimensions(BinPacking3D packingBin, PackingItem item, PackingPosition itemPosition) { 111 var width = itemPosition.Rotated ? item.Depth : item.Width; 112 var depth = itemPosition.Rotated ? item.Width : item.Depth; 113 return packingBin.BinShape.Width >= width && packingBin.BinShape.Height >= item.Height && packingBin.BinShape.Depth >= depth; 114 } 81 115 } 82 116 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFirstFit.cs
r15473 r15488 20 20 #endregion 21 21 22 using HeuristicLab.Common; 22 23 using HeuristicLab.Core; 23 24 using HeuristicLab.Encodings.PermutationEncoding; 24 25 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 26 using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation; 25 27 using System; 26 28 using System.Collections.Generic; … … 30 32 31 33 namespace HeuristicLab.Problems.BinPacking3D.Packer { 34 public class BinPackerFirstFit : BinPacker { 35 #region Constructors for HEAL 36 [StorableConstructor] 37 protected BinPackerFirstFit(bool deserializing) : base(deserializing) { } 32 38 33 [Item("BinPackerFirstFit", "A class for packing bins for the 3D bin-packer problem. It uses a first fit algorithm")] 34 [StorableClass] 35 public class BinPackerFirstFit : BinPacker { 39 protected BinPackerFirstFit(BinPackerFirstFit original, Cloner cloner) 40 : base(original, cloner) { 41 } 42 43 public override IDeepCloneable Clone(Cloner cloner) { 44 return new BinPackerFirstFit(this, cloner); 45 } 46 #endregion 36 47 37 48 public BinPackerFirstFit() : base() { } … … 41 52 /// </summary> 42 53 /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns> 43 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {54 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) { 44 55 IList<BinPacking3D> packingList = new List<BinPacking3D>(); 45 56 IList<int> remainingIds = new List<int>(sortedItems); … … 47 58 while (remainingIds.Count > 0) { 48 59 BinPacking3D packingBin = new BinPacking3D(binShape); 49 PackRemainingItems(ref remainingIds, ref packingBin, items, useStackingConstraints, null);60 PackRemainingItems(ref remainingIds, ref packingBin, items, epGenerationMethod, useStackingConstraints, null); 50 61 packingList.Add(packingBin); 51 62 } … … 60 71 /// <param name="items">List of packing items. Some of the items will be assigned to the BinPacking3D object</param> 61 72 /// <param name="packingBin">This object will be filled with some of the given items</param> 62 protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, bool useStackingConstraints, Dictionary<int, bool> rotationArray) {63 73 protected void PackRemainingItems(ref IList<int> remainingIds, ref BinPacking3D packingBin, IList<PackingItem> items, ExtremePointCreationMethod epCreationMethod, bool useStackingConstraints, Dictionary<int, bool> rotationArray) { 74 IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epCreationMethod, useStackingConstraints); 64 75 foreach (var itemId in new List<int>(remainingIds)) { 65 76 bool rotated = rotationArray == null ? false : rotationArray[itemId]; … … 67 78 // if a valid packing position could be found, the current item can be added to the given bin 68 79 if (position != null) { 69 PackItem(packingBin, itemId, items[itemId], position, useStackingConstraints);80 PackItem(packingBin, itemId, items[itemId], position, extremePointCreator, useStackingConstraints); 70 81 remainingIds.Remove(itemId); 71 82 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFreeVolumeBestFit.cs
r15473 r15488 20 20 #endregion 21 21 22 using HeuristicLab.Common; 22 23 using HeuristicLab.Core; 23 24 using HeuristicLab.Encodings.PermutationEncoding; 24 25 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 26 using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation; 25 27 using System; 26 28 using System.Collections.Generic; … … 30 32 31 33 namespace HeuristicLab.Problems.BinPacking3D.Packer { 32 [Item("BinPackerFreeVolumeBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the free volume.")]33 [StorableClass]34 34 public class BinPackerFreeVolumeBestFit : BinPacker { 35 36 #region Constructors for HEAL 37 [StorableConstructor] 38 protected BinPackerFreeVolumeBestFit(bool deserializing) : base(deserializing) { } 39 40 protected BinPackerFreeVolumeBestFit(BinPackerFreeVolumeBestFit original, Cloner cloner) 41 : base(original, cloner) { 42 } 43 44 public override IDeepCloneable Clone(Cloner cloner) { 45 return new BinPackerFreeVolumeBestFit(this, cloner); 46 } 47 #endregion 35 48 36 49 public BinPackerFreeVolumeBestFit() : base() { } … … 48 61 /// <param name="useStackingConstraints"></param> 49 62 /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns> 50 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {63 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) { 51 64 IList<BinPacking3D> packingList = new List<BinPacking3D>(); 52 65 IList<int> remainingIds = new List<int>(sortedItems); 53 66 IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints); 54 67 foreach (int remainingId in remainingIds) { 55 68 var sortedBins = packingList.OrderBy(x => x.FreeVolume); … … 64 77 var bin = packingBin; 65 78 if (positionFound) { 66 PackItem(bin, remainingId, item, position, useStackingConstraints);79 PackItem(bin, remainingId, item, position, extremePointCreator, useStackingConstraints); 67 80 break; 68 81 } … … 74 87 75 88 if (position == null) { 76 throw new InvalidOperationException("Item " + remainingId + " cannot be packed in empty bin.");89 throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin."); 77 90 } 78 91 79 PackItem(packingBin, remainingId, item, position, useStackingConstraints);92 PackItem(packingBin, remainingId, item, position, extremePointCreator, useStackingConstraints); 80 93 packingList.Add(packingBin); 81 94 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerResidualSpaceBestFit.cs
r15473 r15488 20 20 #endregion 21 21 22 using HeuristicLab.Common; 22 23 using HeuristicLab.Core; 23 24 using HeuristicLab.Encodings.PermutationEncoding; 24 25 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; 26 using HeuristicLab.Problems.BinPacking3D.ExtremePointCreation; 25 27 using System; 26 28 using System.Collections.Generic; … … 30 32 31 33 namespace HeuristicLab.Problems.BinPacking3D.Packer { 32 [Item("BinPackerResidualSpaceBestFit", "A class for packing bins for the 3D bin-packer problem. It uses a best fit algortihm depending on the residual space.")]33 [StorableClass]34 34 public class BinPackerResidualSpaceBestFit : BinPacker { 35 36 #region Constructors for HEAL 37 [StorableConstructor] 38 protected BinPackerResidualSpaceBestFit(bool deserializing) : base(deserializing) { } 39 40 protected BinPackerResidualSpaceBestFit(BinPackerResidualSpaceBestFit original, Cloner cloner) 41 : base(original, cloner) { 42 } 43 44 public override IDeepCloneable Clone(Cloner cloner) { 45 return new BinPackerResidualSpaceBestFit(this, cloner); 46 } 47 #endregion 35 48 36 49 public BinPackerResidualSpaceBestFit() : base() { } … … 42 55 /// </summary> 43 56 /// <returns>Returns a collection of bin packing 3d objects. Each object represents a bin and the packed items</returns> 44 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, bool useStackingConstraints) {57 public override IList<BinPacking3D> PackItems(Permutation sortedItems, PackingShape binShape, IList<PackingItem> items, ExtremePointCreationMethod epGenerationMethod, bool useStackingConstraints) { 45 58 IList<BinPacking3D> packingList = new List<BinPacking3D>(); 46 59 IList<int> remainingIds = new List<int>(sortedItems); 60 IExtremePointCreator extremePointCreator = ExtremePointCreatorFactory.CreateExtremePointCreator(epGenerationMethod, useStackingConstraints); 47 61 bool rotated = false; 48 62 … … 56 70 if (point.Item1.IsPositionFeasible(item, point.Item2, useStackingConstraints)) { 57 71 var binPacking = point.Item1; 58 PackItem(binPacking, remainingId, item, point.Item2, useStackingConstraints);72 PackItem(binPacking, remainingId, item, point.Item2, extremePointCreator, useStackingConstraints); 59 73 packed = true; 60 74 break; … … 66 80 var position = FindPackingPositionForItem(binPacking, item, useStackingConstraints, rotated); 67 81 if (position != null) { 68 PackItem(binPacking, remainingId, item, position, useStackingConstraints);82 PackItem(binPacking, remainingId, item, position, extremePointCreator, useStackingConstraints); 69 83 } else { 70 throw new InvalidOperationException("Item " + remainingId + " cannot be packed in an empty bin.");84 throw new InvalidOperationException("Item " + remainingId + " cannot be packed into an empty bin."); 71 85 } 72 86 packingList.Add(binPacking); 73 87 } 74 88 } 75 76 89 return packingList; 77 90 } … … 110 123 (rs.Item3 - item.Depth)); 111 124 } 112 113 125 } 114 126 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
r15473 r15488 103 103 <Compile Include="2D\ProblemBase.cs" /> 104 104 <Compile Include="2D\Solution.cs" /> 105 <Compile Include="3D\BinPacking3DException.cs" /> 106 <Compile Include="3D\ExtremePointCreation\ExtremePointCreatorFactory.cs" /> 107 <Compile Include="3D\ExtremePointCreation\ExtremePointCreator.cs" /> 108 <Compile Include="3D\ExtremePointCreation\IExtremePointCreator.cs" /> 109 <Compile Include="3D\ExtremePointCreation\LineProjectionBasedEPCreator.cs" /> 110 <Compile Include="3D\ExtremePointCreation\PointProjectionBasedEPCreator.cs" /> 111 <Compile Include="3D\Geometry\Edge3D.cs" /> 105 112 <Compile Include="3D\Packer\BinPacker.cs" /> 106 113 <Compile Include="3D\Packer\BinPackerFactory.cs" /> … … 123 130 <Compile Include="3D\Encoding\IDecoder.cs" /> 124 131 <Compile Include="3D\Evaluators\IEvaluator.cs" /> 125 <Compile Include="3D\ IOperator.cs" />132 <Compile Include="3D\Sorting\IOperator.cs" /> 126 133 <Compile Include="3D\Evaluators\MoveEvaluatorBase.cs" /> 127 134 <Compile Include="3D\PackingItem.cs" />
Note: See TracChangeset
for help on using the changeset viewer.