I believe you can save a lot of time & effort following Minkler's suggestions. I have not visited the subject in about 15 years, but it resembles a popular algorithim for shading in 3D graphics. If you start with a few points and cycle through your data increasing your number of points you can quit when the successive results are small enough to fit your criteria. The only practical use I have seen for this sort of thing is academic & graphics. John Ferrell 6241 Phillippi Rd Julian NC 27283 Phone: (336)685-9606 johnferrell@earthlink.net Dixie Competition Products NSRCA 479 AMA 4190 W8CCW "My Competition is Not My Enemy" > ----- Original Message ----- > From: "Dave Tweed" > To: > Sent: Friday, November 07, 2003 5:34 PM > Subject: Re: [OT:] Looking for algorithm... > > > > David Minkler wrote: > > > > Jim Tellier wrote: > > > > Any math wizards here? I've been searching for quite a while now, but > > > > coming up empty ... I'm looking for an APPROXIMATION algorithm to > compute > > > > the surface area of a convex hull shape. Given a 3D matrix (may be > > > > either sparse or complete, but would be best if I could use sparse to > > > > save space) of surface loci, I need a "reasonably accurate" (say +/- > > > > 15-20% variance from actual true value) but *fast* approximation. > > > > Parallel or distributed algorithms would be ideal, but not a > requirement. > > > > 3D geometry was never really in my bag o' tricks :^) > > > > > > I'm assuming that you have an array of points like: > > > > > > A B D E > > > > > > C F G H > > > > > > I J K L > > > > > > That is, a regular grid of points which lay adjacent to each other in a > > > *rectangular* sort of way. It is not necessary that the spacing between > > > the points be regular, only that their spacial relationship is such that > > > the points which are next to each other in the array be next to each > > > other in 3-space. > > > > I think you're assuming far too much. > > > > When someone says "convex hull" it usually means that he just has a list > > of points, in 3-space in this case. There is no defined relationship among > > the points. The task is to *find* the convex hull (the smallest convex > > polyhedron that encloses them) and then estimate the area of *that*. > > Some (most?) of the given points won't even be on the hull at all. > > > > On the other hand, the OP does say that the array contains "surface loci", > > so perhaps he's either already calculated the hull, or the surface isn't > > necessarily convex after all. In either case, we need more information > > about the edges connecting the vertices. The points alone are no longer > > sufficient to define the surface he wants to measure. > > > > Now, I know how to find a convex hull in 2-space, and I think I could work > > out the equivalent algorithm in 3-space, but IIRC, it's O(n^2) on the > > number of points. Once the hull is found, finding the area is simply a > > matter of adding up the triangle areas as you noted, which is linear on > > the number of triangles. > > > > -- Dave Tweed > > > > -- > > http://www.piclist.com hint: To leave the PICList > > mailto:piclist-unsubscribe-request@mitvma.mit.edu > > -- > http://www.piclist.com hint: PICList Posts must start with ONE topic: > [PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads > -- http://www.piclist.com hint: PICList Posts must start with ONE topic: [PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads