From: sterner@strdev.jhuapl.edu (Ray Sterner)
Subject: Re: Calculate convex hull of scattered data?
Message-ID: <sterner.795463846@strdev.jhuapl.edu>
Date: Fri, 17 Mar 1995 18:10:46 GMT

Sender: usenet@aplcenmp.apl.jhu.edu
Nntp-Posting-Host: strdev.jhuapl.edu

art.croucher@jhuapl.edu writes:

>I'm trying to calculate the convex hull which encloses a scattered data 
>set.  The JHU/APL CONVEXHULL routine didn't work, presumably because 
>the data set isn't a polygon.  Does anyone have a routine that will 
>calculate either a convex hull or a polygon suitable for input to 
>CONVEXHULL?

  I posted a solution to this but just recieved email from David
  Stern with a much simpler and faster solution.  Here it is:

----------------------------------------------------------------------
I saw your messages RE convex hulls on the newsgroup.  The TRIANGULATE
procedure returns the indices of the points on the convex hull as an
optional parameter.  It is efficient, O(n log(n)), and simple.  Here's
an example:

n = 1000                        ;Make some random data
x = randomn(seed, n)
y = randomn(seed, n)

triangulate, x, y, tr, b        ;b contains the vertices on the hull
plot, x, y, psym=1
b = [b, b(0)]                   ;Close the polygon
plots, x(b), y(b)               ;Plot the convex hull
end

Hope this helps...
David
----------------------------------------------------------------------

  I tried 10000 points and it only took a few seconds (unlike my
  convexhull routine which takes a few minutes for that number of
  points).

  Ray Sterner                     sterner@tesla.jhuapl.edu 
  The Johns Hopkins University    North latitude 39.16 degrees.
  Applied Physics Laboratory      West longitude 76.90 degrees.
  Laurel, MD 20723-6099
  WWW Home page:  ftp://fermi.jhuapl.edu/www/s1r/people/res/res.html