Calculating the area of a closed 3-D path or ring

[Math Guy]

Looking for some thoughts about how to understand this problem.

A closed loop (an irregular ring) is defined by a set of n points in
space.

Each point has an (x,y,z) coordinate. The points are not co-planar.
Typically, this ring would approximate the perimeter of a horse saddle,
or a potato chip. The number of points (n) is typically from 6 to 12
(usually 9) but will never be more than 16.

The way I see it, there are two ways to understand the concept of the
area of this ring.

a) if a membrane was stretched across the ring, what would the area of
the membrane be? Think of the membrane as a film of soap - which
because of suface tension would conform itself to the smallest possible
surface area. This would be Area A.

b) if the ring represented an aperture through which some material (gas,
fluid) must pass, or the flux of some field (electric, etc). This would
be Area B.

I theorize that because the points that define this ring are not
co-planar, that Area A would not be equal to Area B.

I am looking for a numerical-methods formula or algorythm to calculate
the "area" of such a ring, and because I believe there are two different
areas that can be imagined, there must be two different formulas or
algorythms, and thus I'm looking for both of them.

If I am wrong, and there is only one "area" that can result from such a
ring, then I am looking for that formula.

I can imagine that summing the area of individual non-over-lapping
triangles will give me "an area". Given 9 perimeter points it is
possible to arrange more than one set of non-over-lapping triangles,
with each set giving it's own total area - but which one is the
"correct" one if they give different results?

Comments?

[Ray Koopman]

A simple first approximation (and probably a lower bound to the area
you want) would be to shift the origin to the centroid and then take
the area inside irregular ring defined by the projections of the
points into the space of their first two principal axes.

[Shmuel Metz]

In <513FD11E...@guy.com>, on 03/12/2013

at 09:06 PM, Math Guy <Ma...@guy.com> said:

>Looking for some thoughts about how to understand this problem.

There is no such thing as the area of a ring.

>a) if a membrane was stretched across the ring, what would the area
>of the membrane be?

A surface with zero variation, but not necessarily with minimal area.

>b) if the ring represented an aperture through which some material
>(gas, fluid) must pass, or the flux of some field (electric, etc).
>This would be Area B.

I believe that the flux would depend on the physical setup, not just
on the ring itself.

>I can imagine that summing the area of individual non-over-lapping
>triangles will give me "an area". Given 9 perimeter points it is
>possible to arrange more than one set of non-over-lapping triangles,
>with each set giving it's own total area - but which one is the
>"correct" one if they give different results?

Why would any peicewise linear surface be "correct"? It certainly
won't be minimal.

>Comments?

You need to ask a precise question in order to get a precise answer.
Define what you mean by the surface associated with the ring and
someone may be able to point you to an algorithm for calculating the
area.

--
Shmuel (Seymour J.) Metz, SysProg and JOAT <http://patriot.net/~shmuel>

Unsolicited bulk E-mail subject to legal action. I reserve the
right to publicly post or ridicule any abusive E-mail. Reply to
domain Patriot dot net user shmuel+news to contact me. Do not
reply to spam...@library.lspace.org

[Frederick Williams]

"Shmuel (Seymour J.) Metz" wrote:
>
> In <513FD11E...@guy.com>, on 03/12/2013
> at 09:06 PM, Math Guy <Ma...@guy.com> said:

> >a) if a membrane was stretched across the ring, what would the area
> >of the membrane be?

> >b) if the ring represented an aperture through which some material
> >(gas, fluid) must pass, or the flux of some field (electric, etc).
> >This would be Area B.

> Define what you mean by the surface associated with the ring [...]

I think he has, twice! If definitions are good, two must be better.

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

[1treePetrifiedForestLane]

nine should be easy for a quadric surface; supposedly,
that is generally the minimum number of points
to define a quadric surface; corresponds
to a 14-deltahedron (convexity).

[fom]

On 3/12/2013 8:06 PM, Math Guy wrote:
>
> I can imagine that summing the area of individual non-over-lapping
> triangles will give me "an area". Given 9 perimeter points it is
> possible to arrange more than one set of non-over-lapping triangles,
> with each set giving it's own total area - but which one is the
> "correct" one if they give different results?

