Esto parece no trivial (se pregunta mucho en varios foros), pero necesito esto como un bloque de construcción para un algoritmo más complejo.

Entrada: 2 polígonos (A y B) en 2D, dados como una lista de bordes[(x0, y0, x1, y2), ...] cada. Los puntos están representados por pares dedoubles. No sé si se dan en el sentido de las agujas del reloj, en sentido contrario o en cualquier dirección. yohacer Sepa que no son necesariamente convexos.

Salida: 3 polígonos que representan A, B y el polígono intersecante AB. Cualquiera de los cuales puede ser un polígono vacío (?), P. Ej.null.

Sugerencia para la optimización: Estos polígonos representan límites de habitación y piso. Por lo tanto, el límite de la habitación normalmente se intersectará completamente con el límite del piso, a menos que pertenezca a otro piso en el mismo plano (¡argh!).

Espero que alguien ya haya hecho esto en c # y me permita usar su estrategia / código, ya que lo que he encontrado hasta ahora sobre este problema es bastante desalentador.

EDITAR: Por lo que parece que no estoy del todo desilusionado ante la posibilidad de hacer esto. Me gustaría reiterar la salida deseada aquí, ya que este es un caso especial y podría simplificar el cálculo:

Salida: Primer polígono menos todos los bits de intersección, polígonos de intersección (el plural es correcto). No estoy realmente interesado en el segundo polígono, solo en su intersección con el primero.

EDIT2: Actualmente estoy usando elGPC (General Polygon Clipper) Biblioteca que hace esto realmente fácil!