Re: Line intersection, scaled to thousands of points

I'm looking at Sedgewich's Algorithms in C++, where he discusses the general problem of line intersection (which is what you have here). The solution he presents is rather detailed, but the gist is that you want to sort on the y coordinate, and add the line segments (with some identification) to a binary tree when a line segment starts (based on the y position), and remove it when it ends. The tree should be sorted on the 'rightness' of a line segment to another (that is, the entire line being to the right of the other line). Note that 'rightness' is not transitive; if line C is right if line A, and line C is right of line B, line B need not be right of line A (it may intersection). So the key step when this tree is built and taken apart is that when a node is removed, and a new node is moved into place to balance the tree somewhere, you must explicit test the connection between any new node connections, as this is where you'll find the intersections of two lines; if 'rightness' or 'leftness' of a parent and a child node after a valid reconstruction can't be determined, then the two lines must intersect. A intersection-less set of lines will result in an empty tree when all is said and done.

I strongly refer to that book or any other good book on computer algorithms for more details.

The method should be O(N*log N), both for the intitial point sorting, and for the building/traversing of the tree. Note that you could also just compare each and every line, but that's O(N^2). I don't think you can cut this down any further while some additional huristics that are based on human observation.

Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain

Comment on Re: Line intersection, scaled to thousands of points

Replies are listed 'Best First'.
Re: Re: Line intersection, scaled to thousands of points by Anonymous Monk on Jul 18, 2001 at 20:35 UTC
For graphics algorithms, check the Graphic Gems series of books. Many are raster-rendering, but vector-polygon processing is covered too. The old standby was the CALGO Collected Algorithms of the ACM. I used to have that on Microfiche subscription, but I think it's online now.) -- Bill	[reply]
Re: Re: Line intersection, scaled to thousands of points by John M. Dlugosz (Monsignor) on Jul 18, 2001 at 19:33 UTC
I like that way. Upon reading the question, I realized that the normal edge-sorting technique used in rendering does tell when lines cross, but it only samples the shape at the rastors. It makes sence, though, that you can compare intervals instead.	[reply]