title: How to split a general closed polygon by a line segment
body: <p>I need a good (robust) algorithm for splitting a polygon into two sets(left/right) by a line segment. My polygon representation is simply a list of integer coordinates(ordered clock wise, never self intersecting) and the line segment is represented by a start and end point. The line always starts and ends outside the polygon, i.e. intersects the polygon an even number of times.</p>
  
  <p>Here is an example:</p>
  
  <p><img src="https://i.imgur.com/5CIfU0G.png" alt="The polygon should be split into two sets of two polygons each."></p>
  
  <p>The output of the algorithm should be the two sets(travelling clock wise):</p>
  
  <ul>
  <li>Left: HABCH, FGDEF</li>
  <li>Right: HCDGH, BAB, FEF</li>
  </ul>
  
  <p>I can identify the points A-H by iterating the polygon and checking if a polygon segment crosses the line, taking care to respect border cases. I can also determine which side each multi-line belongs to. I cannot though, for the life of me, decide how to string these segment together.</p>
  
  <p>Before you suggest a general purpose clipping library: I am using boost polygon which is very good at clipping polygons against each other, but I haven't found any library which let's you clip a polygon against a line segment and it is not possible in general to turn the line segment into a polygon which I could clip with.</p>
  
  <p>EDIT: I had missed FEF and the fact that a polygon can have parts on both sides of the line segment. </p>