Largest area triangle inside a convex hull
조회 수: 5 (최근 30일)
이전 댓글 표시
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 ?
답변 (3개)
Image Analyst
2012년 3월 18일
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.
Image Analyst
2012년 3월 18일
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);
댓글 수: 0
John D'Errico
2012년 3월 18일
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.
댓글 수: 0
참고 항목
카테고리
Help Center 및 File Exchange에서 Bounding Regions에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!