File Exchange Pick of the Week

Our best user submissions

Puzzler: Difficult algorithm development challenge 8

Posted by Doug Hull,

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:





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:




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.

0 views (last 30 days)  | |

Comments

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