title: I need an algorithm for merging/joining a range of segments into a range of polylines
body: <p>I have a range of segments that at most intersect with each other at their ends. I want to merge these segments into polylines. </p>
  
  <p>Is there an algorithm that does this in <code>O(N_segments)</code> without using extra storage (e.g. without having to build a tree or some other spatial data-structure for the segment points and working on that)?  </p>
  
  <p>The number of segments I have is small, O(10). So putting them into a dynamic data-structure like a hash-table or a map (red-black tree) would probably be more expensive than the <code>O(N^2)</code> loop at the end unless I put that data-structure on the stack and avoid any memory allocations (The polylines I am using are implemented using a <code>small_vector</code>, which avoids allocations as long as the number of points is small enough.</p>
  
  <p>Currently I've come up with this:</p>
  
  <pre><code>polylines = []
  // 1. Append each segment to a range of polylines, merging when possible:
  for each segment in segments:
      for each polyline in polylines:
         merge_result = merge(segment, polyline)
         if (not merge_result) continue
         polyline = merge_result
         goto done
  
      // either polylines empty or no merge possible
      polylines.append(segment)
  
      done:
        continue
  
  // 2. Try to merge the polylines among themselves until no more merges are possible
  // Pure brute force, quadratic
  done = false
  while not done:
      for p1 in polylines: 
          for p2 in polylines[p1..end]:
              merge_result = merge(p1, p2)
              if not merge: continue
              p1 = merge_result
              polylines.remove(p2)
              done = false
              goto restart
      restart: continue
  </code></pre>
  
  <p>But the second loop is clearly quadratic, so I wonder if there is a better algorithm to merge/join/combine a sequence of segments among themselves.</p>