http://www.mathworks.com/matlabcentral/newsreader/view_thread/288533
MATLAB Central Newsreader  Looking for an efficient way to find whether a path intersects with a volume
Feed for thread: Looking for an efficient way to find whether a path intersects with a 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

Wed, 04 Aug 2010 17:40:22 +0000
Looking for an efficient way to find whether a path intersects with a volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288533#768499
Bryan Benson
Hi,<br>
<br>
I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.<br>
<br>
The goal: I want to know whether a path, given by a series of coordinates, intersects with a volume, also given by a series of coordinates, where each coordinate represents an volume (let's say 30,50,20 means a volume from 2931,4951,1921).<br>
<br>
Here's a really simplified setup:<br>
path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];<br>
volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];<br>
The answer should be TRUE, because the last coordinate (3.4,3.9,2.2) is within the region described by the point (4,3,3).<br>
<br>
The problem: I have to sample a space that's approximately 100x100x100, each path has about 100 coordinates, each volume is given by about 200 coordinates, and the path coordinates are not integers, so I can't just use ismember. I was thinking maybe just to make two test matrices, one for the lower bound (in our example, 29, 49, 19), and one for the upper bound (31,51,21) of each point, and then just check whether each point is greater than the lower bound & less than the upper bound for each point in both matrices, (the path is sampled often enough that I may get away with not having to look at the line in between points as well) but I'm pretty sure I'd grow old waiting for this to run (it has to run this test on ~2000 different paths).<br>
<br>
If I haven't provided enough information, please don't hesitate to ask for more.<br>
<br>
Thanks again!

Wed, 04 Aug 2010 18:11:04 +0000
Re: Looking for an efficient way to find whether a path intersects with a volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288533#768509
us
"Bryan Benson" <not@an.address> wrote in message <i3c8m6$256$1@fred.mathworks.com>...<br>
> Hi,<br>
> <br>
> I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.<br>
> <br>
> The goal: I want to know whether a path, given by a series of coordinates, intersects with a volume, also given by a series of coordinates, where each coordinate represents an volume (let's say 30,50,20 means a volume from 2931,4951,1921).<br>
> <br>
> Here's a really simplified setup:<br>
> path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];<br>
> volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];<br>
> The answer should be TRUE, because the last coordinate (3.4,3.9,2.2) is within the region described by the point (4,3,3).<br>
> <br>
> The problem: I have to sample a space that's approximately 100x100x100, each path has about 100 coordinates, each volume is given by about 200 coordinates, and the path coordinates are not integers, so I can't just use ismember. I was thinking maybe just to make two test matrices, one for the lower bound (in our example, 29, 49, 19), and one for the upper bound (31,51,21) of each point, and then just check whether each point is greater than the lower bound & less than the upper bound for each point in both matrices, (the path is sampled often enough that I may get away with not having to look at the line in between points as well) but I'm pretty sure I'd grow old waiting for this to run (it has to run this test on ~2000 different paths).<br>
> <br>
> If I haven't provided enough information, please don't hesitate to ask for more.<br>
> <br>
> Thanks again!<br>
<br>
one of the many solutions<br>
<br>
p=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];<br>
v=[4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];<br>
fh=@(z) all(bsxfun(@(x,y) x1<=y&y<=x+1,v,z),2);<br>
r=cellfun(@(x) fh(x),num2cell(p,2),'uni',false);<br>
r=cat(2,r{:});<br>
disp(r);<br>
%{<br>
0 0 0<br>
0 0 0<br>
0 0 1 % < P(3) in V(3,:)<br>
0 0 0<br>
0 0 0<br>
%}<br>
<br>
us

Wed, 04 Aug 2010 18:43:26 +0000
Re: Looking for an efficient way to find whether a path intersects with a volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288533#768527
Roger Stafford
"Bryan Benson" <not@an.address> wrote in message <i3c8m6$256$1@fred.mathworks.com>...<br>
> Hi,<br>
> <br>
> I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.<br>
> <br>
> The goal: I want to know whether a path, given by a series of coordinates, intersects with a volume, also given by a series of coordinates, where each coordinate represents an volume (let's say 30,50,20 means a volume from 2931,4951,1921).<br>
> <br>
> Here's a really simplified setup:<br>
> path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];<br>
> volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];<br>
> The answer should be TRUE, because the last coordinate (3.4,3.9,2.2) is within the region described by the point (4,3,3).<br>
> <br>
> The problem: I have to sample a space that's approximately 100x100x100, each path has about 100 coordinates, each volume is given by about 200 coordinates, and the path coordinates are not integers, so I can't just use ismember. I was thinking maybe just to make two test matrices, one for the lower bound (in our example, 29, 49, 19), and one for the upper bound (31,51,21) of each point, and then just check whether each point is greater than the lower bound & less than the upper bound for each point in both matrices, (the path is sampled often enough that I may get away with not having to look at the line in between points as well) but I'm pretty sure I'd grow old waiting for this to run (it has to run this test on ~2000 different paths).<br>
> <br>
> If I haven't provided enough information, please don't hesitate to ask for more.<br>
> <br>
> Thanks again!<br>
           <br>
