Changeset 15307


Ignore:
Timestamp:
08/04/17 23:45:08 (2 months ago)
Author:
abeham
Message:

#2817:

  • Added checkbox to control showing extreme points in visualization
    • Automatically determine size of extreme point cubes
  • Fixed some bugs in extreme point generation
Location:
branches/2817-BinPackingSpeedup
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml

    r15167 r15307  
    3232             Focusable="true"
    3333             >
    34     <Grid>
    35         <Border BorderThickness="1" Background="{DynamicResource {x:Static SystemColors.ControlBrushKey}}">
    36             <Viewport3D Name="viewport3D1" >
     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">
     37            <Viewport3D Name="viewport3D1" Margin="0,-1,0,0" >
    3738                <Viewport3D.Camera>
    3839                    <PerspectiveCamera x:Name="camMain" Position="0.5 8 8" LookDirection="0 -1 -1"> <!-- camera position for design time-->
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking.Views/3.3/Container3DView.xaml.cs

    r15306 r15307  
    5555    private double startAngleY;
    5656    private int selectedItemKey;
     57    private bool showExtremePoints;
    5758
    5859    private BinPacking<BinPacking3D.PackingPosition, PackingShape, PackingItem> packing;
     
    155156      }
    156157
    157       // draw extreme-points
    158       foreach (var ep in packing.ExtremePoints) {
    159         var epModel = new GeometryModel3D { Geometry = new MeshGeometry3D(), Material = new DiffuseMaterial() { Brush = new SolidColorBrush(Colors.Red) } };
    160         AddSolidCube((MeshGeometry3D)epModel.Geometry, ep.X, ep.Y, ep.Z, 10, 10, 10);
    161         modelGroup.Children.Add(epModel);
     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        }
    162167      }
    163168
     
    229234    private void Container3DView_OnMouseEnter(object sender, MouseEventArgs e) {
    230235      Focus(); // for mouse wheel events
     236    }
     237    private void showExtremePointsCheckBoxOnChecked(object sender, RoutedEventArgs e) {
     238      showExtremePoints = true;
     239      UpdateVisualization();
     240    }
     241    private void showExtremePointsCheckBoxOnUnchecked(object sender, RoutedEventArgs e) {
     242      showExtremePoints = false;
     243      UpdateVisualization();
    231244    }
    232245
     
    471484    }
    472485    #endregion
    473 
    474486  }
    475487}
  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15306 r15307  
    125125      sourcePoint = new Vector3D(position.X, position.Y, position.Z + newDepth);
    126126      if (sourcePoint.X < BinShape.Width && sourcePoint.Y < BinShape.Height && sourcePoint.Z < BinShape.Depth) {
     127        // Projecting onto the XZ-plane
     128        var below = ProjectDown(sourcePoint);
     129        var residualSpace = CalculateResidualSpace(below);
     130        if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
     131          // add only if the projected point's residual space is not a sub-space
     132          // of another extreme point's residual space
     133          var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
     134          AddExtremePoint(belowPoint);
     135        }
    127136        // Projecting onto the YZ-plane
    128137        var left = ProjectLeft(sourcePoint);
    129         var residualSpace = CalculateResidualSpace(left);
     138        residualSpace = CalculateResidualSpace(left);
    130139        if (!IsWithinResidualSpaceOfAnotherExtremePoint(left, residualSpace)) {
    131140          // add only if the projected point's residual space is not a sub-space
     
    134143          AddExtremePoint(leftPoint);
    135144        }
    136         // Projecting onto the XZ-plane
    137         var below = ProjectDown(sourcePoint);
    138         residualSpace = CalculateResidualSpace(below);
    139         if (!IsWithinResidualSpaceOfAnotherExtremePoint(below, residualSpace)) {
    140           // add only if the projected point's residual space is not a sub-space
    141           // of another extreme point's residual space
    142           var belowPoint = new PackingPosition(position.AssignedBin, below.X, below.Y, below.Z);
    143           AddExtremePoint(belowPoint);
    144         }
    145145      }
    146146    }
     
    148148    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> residualSpace) {
    149149      var eps = ExtremePoints.Where(x => pos.IsInside(x, ResidualSpace[x]));
    150       return eps.Any(x => ResidualSpace[x].Item1 >= pos.X - x.X + residualSpace.Item1
    151           && ResidualSpace[x].Item2 >= pos.Y - x.Y + residualSpace.Item2
    152           && ResidualSpace[x].Item3 >= pos.Z - x.Z + residualSpace.Item3);
     150      return eps.Any(x => IsWithinResidualSpaceOfAnotherExtremePoint(pos, residualSpace, x, ResidualSpace[x]));
     151    }
     152    private bool IsWithinResidualSpaceOfAnotherExtremePoint(Vector3D pos, Tuple<int, int, int> rsPos, PackingPosition ep, Tuple<int, int, int> rsEp) {
     153      return rsEp.Item1 >= pos.X - ep.X + rsPos.Item1
     154          && rsEp.Item2 >= pos.Y - ep.Y + rsPos.Item2
     155          && rsEp.Item3 >= pos.Z - ep.Z + rsPos.Item3;
    153156    }
    154157
    155158    private bool AddExtremePoint(PackingPosition pos) {
    156159      if (ExtremePoints.Add(pos)) {
    157         ResidualSpace.Add(pos, Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z));
     160        var rs = Tuple.Create(BinShape.Width - pos.X, BinShape.Height - pos.Y, BinShape.Depth - pos.Z);
     161        ResidualSpace.Add(pos, rs);
     162        // Check if existing extreme points are shadowed by the new point
     163        // That is, their residual space fit entirely into the residual space of the new point
     164        foreach (var ep in ExtremePoints.Where(x => x != pos && new Vector3D(x).IsInside(pos, rs)).ToList()) {
     165          if (IsWithinResidualSpaceOfAnotherExtremePoint(new Vector3D(ep), ResidualSpace[ep], pos, rs)) {
     166            ExtremePoints.Remove(ep);
     167            ResidualSpace.Remove(ep);
     168          }
     169        }
    158170        return true;
    159171      }
Note: See TracChangeset for help on using the changeset viewer.