Finding intersections on a graph

Finding intersections on a graph

Post by Adriano Cos » Tue, 08 Jul 2003 22:29:29



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.

 
 
 

Finding intersections on a graph

Post by Hans-Bernhard Broeke » Tue, 08 Jul 2003 23:17:07



> 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

Post by Gernot Hoffma » Wed, 09 Jul 2003 04:11:59



> 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

 
 
 

Finding intersections on a graph

Post by Gernot Hoffma » Wed, 09 Jul 2003 04:20:28


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

G.H.

 
 
 

Finding intersections on a graph

Post by Philippe Guglielmett » Wed, 09 Jul 2003 19:06:10


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

Post by Adriano Cos » Thu, 10 Jul 2003 03:43:34


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

Post by Adriano Cos » Thu, 10 Jul 2003 03:45:08


Thank you Gernot. Ill study your suggestions.
 
 
 

Finding intersections on a graph

Post by Gernot Hoffma » Thu, 10 Jul 2003 04:18:33



> 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

Post by Hans-Bernhard Broeke » Thu, 10 Jul 2003 15:11:12



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

 
 
 

1. intersection of polygons/planar graphs

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

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

2. ZScript as PS interpreter...

3. Q: finding the intersection between circles

4. Resources for Editing Digital Camera Images

5. efficient way to find curve-surface intersection

6. NVSA Vis Position

7. --HELP-- Find intersection point

8. plotting lines

9. Looking for algorithms to find intersection line of two surfaces

10. Finding 2d Line Intersection Points

11. Sweep Line Algorithm to find intersections

12. Finding the 4 intersection points of plane/sphere

13. Find intersection of ray with icosahedron