Jim,

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.

Further, I assume that each point in the array stores its 3 dimensional
coordinates in a form retrievable as (Ax,Ay,Az), for the point A for
example.  That is, in the way we would ordinarily express a point in
Cartesian coordinates in three space.

Divide your area up into triangles ABC, BCF, BDF, DFG, DEG, EGH, CFI,
...  You get the idea.

Calculate the area of each triangle.  The area of each triangle in 3
space is half the length of the result vector formed by taking the cross
product of the vectors formed by any two sides of each triangle.

Following, is the rough stuff for triangle ABC (you can substitute other
triangles as desired):

A = (Ax, Ay, Az)     B = (Bx, By, Bz)    C = (Cx, Cy, Cz)

Area of ABC =

(((By*Cz - By*Az - Ay*Cz - Bz*Cy + Bz*Ay + Az*Cy)^2 +
   (Bz*Cx - Bz*Ax - Az*Cx - Bx*Cz + Bx*Az + Ax*Cz)^2 +
   (Bx*Cy - Bx*Ay - Ax*Cy - By*Cx + By*Ax + Ay*Cx)^2)^(1/2))/2

Hope I didn't make a mistake there.  You can check it against a triangle
whose area you know (one in two space).

Then, just sum up the areas of all of the triangles.  Of course, the
algorithm will be both faster and less accurate with less data points.
Fast is in the eye of the beholder.

Good luck,

Dave


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 :^)
> Thanks for any suggestions or pointers!
> Jim

--
http://www.piclist.com hint: To leave the PICList
mailto:piclist-unsubscribe-request@mitvma.mit.edu