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.

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.