> 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, a few practical recommendations:
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.
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:
Intersection if 0<S<D and 0<T<D
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
The real problems are edge intersections and overlapping segments
The check for 100x100 segments = 10.000 tests needs about 2ms.
Best regards --Gernot Hoffmann