| Re: Calculate convex hull of scattered data? [message #3760] |
Tue, 14 March 1995 05:52 |
PREUSSER
Messages: 8
Registered: March 1993
|
Junior Member |
|
|
In article <3k1ocd$7dk@aplinfo.jhuapl.edu>, art.croucher@jhuapl.edu wrote:
> 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?
One method of scattered data interpolation in IDL/PVWAVE is that of Akima
with quintic polynomials, which I have improved.
In Akima's original work ACM Algorithm 526, there are output parameters
giving the indices of the input points forming the convex hull of the
point set.
You get Alg 526 from netlib.att.com, directory netlib/toms. Of course, it
is in FORTRAN...
In IMSL/IDL there was a routine TRIANGULATE, which also returned that
list. In PV-WAVE Advantage it seems that routine has disappeared.
A.PREUSSER
--
Note my new Phone Number: -49-30-8413-3220
|
|
|
|
| Re: Calculate convex hull of scattered data? [message #3766 is a reply to message #3760] |
Mon, 13 March 1995 09:13  |
sterner
Messages: 106
Registered: February 1991
|
Senior Member |
|
|
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?
Hi Art,
I wanted to do the same thing but wasn't sure how. Your message
inspired me to think about it again, it's very easy. (I don't have
a need right now but I'm sure one will come up).
Random x,y points can be preprocessed to put them in a form
that the convexhull routine can handle. Here is an example
that first generates 100 random points, then preprocesses the
points, and finally finds the convexhull. I don't know how
far you can puch this as far as number of points goes, 1000
works ok, I'm waiting for 10,000 as I write this (several minutes
so far).
------------------------------------------------------------ -----
;------ Generate some random scatterplot data -----
a = randomu(k,100)*360 ; Random angle from 0 to 360 deg.
r = randomu(k,100) ; Random radius from 0 to 1.
polrec,r,a,/deg,x,y ; Convert to rectangular.
plot,x,y,psym=2 ; Plot.
;------ Preprocess scatterplot data --------
xm = mean(x) ; Find mean of x amd y.
ym = mean(y)
dx = x-xm ; Remove means.
dy = y-ym
recpol,dx,dy,r,a ; Conert to polar form.
is = sort(a) ; Sort on angle.
a = a(is)
r = r(is)
polrec,r,a,x2,y2 ; Convert sorted values back to rectangular
x2 = x2+xm ; Restore means.
y2 = y2+ym
;------ Find the convex hull ---------
convexhull, x2, y2, xh, yh ; Find convexhull.
oplot, xh, yh ; Plot convexhull (not closed).
------------------------------------------------------------ -----
This example assumes you have the JHU/APL/S1R IDL library:
(polrec, recpol, and convexhull)
ftp fermi.jhuapl.edu
login: anonymous
password: your email address
cd pub/idl
get README
bye
The text file README describes what is in the libraries, how to
get them, and how to set them up.
Or see the web page: ftp://fermi.jhuapl.edu/www/s1r/idl/s1rlib/local_idl.html
------------------------------------------------------------ -----
By the way, 10,000 points did work. It took a few minutes on my
HP 7/35 so I wouldn't want to do too many.
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
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
