http://www.mathworks.com/matlabcentral/newsreader/view_thread/293890
MATLAB Central Newsreader  Determine which points of a grid belong to a certain volume
Feed for thread: Determine which points of a grid belong to a certain volume
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Thu, 14 Oct 2010 14:29:04 +0000
Determine which points of a grid belong to a certain volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/293890#787783
Andreas Frölich
Hi everyone,<br>
<br>
I am looking for a good way to solve the following task:<br>
<br>
Given a 3d grid g=zeros(Nx,Ny,Nz)<br>
corresponding to a discretization of a block in physical space with the dimensions ax,ay and az I would like to determine, which points of g belong to the volume swept out by moving the center of an ellipsoid along a path inside the volume that g is a discretization of. The path is specified by a starting point [sx sy sz] and an endpoint [ex ey ez]. The ellipsoid has its long axis rz along the zdirection and its short axis are of equal length rx and lie in the xyplane.<br>
<br>
I hope this is a clearly put question, if not I will be happy to provide additional information.<br>
<br>
Thanks in advance for your help,<br>
<br>
Andreas

Thu, 14 Oct 2010 14:53:04 +0000
Re: Determine which points of a grid belong to a certain volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/293890#787796
Sean
"Andreas Frölich" <ThisPartBlocksSpam_andreas.froelich@kit.edu> wrote in message <i9743g$jip$1@fred.mathworks.com>...<br>
> Hi everyone,<br>
> <br>
> I am looking for a good way to solve the following task:<br>
> <br>
> Given a 3d grid g=zeros(Nx,Ny,Nz)<br>
> corresponding to a discretization of a block in physical space with the dimensions ax,ay and az I would like to determine, which points of g belong to the volume swept out by moving the center of an ellipsoid along a path inside the volume that g is a discretization of. The path is specified by a starting point [sx sy sz] and an endpoint [ex ey ez]. The ellipsoid has its long axis rz along the zdirection and its short axis are of equal length rx and lie in the xyplane.<br>
> <br>
> I hope this is a clearly put question, if not I will be happy to provide additional information.<br>
> <br>
> Thanks in advance for your help,<br>
> <br>
> Andreas<br>
<br>
Well you know the formula for a 3D ellipsoid so this is a basic logical scheme:<br>
<br>
[xx yy zz] = meshgrid(1:Nx,1:Ny,1:Nz); <br>
<br>
These are three matrices which contain the coordinates to every point in your block.<br>
Now write the formula for the ellipsoid in terms of the center and these three matrices with some maximum radii. <br>
<br>
See this thread for the equivalent with just a 2D circle:<br>
<a href="http://www.mathworks.com/matlabcentral/newsreader/view_thread/291115#777679">http://www.mathworks.com/matlabcentral/newsreader/view_thread/291115#777679</a>

Thu, 14 Oct 2010 16:36:23 +0000
Re: Determine which points of a grid belong to a certain volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/293890#787835
ImageAnalyst
Andreas:<br>
That is done by a morphological dilation.<br>
<a href="http://en.wikipedia.org/wiki/Dilation_%28morphology%29">http://en.wikipedia.org/wiki/Dilation_%28morphology%29</a><br>
You just need to set up the kernel that defines the ellipsoid, and<br>
draw your path into your volume (set those pixels to 1), and then call<br>
imdilate().<br>
ImageAnalyst

Thu, 14 Oct 2010 19:10:05 +0000
Re: Determine which points of a grid belong to a certain volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/293890#787875
Roger Stafford
"Andreas Frölich" <ThisPartBlocksSpam_andreas.froelich@kit.edu> wrote in message <i9743g$jip$1@fred.mathworks.com>...<br>
> Hi everyone,<br>
> <br>
> I am looking for a good way to solve the following task:<br>
> <br>
> Given a 3d grid g=zeros(Nx,Ny,Nz)<br>
> corresponding to a discretization of a block in physical space with the dimensions ax,ay and az I would like to determine, which points of g belong to the volume swept out by moving the center of an ellipsoid along a path inside the volume that g is a discretization of. The path is specified by a starting point [sx sy sz] and an endpoint [ex ey ez]. The ellipsoid has its long axis rz along the zdirection and its short axis are of equal length rx and lie in the xyplane.<br>
> <br>
> I hope this is a clearly put question, if not I will be happy to provide additional information.<br>
> <br>
> Thanks in advance for your help,<br>
> <br>
> Andreas<br>
           <br>
