Segment Intersection Proposal

Point A Point B Action
X1: 10
Y1: 16 		X2: 15
Y2: 30
Remove

Possible Segment

Point A Point B Action
X1:

Y1:
X2:

Y2:
Add Segment
Evaluate

Step - 0

Reset

Step - 0

Add new segments by specifying the beginning and end of the segments, once all desired segments were added, define a segment to evaluate it against all previously added segments.

The complexity of the proposed algorithm is O(N), without the need to order the segments we propose 4 steps to define all the segments that cross the segment to evaluate. But we can use a binary range search to reduce the space to evaluate, with a complexity of O(log(n) + k), where k defines the number of segments that "touch" the shadow of the evaluate segment, if this aproach is used that means more memory to store the proyection on X an Y axes.

The algorithm proposed is output sensitive, so in the case we want to evaluate all the segments against all segments the worse case is O(N^2) when all the segments are crossed and the segments are not sorted.

Step - 1

We check the proyection of the evaluated segment against all the other segments on the X axis. [O(n) if are not sorted the elements or O(log(n) + k) if we use a Range Search algorithm], where k defines the number of segments that touch the shadow of the evaluated segment.

Step - 2

With the segments that pass the previous test, we check the proyection of the evaluated segment against this list on the Y axis.

We can search in the k element´s list [O(k)], or we can make a Range Search [O(klog(k)) + O(log(k) + m)], where m defines the segments that pass the second test.

Step - 3

If exists a segment that crosses the evaluated segment, it must cross from the red zone to the blue zone. We search in the m element´s list [O(m)].

Step - 4

Finally with the segments that passes all the previously tests, we check if this segments really crossed the evaluated segment, giving us the following list of crosses: