PDA

View Full Version : 3d-Ellipsoid



hlewin
07-22-2013, 05:41 AM
I have some questions more of curiosity.
I wouldn't seriously mind if no one could answer them:

1. Given a set of points - is there a simple way to construct/compute the ellipsoid with the lowest volume given by
X2/W2 + Y2/H2 + Z2/D2 - 1 = 0
that encompasses all points? How about the ellipsoids that have at least one of it's axis-lengths minimized? Does one imply the other?

2. How many distinct points (X,Y,Z) on the surface of such a 3d-ellipsoid are needed to reduce the number of possible solutions to the ellipsoid-equation to one assuming that the points are chosen at random?

I did some googling but didn't find the right things and as I don't think those questions are too easy to answer I decided to simply draw the ellipsoid by eye. Nontheless I would like to hear oppinions. Does someone know a good book dealing with geometric problems of this kind? I tried to construct an ellipsoid through three points by simply substituting in the equation but this didn't get really far.

GClements
07-23-2013, 11:29 AM
1. Given a set of points - is there a simple way to construct/compute the ellipsoid with the lowest volume given by
X2/W2 + Y2/H2 + Z2/D2 - 1 = 0
that encompasses all points? How about the ellipsoids that have at least one of it's axis-lengths minimized? Does one imply the other?
Here's one way to look at this.

First, make the substitutions:
P = 1/W2
Q = 1/H2
R = 1/D2

Thus, a point <x,y,z> is inside the ellipsoid if
X2P + Y2Q + Z2R <= 1

This forms a linear half-space in <P,Q,R> space.

The set of ellipsoids which contain all points is thus a convex polyhedron in <P,Q,R> space defined as the intersection of a set of half-spaces, each defined by one of the points.

The vertices, edges and faces of this polyhedron can be found using the simplex method (http://en.wikipedia.org/wiki/Simplex_method). If you wanted the ellipsoid which minimised a linear function in P, Q, and R, that could also be found by the simplex method.

However, in this case, you're trying to minimise W*H*D = 1/sqrt(P*Q*R), so you're trying to maximise P*Q*R.

The optimum value will lie on the surface of the polyhedron, but as the function isn't linear, it won't necessarily be a vertex. Having enumerated the vertices, edges and faces, you need to find the value of P*Q*R for each vertex, and its maximum value for each edge and face.



2. How many distinct points (X,Y,Z) on the surface of such a 3d-ellipsoid are needed to reduce the number of possible solutions to the ellipsoid-equation to one assuming that the points are chosen at random?

I'm not sure I understand the question.

In the above approach, each vertex of the polyhedron correspond to an ellipsoid which touches three points.. Similarly, each edge corresponds to a one-dimensional family of ellipsoids which touch the same two points (and possibly others), while each face corresponds to a two-dimensional family of ellipsoids which touch a specific point.

Note that in any of the case of an ellipsoid which touches three points, it may coincidentally touch additional points. In this situation, the simplex method will produce multiple vertices which are coincident but structurally distinct, resulting in some degenerate (zero length or area) edges and faces.

hlewin
07-23-2013, 12:47 PM
The vertices, edges and faces of this polyhedron can be found using the simplex method.
Thank you! I didn't think about it as at the time I asked myself the question I was already finished with the problem despite having heard of the method. The GNU-Scientific Library seems to have an implementation of a simplex-minimizer.


Note that in any of the case of an ellipsoid which touches three Points
I'm afraid I don't understand. In my understanding each point on the surface of the polyhedron is a valid solution but I do not see how this would mean that it necessarily touches more than one point of the set. Anyways: the question was meant in a much simpler way: How many random surface-points does one need to uniquely identify an ellipsoid? My Initial guess was three, but that only seems to work for special points.
EDIT: The tought was to simply take the bounding-box around the point set and make an ellipsoid from it as I do not really need a perfectly minimized ellipsoid, but this produces a set of them.

GClements
07-23-2013, 01:44 PM
Note that in any of the case of an ellipsoid which touches three points

I'm afraid I don't understand. In my understanding each point on the surface of the polyhedron is a valid solution but I do not see how this would mean that it necessarily touches more than one point of the set.
Sorry, the "any" shouldn't have been there. It should have said:

Note that in of the case of an ellipsoid which touches three points
Such cases correspond to a vertex of the polyhedron. Edges correspond to ellipsoids which touch two points, faces to ellipsoids which touch one point, and the interior to ellipsoids which contain all points but touch none.



Anyways: the question was meant in a much simpler way: How many random surface-points does one need to uniquely identify an ellipsoid? My Initial guess was three, but that only seems to work for special points.
In general, three. It's just a case of three equations in three unknowns.

But the actual requirement is for three linearly-independent equations. There are cases where multiple points specify the same equation, making some of them redundant.

As (-X)2=X2 etc, the ellipsoid is symmetric about the X, Y and Z planes. So if the point (x,y,z) lies on the surface of the ellipse, then so do the other seven points obtained by reflecting the original point in the X, Y and Z planes, i.e. (-x,y,z), (-x,-y,-z) and so on.

More generally, if the square of one point (X2,Y2,Z2) is a linear combination of the squares of the other two, then you don't have three linearly-independent equations and the ellipsoid isn't uniquely defined. The symmetry issue is just a specific case of this.

Another specific case is when one point differs from another by a scale factor (i.e. the point lies on a line segment between another point and the origin). As a consequence, there is no upper bound on the number of points required. If you had an infinite number of points forming a line segment with one end at the origin, it would be as if you only had one point (the line segment's other endpoint).

hlewin
07-23-2013, 02:18 PM
Such cases correspond to a vertex of the polyhedron. Edges correspond to ellipsoids which touch two points, faces to ellipsoids which touch one point, and the interior to ellipsoids which contain all points but touch none.
Is this an observation or derived from the algorithm? I read the sentence, that the optimal solution corresponds to a vertex of the polyhedron, but imagining an ellipse and a point that is outside of it


/\.
/ \
\ /
\/


the point can be made to lie on the surface of the ellipse by increasing it's width OR height. So I do not see how an optimal solution would require to hit more than one point of the set (and even that is something I can just derive from imagination without having proven it - sorry if I don't get the point).

GClements
07-23-2013, 05:48 PM
Is this an observation or derived from the algorithm?
It's an observation on the nature of <P,Q,R> space and the polyhedron.


A point (in <P,Q,R> space) corresponds to an ellipsoid (in <x,y,z> space).
A plane corresponds to the set of ellipsoids which touch a specific point.
A (linear) half-space corresponds to the set of ellipsoids which contain (incl. touch) a specific point.
The filled polyhedron corresponds to the set of ellipsoids which contain all points.
The surface of the polyhedron corresponds to the set of ellipsoids which contain all points and touch at least one point.
The interior of the polyhedron corresponds to the set of ellipsoids which contain all points and touch none of them.
Each face corresponds to the set of ellipsoids which touch a specific point and contain all points.
Each edge corresponds to the set of ellipsoids which touch two specific points and contain all points.
Each vertex corresponds to the set of ellipsoids which touch three specific points and contain all points.



I read the sentence, that the optimal solution corresponds to a vertex of the polyhedron,
An optimal solution corresponds to a point on the surface of the polyhedron, not necessarily a vertex.

Because the function being maximised is non-linear (P*Q*R), it's possible for the value at a point within a face to be greater than that at any of its vertices. This is why the simplex method cannot be used to find the optimal solution directly. It can only be used to enumerate the space of candidate solutions; non-linear methods must be used to find the global maximum.


the point can be made to lie on the surface of the ellipse by increasing it's width OR height. So I do not see how an optimal solution would require to hit more than one point of the set (and even that is something I can just derive from imagination without having proven it - sorry if I don't get the point).
An optimal solution doesn't require it to hit more than one point.

hlewin
07-23-2013, 08:06 PM
I'm sorry I read you imprecisely. Giving it a longer thought your 2nd observation seems right.
Nonetheless all this seems way too complicated to implement for the initial problem I was trying to solve - namely to construct bounding-ellipsoids for some 3-d models for which spheres are inadequate because they are very different in their dimensions.
I thought about starting with a (0,0,0) one, throwing in points and quick-guessing which Dimension to increase to make it lie inside. But that lead to the problem scatched above. (Although I didn't give it an empirical try.)

Carmine
07-24-2013, 11:34 AM
Nonetheless all this seems way too complicated to implement for the initial problem I was trying to solve - namely to construct bounding-ellipsoids for some 3-d models for which spheres are inadequate because they are very different in their dimensions. Why stop at ellipsoids? Why not use convex hulls to 'bound' your models? They are convex polyhedra that bound point sets (i.e. model vertices) tightly. You can probably download free software to compute 3D convex hulls. The nice thing about hulls is that it's pretty easy to test a random point to see if it's inside or outside of the hull.

GClements
07-24-2013, 02:09 PM
Why stop at ellipsoids? Why not use convex hulls to 'bound' your models? They are convex polyhedra that bound point sets (i.e. model vertices) tightly. You can probably download free software to compute 3D convex hulls. The nice thing about hulls is that it's pretty easy to test a random point to see if it's inside or outside of the hull.
It's simple, but it's not particularly efficient. You need to perform one plane test per face, and you need at least 4 faces for a closed polyhedron, typically more if you want a tight bound. Testing for a point inside an ellipsoid is roughly twice as expensive as a single plane test.

Testing for intersections between bounding volumes is even more favourable to ellipsoids.

Carmine
07-24-2013, 02:45 PM
It's simple, but it's not particularly efficient. You need to perform one plane test per face, and you need at least 4 faces for a closed polyhedron, Yes - one plane test per face. You need at least 4 non-coplanar vertices to form the simplest polyhedron, which is a tetrahedron.


Testing for intersections between bounding volumes is even more favourable to ellipsoids. Probably true. Didn't know you needed intersections.

hlewin
07-25-2013, 01:19 AM
I'm not that sure what I'll need in the further course I must say. Ellipsoids have the right visual shape for the the things I want to do right now although I might add some additional eccentricity (maybe I'm not using the terminus correctly here) in that I'll tune the equation to move the XY-Maxima along the Z-axis. Haven't really thought about that.
Additionally, mathematical-defined shapes like ellipsoids are suitable for raytracing in shaders.