Largest area triangle inside a convex hull

How to draw a largest area triangle inside a convex hull, so that that the triangle vertices lie on the the convex hull, can we use polyarea() to calculate the area of that triangle ?

[Avi Pal]

will DelaunayTri help in this case ?

Answer 1

[Image Analyst]

Well there's John's suite: http://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects - I think that will work, because your object is convex.

[Avi Pal]

@Image Analyst : the suite talks about minimum area triangle;

Answer 2

[Image Analyst]

Well you could always try the brute force method. Luckily there are so few points that it's very fast (like 10 milliseconds).

clc;    % Clear the command window.
close all;  % Close all figures (except those of imtool.)
clear;  % Erase all existing variables.
workspace;  % Make sure the workspace panel is showing.
fontSize = 20;
format compact;

% Make sample data:
x = randn(150,1);
y = randn(150,1);
plot(x,y,'ro');
xlabel('X', 'FontSize', fontSize);
ylabel('Y', 'FontSize', fontSize);
title('Demo to find largest triangle inside convex hull', 'FontSize', fontSize);
grid on;
% Get convex hull
k = convhull(x,y)
ch_x = x(k)
ch_y = y(k)
hold on;
plot(ch_x, ch_y, 'b', 'LineWidth', 2);
numberOfCHPoints = length(k)
% Enlarge figure to full screen.
set(gcf, 'units','normalized','outerposition',[0 0 1 1]);

% Find largest inscribed triangle
tic; % Start timing
maxArea = 0;
for k1 = 1 : numberOfCHPoints
  for k2 = k1+1 : numberOfCHPoints
    for k3 = k2+1 : numberOfCHPoints
      x1 = ch_x(k1);
      y1 = ch_y(k1);
      x2 = ch_x(k2);
      y2 = ch_y(k2);
      x3 = ch_x(k3);
      y3 = ch_y(k3);
      area = polyarea([x1 x2 x3], [y1 y2 y3]);
      if area > maxArea
        best_k1 = k1;
        best_k2 = k2;
        best_k3 = k3;
        maxArea = area
      end
    end
  end
end
best_x = [ch_x(best_k1), ch_x(best_k2), ch_x(best_k3), ch_x(best_k1)]
best_y = [ch_y(best_k1), ch_y(best_k2), ch_y(best_k3), ch_y(best_k1)]
toc; % Stop timing.
plot(best_x, best_y, 'g-', 'LineWidth', 2);
legend('Original Points', 'Convex Hull', 'Largest Inscribed Triangle');

message = sprintf('The largest triangular area = %.3f', maxArea);
msgbox(message);

Answer 3

[John D'Errico]

Oh geez. Why can't I retire?

Consider any pair of vertices from the convex hull. What one single other vertex from the set of vertices on the convex hull will form a triangle of maximal area? Yes, the answer is trivial, since given the base of a triangle, the area is maximized if you maximize the height!

My point is, this just reduces to a search over all nchoosek(n,2) pairs of vertices of the convex hull. Its not a very large set of pairs. In fact, if you want to get tricky, you can even do slightly better than this, by intelligently sorting the pairs of vertices to test first. This presort will let you stop before you test every pair of vertices. In any event, I won't write the code here.