From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Looking for an efficient way to find whether a path intersects with a volume
Date: Wed, 4 Aug 2010 18:43:26 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 24
Message-ID: <i3ccce$18k$>
References: <i3c8m6$256$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1280947406 1300 (4 Aug 2010 18:43:26 GMT)
NNTP-Posting-Date: Wed, 4 Aug 2010 18:43:26 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: comp.soft-sys.matlab:659094

"Bryan Benson" <not@an.address> wrote in message <i3c8m6$256$>...
> 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