> Hello.

> On my CAD application I have a situation where I have to create a

> graph with the elements that can be represented by line segments. Once

> the elements have included its line segments as edges on the graph, I

> need to determine all the intersections between the edges. Does anyone

> know an efficient algorithm to find all the intersections on an graph?

> Testing each line with all others is impossible, too slow.

> Thanks in advance for any help.

> Adriano.

Adriano, a few practical recommendations:

First step:

Re-arrange all line segments in a way that they are drawn from left to right.

This allows a very fast check whether the other segment is totally left or

totally right and therefore not a candidate for an intersection.

A similar additional sorting from bottom to top is impossible.

Second step:

Dont calculate intersections if these dont exist.

X = P1 + s*(P2-P1)

X = Q1 + t*(Q2-Q1)

s*(P2-P1) - t*(Q2-Q1)= Q1-P1

For x,y, by Cramer:

a11*s + a12*t = r1

a21*s + a22*t = r2

D = a11*a22 - a12*a21

S = r1*a22 - r2*a12

T = r2*a11 - r1*a21

s = S/D

t = T/D

True intersection if 0<s<1 and 0<t<1:

If D>0:

Intersection if 0<S<D and 0<T<D

If D<0:

Intersection if 0>S>D and 0>T>D

If true intersection then calculate s=S/D and X.

A division is executed ONLY if the true intersection of segments

exists.

The real problems are edge intersections and overlapping segments

(multiple solutions).

The check for 100x100 segments = 10.000 tests needs about 2ms.

Best regards --Gernot Hoffmann