Right away, this seemed related to problems from the
calculus of variations. Better men than I have
already told you how difficult a good answer will
be, and, I hope that someone who has actually faced
something similar gives you an answer or at least helps
you to define your needs more carefully.

Given that, it might be sufficient to find the barycenter
or centroid or whatever one cares to call it (someone
at wikipedia redirected barycenter to center of mass),
and calculate the area of the triangles formed from
the corners of the cyclic polygonal line forming the
ring to the barycenter.

With the formula for that area, do the necessary
analysis with directional derivatives to see how
your area function changes with respect to variation
from the barycenter.

Or, perhaps, since the number of triangles is finite,
construct a weighted function based on the calculated
areas for each triangle in relation to the barycenter
(in other words, a baseline against which to define
"correctness" if that is appropriate) and then see
how the weighted function varies with respect to
variation from the barycenter.

If by some lucky chance there were a particular
line through the barycenter -- or even a manageably
finite number of lines -- that are identified by
the analysis of variation, you could examine a
parametrized function that calculates the area
of a pyramidal cone whose vertex lies on those
lines. Then you might find an extreme on one
of those lines that is not at the barycenter.

With respect to those same lines, one could
consider a different notion of "correctness".
The extrema that might be of interest
in this case would be based on a least squares
minimization. What would be minimized would be
the angular differences of the normal lines of
the triangles relative to the line that is
being used to parametrize the function. The
idea of this would be to make the surface as
"orthogonal" as possible to whatever line seemed
interesting enough to pursue further. With this
additional notion, "correctness" might lead to
a point different from the barycenter for
different reasons.

It may be that an "interesting" direction actually
lies in one of the triangles. Then you would
want to consider moving off of the barycenter
in that direction and repeating the analysis with
a new point along that line.

It may be that an "interesting" direction is
not "orthogonal" enough for the analysis above
to even make sense. With that same idea, however,
you might try to find a hyperplane for your
ring based on a least squares minimization of the
angles the segments of your polygonal line
make with hyperplanes. Take the basis of
calculating the areas of a pyramidal cone as
the line passing through the barycenter normal
to such a hyperplane if one can be found.

As I tried to imply above, I am not the one who
should be replying to you. But, you asked for
numerical methods. So, even though this is
a variational problem, answers involving the
calculus of variations will not help you directly.
There probably are instances of people who have
converted problems like this into numerical
approximation methods (but, you would need to
better explain your problem for them to recognize
that their knowledge is directly applicable).
If so, I certainly hope one can help you.

But, if that does not happen, I hope some of
the above suggestions may be of help.

[fom]

On 3/12/2013 8:06 PM, Math Guy wrote:

> Looking for some thoughts about how to understand this problem.
>
> A closed loop (an irregular ring) is defined by a set of n points in
> space.
>
> Each point has an (x,y,z) coordinate. The points are not co-planar.
> Typically, this ring would approximate the perimeter of a horse saddle,
> or a potato chip. The number of points (n) is typically from 6 to 12
> (usually 9) but will never be more than 16.

As in the case of the other reply, I am the last
person who should be answering your question.

What you are describing with this statement is typically
called a "saddle point" (someone should add an entry
at wikipedia for "potato chip point")

http://en.wikipedia.org/wiki/Saddle_point

There are specific analytic functions and specific
methods for curvilinear approximation that would
be helpful to you if you had constraints to choose
such functions and if you were fortunate enough
to find someone who knew methods that might apply.

Since neither of those conditions are satisfied by
me, let us think about the problem in some other
way.

If you look at the picture on the wikipedia page, you
will see that the saddle is enclosed in a convex
rectilinear region. So, you would want to do something
along those lines in order to frame the problem.

Next, notice that a line segment connecting the maximum
points of the concave up curve and a line segment connecting
the minimum points of the concave down curve give you a basis
for constructing a tetrahedral convex domain. You
may need to add points at the extrema once the
rectilinear region is determined in order to do this.

Suppose now that you find the centroid of the
tetrahedral domain.

If you now form triangles from the line segments
of the cyclic polygonal line forming your ring
to the centroid of the tetrahedral domain, you
will have some structure based on the saddle
point geometry you are claiming to approximate
with your statement (my other reply did not
even try to address this since my first thought
was simply any "area" for any configuration of
n points in space based on triangular surfaces --
that is why I snipped the beginning of your post).

