How to intersect two polygons?
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.
Input: 2 polygons (A and B) in 2D, given as a list of edges [(x0, y0, x1, y2), ...] each. The points are represented by pairs of doubles. I do not know if they are given clockwise, counter-clockwise or in any direction at all. I do know that they are not necessarily convex.
Output: 3 polygons representing A, B and the intersecting polygon AB. Either of which may be an empty (?) polygon, e.g. null.
Hint for optimization: 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!).
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.
EDIT: 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:
Output: 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.
EDIT2: I am currently using the GPC (General Polygon Clipper) library that makes this really easy!
Answer
Arash Partow's FastGEO library contains implementations of many interesting algorithms in computational geometry. Polygon intersection is one of them. It's written in Pascal, but it's only implementing math so it's pretty readable. Note that you will certainly need to preprocess your edges a little, to get them into clockwise or counterclockwise order.
ETA: But really, the best way to do this is to not do this. Find another way to approach your problem that doesn't involve arbitrary polygon intersections.