Prev: frame based input of RC digital low pas filter
Next: PCA problem and Memory error
From: Steve on 30 Jul 2010 10:23
Hi all,

I have a lot of line segments and I want to see if a specific line collides with another line segment within a certain radius.

Here's an example:

close all; clear;
%
% Generate the lines
Lines = [0.4214,0.9079, 0.2558, 0.3329
0.5135, 0.8358, 0.6790, 0.5828
0.0861, 0.3706, 0.5698, 0.5780
0.7157, 0.2439, 0.4407, 0.2900
0.5632, 0.2852, 0.7828, 0.3689];
%
%
%
figure;
axis image;
hold on;
%
% Draw the lines (The first one in red)
for k = 1:size(Lines,1)
x = Lines(k, 1:2);
y = Lines(k, 3:4);
if (k==1)
color = [1 0 0];
else
color = [0 0 1];
end;
line(x, y, 'Color', color);
end;
%
%Plot the Radius
Radius = 0.1;
t = linspace(0, 2*pi, 100);
xr = Lines(1,1) + Radius * cos(t);
yr = Lines(1,3) + Radius * sin(t);
plot(xr, yr, 'r');
plot(Lines(1,1), Lines(1,3), 'r+');

How can I calculate if the red line collides with any of the other lines (if any other line lies in that circle with Radius R)? I have more than 30000 Lines, and that is placed in a loop as well, so only a very efficient code would help!

Thanks very much!
From: John D'Errico on 30 Jul 2010 10:39
"Steve " <stefan.griesser(a)alumni.unileoben.ac.at> wrote in message <i2un88$2og$1(a)fred.mathworks.com>...
> Hi all,
>
> I have a lot of line segments and I want to see if a specific line collides with another line segment within a certain radius.
>
> Here's an example:
>
> close all; clear;
> %
> % Generate the lines
> Lines = [0.4214,0.9079, 0.2558, 0.3329
> 0.5135, 0.8358, 0.6790, 0.5828
> 0.0861, 0.3706, 0.5698, 0.5780
> 0.7157, 0.2439, 0.4407, 0.2900
> 0.5632, 0.2852, 0.7828, 0.3689];
> %
> %
> %
> figure;
> axis image;
> hold on;
> %
> % Draw the lines (The first one in red)
> for k = 1:size(Lines,1)
> x = Lines(k, 1:2);
> y = Lines(k, 3:4);
> if (k==1)
> color = [1 0 0];
> else
> color = [0 0 1];
> end;
> line(x, y, 'Color', color);
> end;
> %
> %Plot the Radius
> Radius = 0.1;
> t = linspace(0, 2*pi, 100);
> xr = Lines(1,1) + Radius * cos(t);
> yr = Lines(1,3) + Radius * sin(t);
> plot(xr, yr, 'r');
> plot(Lines(1,1), Lines(1,3), 'r+');
>
> How can I calculate if the red line collides with any of the other lines (if any other line lies in that circle with Radius R)? I have more than 30000 Lines, and that is placed in a loop as well, so only a very efficient code would help!
>
> Thanks very much!

In 2 dimensions, you need to know if either

- either endpoint of a line segment is within the
specified radius of another segment.

- a pair of line segments cross, but the end points
are not close to the other line, so the previous test
will miss that pair of line segments.

Given 30000 line segments, good luck. Why do
I say this? Because not every thing you wish to
do will be easy to accomplish.

I would probably recommend use of a quad-tree
like decomposition, splitting the domain into
sub-domains. Then you need only worry about
intersections within a given sub-domain. Note
that some line segments may fall inside more
than one sub-domain.

John
From: Sean on 30 Jul 2010 11:38
"Steve " <stefan.griesser(a)alumni.unileoben.ac.at> wrote in message <i2un88$2og$1(a)fred.mathworks.com>...
> Hi all,
>
> I have a lot of line segments and I want to see if a specific line collides with another line segment within a certain radius.
>
> Here's an example:
>
> close all; clear;
> %
> % Generate the lines
> Lines = [0.4214,0.9079, 0.2558, 0.3329
> 0.5135, 0.8358, 0.6790, 0.5828
> 0.0861, 0.3706, 0.5698, 0.5780
> 0.7157, 0.2439, 0.4407, 0.2900
> 0.5632, 0.2852, 0.7828, 0.3689];
> %
> %
> %
> figure;
> axis image;
> hold on;
> %
> % Draw the lines (The first one in red)
> for k = 1:size(Lines,1)
> x = Lines(k, 1:2);
> y = Lines(k, 3:4);
> if (k==1)
> color = [1 0 0];
> else
> color = [0 0 1];
> end;
> line(x, y, 'Color', color);
> end;
> %
> %Plot the Radius
> Radius = 0.1;
> t = linspace(0, 2*pi, 100);
> xr = Lines(1,1) + Radius * cos(t);
> yr = Lines(1,3) + Radius * sin(t);
> plot(xr, yr, 'r');
> plot(Lines(1,1), Lines(1,3), 'r+');
>
> How can I calculate if the red line collides with any of the other lines (if any other line lies in that circle with Radius R)? I have more than 30000 Lines, and that is placed in a loop as well, so only a very efficient code would help!
>
> Thanks very much!

Does it only matter if they intersect once? I.e. If the line is intersected by _any_ other line it's true or do you need the number that intersect it?

If you just need a boolean value for each line this doesn't sound like such a difficult problem as any time there is an intersection, both lines don't need to have any further calculations done for them.
To do this I would set up a sparse upper triangular matrix where each row/column corresponds to 1 line and traverse it horizontally. Once the condition of intersection is met; neither of those rows will need traversed any further cutting down on necessary computations. You could have a table with the points and circle radius/location so that a function; given the two indexes could check the criteria for intersection.

Just a few thoughts; good luck!
-Sean
From: Steve on 30 Jul 2010 20:53
> Does it only matter if they intersect once? I.e. If the line is intersected by _any_ other line it's true or do you need the number that intersect it?
>
> If you just need a boolean value for each line this doesn't sound like such a difficult problem as any time there is an intersection, both lines don't need to have any further calculations done for them.
> To do this I would set up a sparse upper triangular matrix where each row/column corresponds to 1 line and traverse it horizontally. Once the condition of intersection is met; neither of those rows will need traversed any further cutting down on necessary computations. You could have a table with the points and circle radius/location so that a function; given the two indexes could check the criteria for intersection.
>
> Just a few thoughts; good luck!
> -Sean



Well, the problem is that I don't need the intersection point. As soon as a part of any another line is within the certain radius of the tip of my line, this is what I would need. A boolean value would be ok for the first time.
And I don't want to have such a matrix in the background. I have more than 30000 lines, which is more than the allowed variable size in matlab. A vektorized solution would be the best - if possible.
From: ImageAnalyst on 30 Jul 2010 21:13
Are you (1) going to place all the blue lines first and then check
(like your example), or are you (2) going to place one line at each
iteration of a loop and then check against that one line (kind of like
your explanation that mentioned a loop) and then break out of the loop
if the latest line is within the radius?

A dumb brute force way is to write the lines into a 2D matrix (image)
and then use the Euclidean Distance Transform (bwdist() which is in
the Image Processing Toolbox), but I bet there's a more clever
analytical method.
 |  Next  |  Last
Pages: 1 2
Prev: frame based input of RC digital low pas filter
Next: PCA problem and Memory error