Once again, you need to look at variations with
respect to the centroid. Your polygonal
boundary may not be as symmetrical as a "horse
saddle". If it is, you might be restricted to
vary only along the normal to the "top" and
"bottom" surfaces of the rectilinear boundary
which passes through the centroid.

If you want to vary off of such a line for
any reason, consider forming an ovoid region
inscribed in the tetrahedron, having the same
ratio of axes as the rectilinear region, and
oriented to have its axes coherently aligned
with the rectilinear region. Then your
variations will have some constraint within
the tetrahedral region that reflects the
external constraint used to orient your
tetrahedral geometry. This will prevent
you from varying too far from your intended
"shape".

Actually, once you have determined the
ovoid that could be inscribed, use a
smaller ovoid (the golden ratio is always
the aesthetic choice since there is
no notion of "correctness" available
to us) so that your variations are
sufficiently distant from the tetrahedral
boundary.

http://en.wikipedia.org/wiki/Golden_ratio


Good luck.

[Math Guy]

Math Guy wrote:

> A closed loop (an irregular ring) is defined by a set of n points
> in space.
>

> The way I see it, there are two ways to understand the concept of

> the area of this ring...

Thanks for all the responses.

The points are markers on the mitral valve annulus of research subjects.

The desired area is thus the aperture or opening of the valve.

We will probably go with calculating a centroid and then summing the
areas of the triangles formed from the centroid to the perimeter
markers.

The more "elegant" method (I would think, given the objective) would be
to project this opening to a flat plane, and then measure the area of
the projection. One way to imagine this plane is the "plane of best
fit" from the given points (a plane where the sum of the squared
differences of the distances from each point to the plane is minimized).

Once the plane is known, the points are translated to the coordinate
system of the plane, their Z coordinates are ignored or dropped, and
this becomes a 2-dimensional area calculation.

[Ray Koopman]

That's exactly what I suggested :)

You haven't said whether the ordering of the points around the loop is
given or not. Also, what do you want to do if the loop is not convex?
(Even if the loop "ought" to be convex, it's a biological system and
won't always behave as it "should", and there may also be measurement
errors.)

[Math Guy]

Ray Koopman wrote:

> > Once the plane is known, the points are translated to the
> > coordinate system of the plane, their Z coordinates are ignored
> > or dropped, and this becomes a 2-dimensional area calculation.
>
> That's exactly what I suggested :)

Hmm - I guess I didn't read that far...

> You haven't said whether the ordering of the points around the
> loop is given or not.

The user will specify the markers to be used (there are other markers on
the heart which will not be involved in this ring). A routine will
identify the order by picking one point and then determine which of the
remaining points is closest, and will piece-wise work it's way around
the ring. This should avoid any errors if the user gives the order
incorrectly.

> Also, what do you want to do if the loop is not convex?

Do you mean what if the loop looks like a potato chip with a bite taken
out of it?

I don't see how that would affect the proposed area calculation method.

[fom]

On 3/14/2013 11:36 PM, Math Guy wrote:
> Ray Koopman wrote:
>
>>> Once the plane is known, the points are translated to the
>>> coordinate system of the plane, their Z coordinates are ignored
>>> or dropped, and this becomes a 2-dimensional area calculation.
>>
>> That's exactly what I suggested :)
>
> Hmm - I guess I didn't read that far...

He is correct. He suggested simple projection
as a lower bound on any area that might be
calculated.

[Peter Spellucci]

use something like odrpack from netlib (or in this simple case, the svd )
compute the plane of least sum of orthogonal distances squared ,
project your points to this plane, compute the centroid, construct the triangles
(in the plane now) and you get a lower bound for the surface in question
with such a small number of points you might use this here:
http://numawww.mathematik.tu-darmstadt.de
in the section ''least squares'' there is the svd solution to compute the plane.
hth
peter

[Ray Koopman]

On Mar 14, 9:36 pm, Math Guy <M...@Guy.com> wrote:

> Ray Koopman wrote:
>>
>> You haven't said whether the ordering of the points around the
>> loop is given or not.
>
> The user will specify the markers to be used (there are other markers
> on the heart which will not be involved in this ring). A routine will
> identify the order by picking one point and then determine which of
> the remaining points is closest, and will piece-wise work it's way
> around the ring. This should avoid any errors if the user gives the
> order incorrectly.
>
>> Also, what do you want to do if the loop is not convex?
>
> Do you mean what if the loop looks like a potato chip with a bite taken
> out of it?
>
> I don't see how that would affect the proposed area calculation method.

