Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: The largest Triangle that can fit in convex hull
Date: Thu, 7 May 2009 21:25:03 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 103
Message-ID: <gtvjjf$1k9$1@fred.mathworks.com>
References: <b9bb3ca1-66f4-4c5f-9553-cd970bfb7eb1@v4g2000vba.googlegroups.com> <a3eecd7c-3fb1-4f8f-ba6c-0e39057b0279@j12g2000vbl.googlegroups.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-02-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1241731503 1673 172.30.248.37 (7 May 2009 21:25:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 7 May 2009 21:25:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:538363


Dodo <lovelygirl_2220@hotmail.com> wrote in message <a3eecd7c-3fb1-4f8f-ba6c-0e39057b0279@j12g2000vbl.googlegroups.com>...
> On May 4, 9:18?pm, "Damian Sheehy" <Damian.She...@mathworks.com>
> wrote:
> > Before anyone can attempt to answer that question, you have to define wha=
> t
> > you mean by "large".
> > Do you mean thetrianglethat has the largest diameter, thetrianglethat
> > has the largest area, or what ?
> > Also, do you need an accurate solution or are you willing to accept an
> > approximation?
> >
> > Damian
> >
> > "Dodo" <lovelygirl_2...@hotmail.com> wrote in message
> >
> > news:b9bb3ca1-66f4-4c5f-9553-cd970bfb7eb1@v4g2000vba.googlegroups.com...
> >
> > > Hi
> > > Could any one tell me how to find the largesttrianglecanfitintoa
> > >convexhull.
> > > Thanks in advance.
> 
> Hi Damian
> i want the largest-area triangle
> i want an accurate solution but if there is not you can tell me an
> approximate one and i will test it
> Thanks in advance

My gut says that this is just a combinatorial problem.
The nice thing is it is easily vectorized, almost trivially
so, and it is only O(n^3) in the number of vertices
of the convex hull. Since convex hulls tend to have
a limited number of points, I don't see much of a
problem.

Given the N vertices of the convex hull, pick any
subset of three of them. There are nchoosek(N,3)
such combinations. Each subset of vertices defines
a triangle. Pick the one with the largest area.

V = randn(100,2);
edges = convhulln(V)
edges =
    49     2
     2    68
    68    27
    27    14
    14    44
    44    95
    95    84
    84    28
    28    49

hlist = unique(edges(:))
hlist =
     2
    14
    27
    28
    44
    49
    68
    84
    95

There are exactly 84 distinct triangles that can
be created from these points.

nchoosek(9,3)
ans =
    84

tri = nchoosek(hlist,3);
A = V(tri(:,1),:);
B = V(tri(:,2),:);
C = V(tri(:,3),:);
nt = size(tri,1);

areas = sum(abs(cross([B-A,zeros(nt,1)],[C-A,zeros(nt,1)])/2),2);

That triangle with maximum area:

[maxarea,ind] = max(areas);
maxarea =
       7.5423

ind =
     6

The vertices that contributed to that triangle:
tri(ind,:)
ans =
     2    14    84

The vertices that define the triangle:
V(tri(ind,:),:)
ans =
      -1.6656      -2.2023
       2.1832     0.055744
     -0.99209       2.1122

HTH,
John