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.

take a look at [Implementing Hoey Shamos algorithm with C#](https://stackoverflow.com/q/18512815/2521214) — Spektre, Jun 23 '17 at 07:26

MBo · Accepted Answer · 2017-06-21T16:24:02.040

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)

Infinite length for this purpose of this question, in reality limited by the size of the image they are in. I could probably extend all the lines to be no larger than the image and use the Bently-Ottmann, how I would do that I am not sure. — Douglas Gaskell, Jun 21 '17 at 05:27
You can use any line clipping algorithm - for example, Liang-Barsky one, then use points on window border as segment ends. — MBo, Jun 21 '17 at 05:32
Great answer! I'm going to try and translate this into code and see how it works out for me, I will accept the answer once I've done that and verified. What did you use to create your annotation? — Douglas Gaskell, Jun 21 '17 at 21:34

Efficiently finding the intersections of an array of lines

1 Answers1