It won't affect the plane of best fit, but it may make it harder to
identify the loop. I would give the 2D coordinates to a convex hull
routine. If the hull uses all the points then it's your loop. But
if some points are inside the hull then a simple nearest-neighbor
approach can sometimes connect the points in the wrong order.

[fom]

Absolutely.

When I had been trying to visualize the stated problem,
I assumed that a "ring" would be a convex star.

Good point!

[Math Guy]

fom used improper usenet message composition style by unnecessarily
full-quoting:

> When I had been trying to visualize the stated problem,
> I assumed that a "ring" would be a convex star.

I clearly stated in the first post that the ring resembled the perimeter

of a horse saddle, or a potato chip.

How does either of those resemble a star?

[fom]

The sense of a star in this case is the
idea that there is some point in the
region which can form a line segment with
any given point of the region different
from itself such that every point of that
line segment is a point of the region.

Of course, with curved differentiable
surfaces, one would have to interpret
the sense of my statement in terms of
geodesics.

As for your description, you asked for
numerical methods and suggested that
the data available would be some finite
number of points on the boundary.

Assuming a Euclidean interpretation of
coordinates, the closest approximation
to a ring you could have is a polygonal
line closing upon itself. Hence corners.

Given the barycenter and triangular
regions formed with each consecutive
pair of points on the boundary, every
point of the region different from the
barycenter forms a line segment in the
surface.

Sadly, my choice of words is often not
as precise as I would like. But, it
can usually be reasonably clarified.
I hope I have done so.

[Ray Koopman]

On Mar 16, 12:27 am, Ray Koopman <koop...@sfu.ca> wrote:
> ... I would give the 2D coordinates to a convex hull routine.

> If the hull uses all the points then it's your loop. But if
> some points are inside the hull then a simple nearest-neighbor
> approach can sometimes connect the points in the wrong order.

If there are points inside the hull then try inserting them into
the hull sequence so as to minimize the total length of the
resulting loop -- sort of a modified traveling salesman problem.
You may even find code somewhere that does it.

[Math Guy]

Math Guy wrote:

> A closed loop (an irregular ring) is defined by a set of n points
> in space.
>
>

> I am looking for a numerical-methods formula or algorythm to

> calculate the "area" of such a ring...

In case anyone's interested, here is some example data:

http://www.fileden.com/files/2008/7/19/2010361/data.xls

http://www.fileden.com/files/2008/7/19/2010361/data.txt

They contain the same data - the txt file is just a tab-delimited ascii
text dump of the data in the xls file.

First column is time, the next 27 columns are the {x,y,z} sets for 9
marker coordinates.

About 260 rows representing about 1.7 seconds worth of data.

The markers are numbered in correct path-order from 1 to 9 (and back to
1).

[Ray Koopman]

This set of data seems quite well conditioned. All the projections
into the best-fit planes give convex polygons, with their vertices
in the order given. The areas of the polygons range from 699 to 933.
A plot of the areas as a function of time makes it obvious that the
264 points cover 3 beats of the heart. This can also be seen if you
view the polygons successively, as a movie.

[Math Guy]

Ray Koopman wrote:

> This set of data seems quite well conditioned. All the projections
> into the best-fit planes give convex polygons, with their vertices
> in the order given. The areas of the polygons range from 699 to 933.
> A plot of the areas as a function of time makes it obvious that the
> 264 points cover 3 beats of the heart. This can also be seen if you
> view the polygons successively, as a movie.

How do the polygon area plots compare with the more simple area method
(sum of triangles using computed centroid) ?

[Ray Koopman]

As predicted, the sum of the triangle areas is always greater than
the polygon area, but plots of the areas as functions of time are very
similar. Plotting one area against the other shows a hysteresis-like
pattern. Plotting the difference between the two areas against the
smallest singular value of the centered 3D coordinates shows a similar
pattern.

[Gib Bogle]

I just learned that determining the minimum-area surface is called
Plateau's problem, after the mathematician Joseph Plateau.
http://en.wikipedia.org/wiki/Plateau%27s_problem