Figure 2: Outline of the Bentley-Ottmann algorithm
C = collection of all non-vertical line segments.
ScanSet = sorted collection of x-values of all segment endpoints.
ActiveSegs = sorted subcollection of segments from C which are
intersected by the current scanline.
for (each x_c in ScanSet)
Reorder ActiveSegs based on x_c
for each segment s in C
if (x_c is the left endpoint of s)
insert s into ActiveSegs
report any new intersections created and update ScanSet
for each segment s in ActiveSegs
if (x_c is the right endpoint of s)
remove s from ActiveSegs
report any new intersections created and update ScanSet
else // x_c is a point of intersection of two or more segments in
ActiveSegs reverse the order of the segments that
intersect s at this point report any new intersections
created and update ScanSet