Prev: Really need help to speed up piece of code
Next: mmreader method
From: Bryan Benson on 4 Aug 2010 13:40
Hi,

I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.

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 29-31,49-51,19-21).

Here's a really simplified setup:
path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];
volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];
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).

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).

If I haven't provided enough information, please don't hesitate to ask for more.

Thanks again!
From: us on 4 Aug 2010 14:11
"Bryan Benson" <not(a)an.address> wrote in message <i3c8m6$256$1(a)fred.mathworks.com>...
> Hi,
>
> I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.
>
> 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 29-31,49-51,19-21).
>
> Here's a really simplified setup:
> path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];
> volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];
> 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).
>
> 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).
>
> If I haven't provided enough information, please don't hesitate to ask for more.
>
> Thanks again!

one of the many solutions

p=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];
v=[4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];
fh=@(z) all(bsxfun(@(x,y) x-1<=y&y<=x+1,v,z),2);
r=cellfun(@(x) fh(x),num2cell(p,2),'uni',false);
r=cat(2,r{:});
disp(r);
%{
0 0 0
0 0 0
0 0 1 % <- P(3) in V(3,:)
0 0 0
0 0 0
%}

us
From: Roger Stafford on 4 Aug 2010 14:43
"Bryan Benson" <not(a)an.address> wrote in message <i3c8m6$256$1(a)fred.mathworks.com>...
> Hi,
>
> I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.
>
> 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 29-31,49-51,19-21).
>
> Here's a really simplified setup:
> path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];
> volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];
> 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).
>
> 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).
>
> If I haven't provided enough information, please don't hesitate to ask for more.
>
> Thanks again!
- - - - - - - - - - - -
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 three-column 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
'intersect' function makes use of sorting so as to greatly reduce computation time for large sets like this.

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.

Roger Stafford
From: Bryan Benson on 4 Aug 2010 14:58
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <i3ccce$18k$1(a)fred.mathworks.com>...
> "Bryan Benson" <not(a)an.address> wrote in message <i3c8m6$256$1(a)fred.mathworks.com>...
> > Hi,
> >
> > I have a problem that is somewhat above my ability, so I thought I'd give you all a try. Thanks in advance.
> >
> > 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 29-31,49-51,19-21).
> >
> > Here's a really simplified setup:
> > path=[1.8,3.1,2.6;2.3,3.5,2.7;3.4,3.9,2.2];
> > volume= [4,4,4;4,3,4;4,3,3;5,3,4;5,3,3];
> > 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).
> >
> > 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).
> >
> > If I haven't provided enough information, please don't hesitate to ask for more.
> >
> > Thanks again!
> - - - - - - - - - - - -
> 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 three-column 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
> 'intersect' function makes use of sorting so as to greatly reduce computation time for large sets like this.
>
> 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.
>
> Roger Stafford

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.
From: Roger Stafford on 4 Aug 2010 15:53
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <i3ccce$18k$1(a)fred.mathworks.com>...
> 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 three-column 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
> 'intersect' function makes use of sorting so as to greatly reduce computation time for large sets like this.
>
> 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.
>
> Roger Stafford
- - - - - - - -
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:

P1 = floor(P);
P2 = P1; P2(:,1) = P2(:,1)+1; P1 = [P1;P2];
P2 = P1; P2(:,2) = P2(:,2)+1; P1 = [P1;P2];
P2 = P1; P2(:,3) = P2(:,3)+1; P1 = [P1;P2];
b = ~isempty(intersect(P1,C,'rows');

If b is true, then the path intersects the volume; otherwise it doesn't (subject to the caveat I mentioned previously.)

Roger Stafford
 | 
Pages: 1
Prev: Really need help to speed up piece of code
Next: mmreader method