How to chain together points in an array

Question

I have a series of points with lengths and rotations like this:

I need to create separate chains from points whose lines overlap but I’m having real trouble doing this efficiently.

I have an array of simple Point objects, in no particular order, and I can loop through them and test them with a simple "intersect" function. I need to end up with an array of chains, each with an ordered list of points. (Or another way of representing the chains).

At the moment every avenue I explore seems to involve a convoluted hack of arrays, nudges and fudges. Having never studied Computer Science I wonder if there is some sort of data structure or technique that would lend itself well to this sort of thing.

Answer 1

A naive algorithm for this takes O(n^2) time, that is, for every line you add to the total number of lines, it takes (very roughly) the square of that number of lines in terms of time. So if checking one line took one second, then if we have 5 lines, it'd take 25 seconds.

In order to efficiently process the intersections, we can use a number of different algorithms. Most of these are sweep line algorithms. A common one is the Bentley-Ottmann algorithm. It's not the fastest algorithm for this sort of task but it's fairly easy to implement. You'll need a binary search tree and a priority queue. They are both kinds of trees. Specifically you'll need a red-black tree or similar self-balancing binary tree. Also a binary heap is needed to build the priority queue.

This will process the number of intersections in O(n+k)*log(n)) time. Logarithmic time is less than linear time so this algorithm is more efficient than our naive attempt. There are of course faster options but they are generally more complex.