# How to chain together points in an array

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.

• This is a coding problem and it belongs to Stack Overflow or possibly Mathematics and Game Development (if it's for a game). Aug 11, 2014 at 23:49
• @SHiNKiROU - questions about algorithms are on-topic for Programmers. OP is wanting to find a solution to the problem and not necessarily just a theoretical discussion of how to solve the problem.
– user53019
Aug 12, 2014 at 0:41
• My original question asked for pseudo-code so I am actually looking for a specific solution, albeit not necessarily in a specific language.
– Josh
Aug 12, 2014 at 7:34

## 1 Answer

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.

• We've got ~nlog(n), which is linearlogarithmic. Quadratic is linear*linear and since logarithmic is less than linear, nlogn < quadratic.
– user28988
Aug 12, 2014 at 2:29
• Right, my mistake. Aug 12, 2014 at 2:31