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.
xxxxxxxxxx<meta charset="utf-8"><style>.seg{ stroke-width: 4px;}.q{ stroke: black; stroke-dasharray: 2 4 2 6;}.point{ stroke: black;}.check{ stroke: black;}html{ width: 960px; height: 500px;}</style><script src="/1wheel/raw/67b47524ed8ed829d021/d3-3.5.5.js"></script><script src="/1wheel/raw/67b47524ed8ed829d021/lodash-3.8.0.js"></script><script src='/1wheel/raw/1b6758978dc2d52d3a37/d3-jetpack.js'></script><script src='/1wheel/raw/1b6758978dc2d52d3a37/d3-starterkit.js'></script><script src='/1wheel/raw/5d32ecb8a54b42f53646/geometry.js'></script><script src='n-line-intersection.js'></script>