Let us assume that it is sufficient to test whether the discrete points in the path lie in the volume. For each point in the path you can do a 'floor' on each coordinate to bring them down to integer values. Out of this set of three integers you can then construct seven more sets by adding one to a) one of them, b) to two of them, or c) to all three. For example if you start with the point (1.8,3.1,2.6) above, you first floor them to get (1,3,2). Then from this you also create (2,3,2), (1,4,2), (1,3,3), (2,4,2), (2,3,3), (1,4,3), and (2,4,3). This would give you 800 sets of integer coordinates in place of the 100 in the path. Now you can use these with the 'intersect' function with the 'rows' option for threecolumn matrices. The question is, is the intersection between these and the set of cube centers empty or not. I don't think you will grow old waiting for this answer. The <br>
'intersect' function makes use of sorting so as to greatly reduce computation time for large sets like this. <br>
<br>
Of course it is quite possible for a line segment to intersect one of these cubes without either endpoint being in that cube, so the above procedure is not perfect. To handle that difficulty would require a somewhat more sophisticated approach.<br>
<br>
Roger Stafford

Wed, 04 Aug 2010 18:58:04 +0000
Re: Looking for an efficient way to find whether a path intersects with a volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288533#768538
Bryan Benson
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i3ccce$18k$1@fred.mathworks.com>...<br>
> "Bryan Benson" <not@an.address> wrote in message <i3c8m6$256$1@fred.mathworks.com>...<br>
> > Hi,<br>
> > <br>
> > I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.<br>
> > <br>
> > The goal: I want to know whether a path, given by a series of coordinates, intersects with a volume, also given by a series of coordinates, where each coordinate represents an volume (let's say 30,50,20 means a volume from 2931,4951,1921).<br>
> > <br>
> > Here's a really simplified setup:<br>
> > path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];<br>
> > volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];<br>
> > The answer should be TRUE, because the last coordinate (3.4,3.9,2.2) is within the region described by the point (4,3,3).<br>
> > <br>
> > The problem: I have to sample a space that's approximately 100x100x100, each path has about 100 coordinates, each volume is given by about 200 coordinates, and the path coordinates are not integers, so I can't just use ismember. I was thinking maybe just to make two test matrices, one for the lower bound (in our example, 29, 49, 19), and one for the upper bound (31,51,21) of each point, and then just check whether each point is greater than the lower bound & less than the upper bound for each point in both matrices, (the path is sampled often enough that I may get away with not having to look at the line in between points as well) but I'm pretty sure I'd grow old waiting for this to run (it has to run this test on ~2000 different paths).<br>
> > <br>
> > If I haven't provided enough information, please don't hesitate to ask for more.<br>
> > <br>
> > Thanks again!<br>
>            <br>
> Let us assume that it is sufficient to test whether the discrete points in the path lie in the volume. For each point in the path you can do a 'floor' on each coordinate to bring them down to integer values. Out of this set of three integers you can then construct seven more sets by adding one to a) one of them, b) to two of them, or c) to all three. For example if you start with the point (1.8,3.1,2.6) above, you first floor them to get (1,3,2). Then from this you also create (2,3,2), (1,4,2), (1,3,3), (2,4,2), (2,3,3), (1,4,3), and (2,4,3). This would give you 800 sets of integer coordinates in place of the 100 in the path. Now you can use these with the 'intersect' function with the 'rows' option for threecolumn matrices. The question is, is the intersection between these and the set of cube centers empty or not. I don't think you will grow old waiting for this answer. <br>
The <br>
> 'intersect' function makes use of sorting so as to greatly reduce computation time for large sets like this. <br>
> <br>
> Of course it is quite possible for a line segment to intersect one of these cubes without either endpoint being in that cube, so the above procedure is not perfect. To handle that difficulty would require a somewhat more sophisticated approach.<br>
> <br>
> Roger Stafford<br>
<br>
Thank you for the fast and elegant responses! I will give these a try and see (since I have a reference of what the data should look like at the end) whether it will be necessary to test the lines in between points, or whether the discrete points will be sufficient.

Wed, 04 Aug 2010 19:53:05 +0000
Re: Looking for an efficient way to find whether a path intersects with a volume
http://www.mathworks.com/matlabcentral/newsreader/view_thread/288533#768564
Roger Stafford
"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <i3ccce$18k$1@fred.mathworks.com>...<br>
> Let us assume that it is sufficient to test whether the discrete points in the path lie in the volume. For each point in the path you can do a 'floor' on each coordinate to bring them down to integer values. Out of this set of three integers you can then construct seven more sets by adding one to a) one of them, b) to two of them, or c) to all three. For example if you start with the point (1.8,3.1,2.6) above, you first floor them to get (1,3,2). Then from this you also create (2,3,2), (1,4,2), (1,3,3), (2,4,2), (2,3,3), (1,4,3), and (2,4,3). This would give you 800 sets of integer coordinates in place of the 100 in the path. Now you can use these with the 'intersect' function with the 'rows' option for threecolumn matrices. The question is, is the intersection between these and the set of cube centers empty or not. I don't think you will grow old waiting for this answer. <br>
The <br>
> 'intersect' function makes use of sorting so as to greatly reduce computation time for large sets like this. <br>
> <br>
> Of course it is quite possible for a line segment to intersect one of these cubes without either endpoint being in that cube, so the above procedure is not perfect. To handle that difficulty would require a somewhat more sophisticated approach.<br>
> <br>
> Roger Stafford<br>
       <br>
Urs has put me to shame by furnishing all the necessary code, so I will do likewise. Let C be the n by 3 array of all cube centers, and let P be the m by 3 array of all discrete path points. Then do:<br>
<br>
P1 = floor(P);<br>
P2 = P1; P2(:,1) = P2(:,1)+1; P1 = [P1;P2];<br>
P2 = P1; P2(:,2) = P2(:,2)+1; P1 = [P1;P2];<br>
P2 = P1; P2(:,3) = P2(:,3)+1; P1 = [P1;P2];<br>
b = ~isempty(intersect(P1,C,'rows');<br>
<br>
If b is true, then the path intersects the volume; otherwise it doesn't (subject to the caveat I mentioned previously.)<br>
<br>
Roger Stafford