I will approach this problem from a mathematical point of view. If you had a sphere rather than an ellipsoid, the volume in question would consist of the inside of a circular cylinder with a hemispherical cap at either end. Testing that an arbitrary point (x,y,z) lies within that volume would be accomplished by determining if the point was a) inside either end sphere or b) simultaneously within the (infinitelylong) cylinder and between the two planes where the cylinder contacts each sphere.<br>
<br>
With an ellipsoid the method is similar though more complicated. The points inside the "start" and "end" ellipsoids satisfy<br>
<br>
(xsx)^2/a^2 + (ysy)^2/b^2 + (zsz)^2/c^2 <= 1 (1)<br>
<br>
(xex)^2/a^2 + (yey)^2/b^2 + (zez)^2/c^2 <= 1 (2)<br>
<br>
respectively. (I generalized to a, b, and c being all different.)<br>
<br>
As the ellipsoid is moved from "start" to "end", an ellipsoidal cylinder is swept out by the ellipsoid. The points on either ellipsoid that make contact with this cylinder must have their surface normal orthogonal to a vector in the direction of motion from (sx,sy,sz) to (ex,ey,ez). For the start ellipsoid the surface normal points in the direction of the three partial derivatives 2*(xsx)/a^2, 2*(ysy)/b^2, 2*(zsz)/c^2, so for such points we must have<br>
<br>
(xsx)/a^2*(exsx) + (ysy)/b^2*(eysy) + (zsz)/c^2*(ezsz) = 0<br>
<br>
which defines a plane, just as with the above spheres. There is a similar parallel plane for the end ellipsoid, and the resulting inequalities for a point to lie between the planes would be<br>
<br>
(xsx)*(exsx)/a^2 + (ysy)*(eysy)/b^2 + (zsz)*(ezsz)/c^2 >= 0 (3)<br>
<br>
(xex)*(exsx)/a^2 + (yey)*(eysy)/b^2 + (zez)*(ezsz)/c^2 <= 0 (4)<br>
<br>
If we define dx = exsx, dy = eysy, and dz = ezsz, and vary the parameter t as we move the ellipsoid, it satisfies<br>
<br>
(xsxdx*t)^2/a^2 + (ysydy*t)^2/b^2 + (zszdz*t)^2/c^2 = 1<br>
<br>
This equation can (after a little sweat or expeditious use of matlab's symbolic toolbox) be put in the form<br>
<br>
A*t^2 + B*t + C = 0 (5)<br>
<br>
where for example A = dx^2/a^2+dy^2/b^2+dz^2/c^2. (I'll let you work out B and C.) If a point (x,y,z) is to lie inside the abovementioned cylinder, then there must exist a value for t which satisfies the quadratic (5), and this is possible if and only if its discriminant is nonnegative:<br>
<br>
B^24*A*C >= 0 (6)<br>
<br>
Therefore the equation for the inside of the cylinder is (6) with A, B, and C determined as described above.<br>
<br>
Thus we now have the criterion for an arbitrary point (x,y,z) to lie within the volume in question. It must either satisfy inequality (1), or satisfy inquality (2), or else it must satisfy inequalities (3), (4), and (6) simultaneously.<br>
<br>
I realize this still requires some work on your part working out the details of inequality (6), but what we have here is a balance between the effort of doing this and the inefficiency of a more crude kind of matlab code that would place the ellipsoid in tiny successive steps along the path, testing all points in the grid each time. This latter could constitute a rather wasteful order n^3 type algorithm.<br>
<br>
Roger Stafford

Fri, 15 Oct 2010 00:41:03 +0000
Re: Determine which points of a grid belong to a certain volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/293890#787910
Roger Stafford
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i97kic$8p4$1@fred.mathworks.com>...<br>
> I will approach this problem from a mathematical point of view. If you had a sphere rather than an ellipsoid, the volume in question would consist of the inside of a circular cylinder with a hemispherical cap at either end. Testing that an arbitrary point (x,y,z) lies within that volume would be accomplished by determining if the point was a) inside either end sphere or b) simultaneously within the (infinitelylong) cylinder and between the two planes where the cylinder contacts each sphere.<br>
> <br>
> With an ellipsoid the method is similar though more complicated. The points inside the "start" and "end" ellipsoids satisfy<br>
> ........<br>
          <br>
It has occurred to me that you could simplify the analysis of your problem by first transforming all the z coordinates of your mesh points by<br>
<br>
Z = a/c*z<br>
<br>
Remembering that your a and b are equal, this transforms your ellipsoids into spheres and you could then test for the transformed points lying in a circular cylinder with spherical hemispheres at each end, an easier analysis to perform.<br>
<br>
Roger Stafford