Stuart’s MATLAB Videos

Watch and Learn

Puzzler: Difficult algorithm development challenge

This week’s puzzler is significantly harder than others we have done in the past, I would be surprised (and delighted) to see an answer before I go home tonight… The challenge is shown below. Given a group of trees, find the rectangular bounding box in the x-y direction that holds all the trees. Once you have that bounding box, look for the largest rectangle (by area) that can be made inside the bounding box. Of course, this rectangle can have no trees in the interior. bigfield.jpg Since this is a more difficult problem, you may want to look at the first video to see the outline for an algorithm to solve this:
Video Player is loading.
Current Time 0:00
Duration 0:00
Loaded: 0%
Stream Type LIVE
Remaining Time 0:00
 
1x
  • Chapters
  • descriptions off, selected
  • captions off, selected
  • en (Main), selected

    If you do not want to attempt this challenge on your own, then feel free to watch the code review of my solution in the video below:
    Video Player is loading.
    Current Time 0:00
    Duration 8:16
    Loaded: 0%
    Stream Type LIVE
    Remaining Time 8:16
     
    1x
    • Chapters
    • descriptions off, selected
    • captions off, selected
    • en (Main), selected

      This video walks through the described algorithm line by line. If you come up with a solution, please post it in the comments below. I have already posted the code from the video as the first comment. Here is the code that you can use to test and visualize your solution with. Simply make main.m in this form:
      
       function [bigArea, boundBox] = main(trees)
       % bigArea and boundBox are structures that describe a rectangle and
       % contain the fields:
       % bigArea.x      X of lower left corner
       % bigArea.y      Y of lower left corner
       % bigArea.width Width of rectangle
       % bigArea.height Height of rectangle
       
       % bigArea is the largest open area
       % boundBox is the bounding box of the entire set of trees
       
      Here is the code to get you started:
      
       clc
       n = 5;
       
       trees.x = rand(1,n);
       trees.y = rand(1,n);
       [bigArea, boundBox] = main(trees);
       
       clf
       rectangle('position', [ bigArea.x  bigArea.y  bigArea.width  bigArea.height], ...
                'facecolor', [1 1 0])
       
       rectangle('position', [boundBox.x boundBox.y boundBox.width boundBox.height])
       axis([0 1 0 1])
       
       line(trees.x,trees.y, ...
                 'color',[0 1 0], ...
                'marker','^'    , ...
             'linestyle','none' , ...
            'markersize',5      , ...
             'linewidth',5)
       
      Remember to use the <pre><code> and </code></pre> tags around your code in the comments.
      |
      • print

      Comments

      To leave a comment, please click here to sign in to your MathWorks Account or create a new one.

      Loading...
      Go to top of page