Dave Tweed wrote: > >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. Just to clarify... I am *not* trying to "find" the convex hull, or determine whether or not the points I have stored in a 3D array are (or are not) actually a convex hull. I *KNOW* 'a priori' that the points in hand do form a convex hull, and I *KNOW* how to calculate the "actual" area (which is, as noted in an earlier post, the sum of the 'triangles' formed by adjacent sets of points, A/B/C, etc.) - Why do you say ' the points alone are no longer sufficient to define the surface..'? - What do you mean by '... a convex hull in 2-space...'?? It's not a 2-d object at all, it's a "solid" (i.e. 3-d). - Remember, as I mentioned in my OP, I am *not* looking for an algorithm to simply find the area: I am looking for an "approximation" (i.e. "shortcut" with estimable error factor) that takes significantly less compute-time than the "real" algorithm. Thanks! JIm ----- 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