Calculating the intersections between n line segments can be done in n log n time. Here, segments are only checked for intersection when they are newly adjacent after a line start, end or intersection. The dots on the left show the order of the lines at each adjacency change, with newly adjacent pairs of lines connect by a black line.