Press the green flag for random lines with their intersections. This is a utility that can be used in applications to determine all the intersections in a set of line segments. Coordinates must be in whole pixels using screen coordinates. Only true intersections are calculated, not co-linear endpoints, endpoints that exactly touch a line, or linearly overlapping segments. (I wrote this because I think it will be useful in writing a polygon filler... see http://scratch.mit.edu/projects/51071894/ - I'm already using it in my quad filler... http://scratch.mit.edu/projects/51488276/ ) The code has been optimised considerably from the first release.
Pro: it works Con: n^2 loop over all lines. Would be more efficient to use quadtrees or some other geometric/spatial data structure; however for the sort of application we'll see here, this is sufficient. (We're only dealing with lines that are on-screen. A more optimised program could handle lines in world space instead and would need to handle a lot more lines) The code was derived from http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect but had to be tweaked to confirm that the intersection point between two lines is actually within the line segments themselves. There is a small bug. Internally, it needs to test A intersects B and B intersects A. Not sure why, the code ought to be symmetric and find the intersection from either test. However for now I have wrapped the code in a block which does both tests. Unfortunate that the runtime is twice as much. I did however rewrite the low-level part of the code to speed it up a lot - it now does only one floating point divide per call. BUG!!! After 2 years I just now spotted that 100% vertical lines do not register a crossing line!
