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