Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
fast algorithm for detecting all Intersections of multiple linesegments

Subject: fast algorithm for detecting all Intersections of multiple linesegments

From: Jens Hilwig

Date: 2 Apr, 2008 09:55:12

Message: 1 of 5

Hello,

Im looking for a fast algorithm for detecting all Intersections of multiple
linesegments.(only linesegments nothing else)
In 2D there is a fast sweep line algorithm by Bentley-Ottmann but I did not
found a fast alogorithm for the 3D space.
Can you help me ?

regards
jens

Subject: fast algorithm for detecting all Intersections of multiple linesegments

From: Ashish Uthama

Date: 2 Apr, 2008 17:50:50

Message: 2 of 5

in what form do you have the line segments?
  array of end points?
  arbit collection of points for each segment?
  equation based?


On Wed, 02 Apr 2008 05:55:12 -0400, Jens Hilwig <jhilwig@gmx.de> wrote:

> Hello,
>
> Im looking for a fast algorithm for detecting all Intersections of
> multiple
> linesegments.(only linesegments nothing else)
> In 2D there is a fast sweep line algorithm by Bentley-Ottmann but I did
> not
> found a fast alogorithm for the 3D space.
> Can you help me ?
>
> regards
> jens
>
>

Subject: sorry send above to fast....

From: Jens Hilwig

Date: 2 Apr, 2008 20:55:52

Message: 3 of 5

Hello,

thank you for answering the points came as Array of LineSegment Pointers
(LS) in c++

struct LS
{
    double x1;
    double y1;
    double z1;

    double x2;
    double y2;
    double z2;
}





"Ashish Uthama" <ashishu@ece.ubc.ca> schrieb im Newsbeitrag
news:op.t8zvu0hlxwvkfj@uthamaa.dhcp.mathworks.com...
> in what form do you have the line segments?
> array of end points?
> arbit collection of points for each segment?
> equation based?
>
>
> On Wed, 02 Apr 2008 05:55:12 -0400, Jens Hilwig <jhilwig@gmx.de> wrote:
>
>> Hello,
>>
>> Im looking for a fast algorithm for detecting all Intersections of
>> multiple
>> linesegments.(only linesegments nothing else)
>> In 2D there is a fast sweep line algorithm by Bentley-Ottmann but I did
>> not
>> found a fast alogorithm for the 3D space.
>> Can you help me ?
>>
>> regards
>> jens
>>
>>
>

Subject: fast algorithm for detecting all Intersections of multiple linesegments

From: Roger Stafford

Date: 3 Apr, 2008 13:24:03

Message: 4 of 5

"Jens Hilwig" <jhilwig@gmx.de> wrote in message
<65h3g1F2fsf9dU1@mid.uni-berlin.de>...
> Hello,
>
> Im looking for a fast algorithm for detecting all Intersections of multiple
> linesegments.(only linesegments nothing else)
> In 2D there is a fast sweep line algorithm by Bentley-Ottmann but I did not
> found a fast alogorithm for the 3D space.
> Can you help me ?
>
> regards
> jens
-----------
  It has occurred to me that you could make use of the two-dimensional fast
line sweep Bentley-Ottmann algorithm itself in solving your three-
dimensional problem. Suppose you project your 3D segment endpoints onto
the x-y plane (that is, ignore their z-coordinates) and use the Bentley-
Ottmann method for finding all the apparent segment intersections as seen
on that projection. Then do a projection of the original 3D endpoints onto
the x-z plane and again find all the apparent intersections on that plane.

  Any true 3D intersection between a particular pair of segments must appear
on both projections with the same x-coordinate. Furthermore, if a pair of
segments do have the same intersection x-coordinate in both projections, it
must be a true 3D intersection, except in the case of segments orthogonal, or
very nearly orthogonal, to the x-axis. Therefore the two fast sweeps will
almost have completed the job. If the cases of segments nearly orthogonal to
the x-axis create difficulties, perhaps a third projection onto the y-z plane
together with another line sweep would be useful in making the algorithm
"fail-safe".

  You can directly check for the validity of a line-line intersection using
formulas (19), (20), and (24) at the website

 http://mathworld.wolfram.com/Line-LineIntersection.html

Of course it is important in formulas (19) and (20) to allow some carefully
chosen amount of error tolerance to properly distinguish line segments that
almost but actually do not quite intersect, from cases of mere round-off
error.

Roger Stafford

Subject: fast algorithm for detecting all Intersections of multiple linesegments

From: Tal Tiro

Date: 18 Oct, 2008 00:28:02

Message: 5 of 5

"Ashish Uthama" <ashishu@ece.ubc.ca>

I have been able to generate a set of finite segments; that have random orientation and normal length distribution. I need an algorithm that can pick only finite segments that are intersecting across the entire square domain (i.e from one side of the domain boundary to the other) and leave out those that are localized clusters.

thanks

Tal
>

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us