First, regarding the intersection of lines: you do not need the actual intersection point, only to find out if they intersect. See http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ for an algorithm that does just that.
About List implementation:
In your implementation using List s, you call indexOf in sweepline to find nl . It seeks a sweepline from start to finish. See List(T).IndexOf . If you used the BinarySearch method, this should speed up the search significantly.
The documentation list contains a paragraph called performance considerations. They strongly recommend using a value type that implements IEquatable<T> and IComparable<T> . So your Line2D should be struct and implement these interfaces.
If you follow this advice, extracting the endpoint from the sweepline should be O (log n), which is enough for your purpose, and the memory should be used more efficiently.
Insert and delete are O (n) for lists, as a result of which the base array needs to be moved in memory. A SortedSet has faster insertion and deletion, but I don't quite understand how to find the neighbors of elements in O (log n). Anyone? (See also Why SortedSet <T> .GetViewBetween is not O (log N)? )
In any case, C5 TreeSet should solve this problem.
I looked at the performance of IndexOf and [i] in the user manual , and both are listed as O (log n), so this should not be a problem. This is probably somewhat faster, but nothing more than a fixed factor, to name specific methods for finding neighbors on sweepline, i.e. Successor and Predecessor , which are also O (log n).
So,
[...] try { Line2D above = sweepline.Successor(nl); if (above.intersectsLine(nl)) { return false; } } catch (NoSuchItemException ignore) { } [...]
I do not like that they do not have a method that does not throw an exception, since throwing a throw is very expensive. Your scan line will be quite complete, so I think it’s rare to find it, and calling Successor is the most efficient way. Alternatively, you could continue to call indexOf as it is now, but check to see if it is Count minus one before retrieving [index + 1] and prevent the exception from being thrown:
[...] int index = sweepline.IndexOf(nl); if( index < sweepline.Count-1 ) { Line2D above = sweepline[index + 1]; if (above.intersectsLine(nl)) { return false; } } [...]
Chapter Two of the manual describes equality and comparison for C5 collections. Here, too, at least you should implement IEquatable<T> and IComparable<T> !
Another thought: you are reporting an algorithm feed of 700,000 lines. Could you start by synchronizing, for example, 1000, 2500, 5000, 10000 lines and see how the algorithm scales for cases when they do not overlap?
How to compare lines on sweepline:
You need to find the natural order for Line2Ds in the Sweepline TreeSet, as the CompareTo method will ask you to compare one Line2D with another. One of Line2Ds is already in the Sweepline TreeSet, the other just met and added.
Your sweepline works from bottom to top, I think:
List<AlgEvent> SortedList = events.OrderBy(o => o.getY()).ToList();
So, let the S1 segment be added to the TreeSet at event 1, and we want to compare it with S2, which is added to event 2, right now.
Line segments may intersect at some point, which would change the order, but the algorithm will check this right after inserting them in the checks above and below. Which might be better called left and right checks, think about it.
In any case ... it would be easiest to compare the lower endpoints of both line segments. Less on the left, more on the right. However, we need to look at the ordering in the sweepline position, and since then they may have changed positions, as in the picture.
So, we need to compare the lower endpoint S2 with the red dot on S1 and see if it lies to the left or right of this point. It lies to the left, so S2 is considered less than S1.
This is usually simpler: if all S1 lies to the left of the lower endpoint S2, S1 is less than S2. If all S1 is to the right of the lower endpoint of S2, S1 is greater than S2.
I think you're looking for an interface type version:
public class Line2D : IComparable<Line2D>
Assuming the two BottomY properties, the smallest of the two values Y and BottomX , the X value of the smallest endpoint, a somewhat verified attempt:
int IComparable<Line2D>.CompareTo(Line2D other) { if( BottomY < other.BottomY ) { return -other.CompareTo(this); }