title: How to intersect two polygons?
body: <p>This seems non-trivial (it gets asked quite a lot on various forums), but I absolutely need this as a building block for a more complex algorithm.</p>
  
  <p><em>Input</em>: 2 polygons (A and B) in 2D, given as a list of edges <code>[(x0, y0, x1, y2), ...]</code> each. The points are represented by pairs of <code>double</code>s. I do not know if they are given clockwise, counter-clockwise or in any direction at all. I <em>do</em> know that they are not necessarily convex.</p>
  
  <p><em>Output</em>: 3 polygons representing A, B and the intersecting polygon AB. Either of which may be an empty (?) polygon, e.g. <code>null</code>.</p>
  
  <p><em>Hint for optimization</em>: These polygons represent room and floor boundaries. So the room boundary will normally fully intersect with the floor boundary, unless it belongs to another floor on the same plane (argh!).</p>
  
  <p>I'm kind of hoping someone has already done this in c# and will let me use their strategy/code, as what I have found so far on this problem is rather daunting.</p>
  
  <p><strong>EDIT</strong>: So it seems I'm not entirely chicken for feiling faint at the prospect of doing this. I would like to restate the desired output here, as this is a special case and might make computation simpler:</p>
  
  <p><em>Output</em>: First polygon minus all the intersecting bits, intersection polygons (plural is ok). I'm not really interested in the second polygon, just its intersection with the first.</p>
  
  <p><strong>EDIT2</strong>: I am currently using the <a href="http://www.cs.man.ac.uk/~toby/gpc/" rel="noreferrer">GPC (General Polygon Clipper)</a> library that makes this really easy!</p>