Efficiently finding the intersections of an array of lines

Question

I am finding the intersection of an array of lines via determinants. However, to look for all intersections, I am checking each line with every other line, creating O(n^2) checks.

Is there a more efficient way to check for all of the intersections? I'm afraid of the run time when I am trying to sort out the intersections between hundreds or thousands of lines.

Answer 1

Please specify - do you mean infinite lines?

For line segments there is efficient Bentley-Ottmann algorithm.

For N infinite lines there are about N^2 intersections (if most of them are not parallel), so your approach is optimal in complexity sense (perhaps, micro-optimization is possible)

Edit: with clarified task description Bentley-Ottmann looks like overhead.

Find intersections of lines with clipping window
(for example, using Liang-Barsky algorithm)
Consider only lines that intersect window

Scan top window border from left corner to the right
Insert every line end into the binary search tree 
(and add link to this tree node from the paired end to the map) 


Scan right window border from top corner to the bottom right one
Check whether current line already has another end in the tree/map
If yes
    all lines with ends between positions of the first and 
    the second ends do intersect with it
    Calculate intersections and remove both line ends from tree and map
else
  Insert line end into the list

Continue for bottom and left edge.

Complexity O(N) for preliminary treatment and O(K + MlogM) for M lines intersecting window rectangle and K intersection (note that K might be about N^2)

Example: tree state for walking around the perimeter

 E               //and map F to E node
 EG              //and map H to G
 EGI     
 EGIK
 EGIK + H
      H has pair point G, so GH intersect IJ and KL
      remove G
 EIK
 EIK + F
      F has pair point E, so EH intersect IJ and KL
      remove E
 IK
 IK + J
      J has pair point I, so IJ intersect KL
      remove I
 K
 K+L  
    remove K
 end (5 intersections detected)