## Finding intersections on a graph

### Finding intersections on a graph

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.

### Finding intersections on a graph

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

You can and should speed it up, then.  But the principle will always
have to remain to test each line against, at least possibly, all
others.  That's strictly necessary because it's possible to create
situations where every edge *does* indeed intersect every other one.
For your algorithm to find them all, it must be able to test every
edge against every other.  It just shouldn't do so in the more typical
cases.

The usual methods to avoid testing each against every are to subdivide
the scene into smaller regions, so you can restrict testing each
object only against those that can possibly intersect it.

--

Even if all the snow were burnt, ashes would remain.

### Finding intersections on a graph

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

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

### Finding intersections on a graph

Correction:
The real problems are end point intersections and ...

G.H.

### Finding intersections on a graph

Just an idea : in CAD data, many edges are vertical or horizontal. Don't
test parallel edges, and use simplified code for vertical/horizontal
intersections.

--
Philippe Guglielmetti - www.dynabits.com

### Finding intersections on a graph

Thanks for your answer Hans. Maybe Ill try to divide the scene into a
grid (5x5 for example) to avoid testing all existing lines when a new
line is added. I just dont know if the tests to exclude lines from
intersection region will not be very time consuming too...

### Finding intersections on a graph

Thank you Gernot. Ill study your suggestions.

### Finding intersections on a graph

> Just an idea : in CAD data, many edges are vertical or horizontal. Don't
> test parallel edges, and use simplified code for vertical/horizontal
> intersections.

Philippe,

good point. Additionally it might be important whether the coordinates
are stored as incremental floats, e.g. in 0.001 mm units or their equiva-
lents in integer. This would simplify the finding of EQUAL points, espe-
cially for connected line end points.

Best regards  --Gernot Hoffmann

### Finding intersections on a graph

> Thanks for your answer Hans. Maybe Ill try to divide the scene into a
> grid (5x5 for example) to avoid testing all existing lines when a new
> line is added. I just dont know if the tests to exclude lines from
> intersection region will not be very time consuming too...

The idea is that you test each line only once to determine which
subdivision cells it's in, which should be O(N) for N objects.  Then
you run the actual tests and hope that on average, most of the N other
objects will not fall into any of the cells your current object
intersects.

A regular grid is not necessarily the best choice, but a usable first
example of this kind of subdivision.  For better results, the
subdivision should be adaptive and hierarchical, e.g. a k-d tree.
--

Even if all the snow were burnt, ashes would remain.

Dear ALL,

I'm looking for an algorithm to determine the intersection areas of a
set of polygons where the polygons may have joint contours which should
not be removed during the intersection. The polygon are arbritrary and
not restricted to be triangles or quadrangles. Preferable C-code.

________               _________
\      /\             |    |    |
\    /  \            |    |    |
\  /    \ intersect |    |    |
\/______\          |____|____|

^                 ^
|_________________|

identical positions
for intersection

|
\ /

____              _____
|   /|\           |     \
|  / | \          |      \
| /  |  \  rather |       \
|/___|___\  than  |________\

Any ideas? I tried Alan Murta's gpc but it seems that gpc removes the
inner boundaries.

Cheers, Uli
--
========================================
Ulrich Lenk
Institute of Cartography
University of Hannover

========================================