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
Can't be helped who it happens to be by :-)
He's got a lot of good stuff there.
Point Google at "cubic spline" and you can spend many a happy hour with the
results.
RM
___________________________________________________________
If we have already accidentally created an unexpectedly lethal virus by
single
gene transfer, why should we believe that it might not happen again, once
or on numerous occasions in future, but in less controlled circumstances?
What's fast? Do you have equations which describe the surface? Do you
need a one time solution or is this going to be done repeatedly?
Best regards,
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
> > I'm looking for an APPROXIMATION algorithm to compute the surface area
of {Quote hidden}
> a convex hull shape.
> Any math wizards here?
> >
>
>
> Not me. But cubic splines are liable to be your friend.
> See http://www.tinaja.com/cubic01.asp for starters.
>
> Can't be helped who it happens to be by :-)
> He's got a lot of good stuff there.
>
> Point Google at "cubic spline" and you can spend many a happy hour with
> results.
>
>
> RM
>
> ___________________________________________________________
> If we have already accidentally created an unexpectedly lethal virus by
> single
> gene transfer, why should we believe that it might not happen again, once
> or on numerous occasions in future, but in less controlled circumstances?
>
> --
> http://www.piclist.com#nomail Going offline? Don't AutoReply us!
> email listservspam_OUTmitvma.mit.edu with SET PICList DIGEST in the body
David Minkler wrote:
> What's fast? Do you have equations which describe the surface? Do you
> need a one time solution or is this going to be done repeatedly?
Dave, good question: I should have explained that a bit, actually. I
*think* that the true value computation can be O(n) (i.e. linear) where 'n'
is the number of loci describing the hull. I'm not completely sure about
that, but that's what I'm assuming is the case. Of course I'd like the
approximation to require 0 time :^), but realistically if I found one that
was 20% the cost of the true value comp, I'd be very happy.
I don't have equations, just data points in 3D space; I can vary the
"resolution" of the hull description quite easily - i.e., just generate
fewer data points, which will obviously save time for any algorithm, but
introduce error at the same time.
This isn't a 1-time thing, it's part of a larger algorithm that will need
to invoke the approximation at a pretty high frequency (no, not in real
time, thank goodness!)
Jim
> OP:
> 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#nomail Going offline? Don't AutoReply us!
> email KILLspamlistservKILLspammitvma.mit.edu with SET PICList DIGEST in the body
John Ferrell
6241 Phillippi Rd
Julian NC 27283
Phone: (336)685-9606 spamBeGonejohnferrellspamBeGoneearthlink.net
Dixie Competition Products
NSRCA 479 AMA 4190 W8CCW
"My Competition is Not My Enemy"
John Ferrell wrote:
> How do you add/remove data points?
If you mean, at the code-implementation level, it's simply a 3D Array
representation, "Data[x,y,z]", and a point is added by storing a value at a
particular element, e.g. Data[122,345,55] = 1. Remove by setting the
element value = 0.
Jim
>From: Jim Tellier <TakeThisOuTjimtellierEraseMEspam_OUTCOX.NET>
>Reply-To: pic microcontroller discussion list <RemoveMEPICLISTTakeThisOuTMITVMA.MIT.EDU>
>To: PICLISTEraseME.....MITVMA.MIT.EDU
>Subject: [OT:] Looking for algorithm...
>Date: Thu, 6 Nov 2003 15:46:19 -0800
>
>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#nomail Going offline? Don't AutoReply us!
>email EraseMElistservmitvma.mit.edu with SET PICList DIGEST in the body
If the element spacing is generated in a uniform manner, I believe a simple
flood fill graphics algorithim will provide an opportunity to glean the
information you want.
The best way would probably be to generate an array of points where one of
the variables is constant and step the constant to generate planes through
the figure. This is more commonly done to calculate volume by summing the
areas but it appears to me that if you sum the differentials of the
generated planes the value will represent the surface.
Accuracy of the computations would be limited only by the number of points
and whatever time constraints you place on the calculations.
Although the actual program would not be very complex the array handling may
require the use of files. Then on the other hand, with the availability
virtual storage and dynamic arrays (DELPHI language) that may not be much of
a problem.
The whole thing hinges around just how bad you want a solution!
John Ferrell
6241 Phillippi Rd
Julian NC 27283
Phone: (336)685-9606 RemoveMEjohnferrellspam_OUTKILLspamearthlink.net
Dixie Competition Products
NSRCA 479 AMA 4190 W8CCW
"My Competition is Not My Enemy"
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)
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
Nice!
John Ferrell
6241 Phillippi Rd
Julian NC 27283
Phone: (336)685-9606 EraseMEjohnferrellspamspamBeGoneearthlink.net
Dixie Competition Products
NSRCA 479 AMA 4190 W8CCW
"My Competition is Not My Enemy"
David, John & company....
I haven't had a chance to get into your replies over the past day or so,
so forgive me.. I'll get my head back around this in a couple of days.. but
it looks like there are a couple of notions here that suggest a possible
solution... I need to get into my "quiet room" for a while to think about
the details.... but thanks for the ideas!
Jim
{Original Message removed}
> > 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.
>
>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
> Dave Tweed wrote:
> > 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..'?
Because you need to know which sets of three points at a time form each
facet of the hull. This is sometimes called "adjacency". If all you have
is a list of all the points, you don't have this information.
> - 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).
I said "I know how to find a convex hull in 2-space" and that I could
probably extrapolate this to 3-space. Even if you know a priori that
your list of points is indeed a hull, you still need to go through the
algorithm to match them up to form the facets.
> - 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.
In that case, you need to give us some hints about the general character
of the shapes you're encountering so that we can make some guesses about
what kinds of approximations would be suitable.
For example, if your hulls are generally ellipsoidal, it wouldn't be hard
to extract some simple parameters about the best orientation of the axes
and the dimensions of the "bounding ellipsoid", and then calculate the
area of that. If they're generally spherical, you just need to calculate
the diameter, which is simply the maximum distance between any two points.
The latter calculation is O(n^2), but is readily parallelized.
-- Dave Tweed
-- http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads
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 KILLspamjohnferrellspamBeGoneearthlink.net
Dixie Competition Products
NSRCA 479 AMA 4190 W8CCW
"My Competition is Not My Enemy"
I asked:
> > - Why do you say ' the points alone are no longer sufficient to define
> > the surface..'?
>
and Dave Tweed wrote:
> Because you need to know which sets of three points at a time form each
> facet of the hull. This is sometimes called "adjacency". If all you have
> is a list of all the points, you don't have this information.
>
Ah! Yes, I see. Given that I have the actual "surface definition" of the
solid contained in a 3-dimensional array, I should be able to "find" the
adjacent points. As I understand it, given a particular starting point "A",
I'll have to search in 3-D space for "B" and "C", calculate the area of the
resulting triangle, sum it to the total, and iterate (in some deterministic
manner to guarantee finding all triangles).
( This may be an over-simplification of Dave Minkler's description, but
that's about what I understood him to be describing)
--------
and
> In that case, you need to give us some hints about the general character
> of the shapes you're encountering so that we can make some guesses about
> what kinds of approximations would be suitable.
>
Good point; I can see how that would be helpful.
> For example, if your hulls are generally ellipsoidal, it wouldn't be hard
> to extract some simple parameters about the best orientation of the axes
> and the dimensions of the "bounding ellipsoid", and then calculate the
> area of that. If they're generally spherical, you just need to calculate
> the diameter, which is simply the maximum distance between any two points.
> The latter calculation is O(n^2), but is readily parallelized.
>
Well, problem is... I don't know what the shape really *is*. The points
that define its surface are simply the output of another algorithm. The
only thing I can know a priori is the maximum dimensions of the hull.
Trying to fit the resulting 3D array data to possible known shapes sounds
like it could be at least as time-consuming as just running the complete
hull area calculation, so I don't think that's an option.
I'm beginning to think that the best way to approach "approximating" a
result for area is to just limit the number of points. I can do that by
modulo constraint on the adjacency search without having to physically
subset the data. I'm going to play around with it a bit.
Thanks for all the responses so far! You've got me thinking in a little
different direction!
Jim
>
> --
> 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
If you have a 3d-array of evenly spaced points that are "1" if they
interesect the surface
of your solid, can't you get a rough approximation of area just by
counting the points and
multiplying by a proportionality constant that is somewhat dependent on
the general shape of the objects you're dealing with? It's not clear
that tromping all the way through a 3d
array is faster than other algorithms that use a list of xyz coords of
just the surface-intersecting points, but I don't see how you can avoid
it if that's the data structure that you have...
BillW
-- http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads
Bill,
Hmm... that's an interesting thought! There's clearly a relationship
there, so maybe I could empirically develop some constants for hull objects
with known area, then fit those into a simple method. Hmm. I'm not
completely sure if all of the points I see will be evenly spaced, but I'm
reasonably sure that the density of point data on one part of the surface
won't vary much from that on other parts. Just might be the kind of
"guesstimate" I'm looking for. If I define the array to be implemented as
1-bit per point I can make the counting *really* fast, too.
Thanks for the idea!
Jim
{Original Message removed}
mitvma.mit.edu with SET PICList DIGEST in the body
