Thread Subject: Line segment intersection?

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!

"Steve " <stefan.griesser@alumni.unileoben.ac.at> wrote in message <i2un88$2og$1@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

"Steve " <stefan.griesser@alumni.unileoben.ac.at> wrote in message <i2un88$2og$1@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

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

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.

ImageAnalyst <imageanalyst@mailinator.com> wrote in message <8887b212-9387-4b54-af5f-6f8e388aa410@j8g2000yqd.googlegroups.com>...
> 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.

Thanks for your answer.
Every line is growing over time and i want to check which lines are colliding and stop the growth of these lines. Like in my example.

I'm using such a 2D matrix at the moment, but when the lines get very long this matrix gets very huge, sometimes more than the allowed variable size allowed.

So I'm looking for an analytical way. This is really tricky...

Then I'd probably do something like this:

for each blue line
  calculate distance of blue endpoints to each red endpoint
  if any of those distances <= radius
    This is the really trivial case.
    There IS definitely an intersection so you can bail out of loop
  else
    There MAY be an intersection IN BETWEEN the blue endpoints
    This is the more complicated case
    for each red endpoint, calculate perpendicular distance to blue
line as if blue line were infinitely long using standard geometrical
"point-line distance" equations.
      if (perpendicular distance < Radius) && (blue midpoint
coordinates are in between blue endpoints)
        There is an intersection in the middle of the blue line
somewhere
        bail out of loop
      else
        This line does not intersect anywhere
      end % of if
    end % of for loop to check red endpoints
  end
end % of for loop over all blue lines.

You can check if the blue mid point is between the blue endpoints just
by doing this:
if (midx > minEnd1x) && (midx < maxEnd1x) && ...
 (midy > minEnd1y) && (midy < maxEnd1y)
      Then the "in between point" is really in between the actual
endpoints.
end

Ref for point-line distance:
http://www.intmath.com/Plane-analytic-geometry/Perpendicular-distance-point-line.php

"Steve " <stefan.griesser@alumni.unileoben.ac.at> wrote in message <i2un88$2og$1@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+');
>

There are few tools in FEX that might ease to carry out the task, such as this one (not tested myself):
http://www.mathworks.com/matlabcentral/fileexchange/28268-calculation-of-distances-from-a-given-set-of-points-to-a-set-of-segments

Bruno

> There are few tools in FEX that might ease to carry out the task, such as this one (not tested myself):
> http://www.mathworks.com/matlabcentral/fileexchange/28268-calculation-of-distances-from-a-given-set-of-points-to-a-set-of-segments
>
> Bruno


Bruno, thank you very much for that link. This is exactly what I needed.

Works perfect!