0

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

points

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). – Ming-Tang Aug 11 '14 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. – GlenH7 Aug 12 '14 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 '14 at 7:34
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.