¿Cómo puedo encontrar el área de superposición entre dos polígonos arbitrarios

Question

Estoy intentando crear un método que se llevará en dos listas arbitrarias de nodos, por un sujeto y un polígono de recorte, y la salida de cualquiera:

a) la zona de la superposición
b) una lista de nodos para la resultante (recortado) polígono de modo que pueda calcular el área

he encontrado muchos ejemplos que clip de un polígono arbitrario usando un rectangular ventana (que es bastante estándar en gráficos) pero eso no es lo que necesito. Entiendo que es bastante complejo, especialmente cuando tienes agujeros, polígonos convexos y similares. La única suposición simplificadora que puedo hacer es que los polígonos arbitrarios no contendrán ningún agujero.

No soy en absoluto un experto en este campo, entonces ¿funcionaría algo así como el algoritmo de Sutherland-Hodgman? ¿Hay alguna biblioteca por ahí que ya lo haga, o es mi mejor opción simplemente implementar el algoritmo como se describe en el pseudo-código en Wikipedia?

¡Gracias por la ayuda!

Answer 1

Encontré que el uso de la biblioteca JavaGeom funcionó muy bien. Integra el código del puerto Java de GPC (que ya no está disponible) y permite operaciones de polígono arbitrarias. Usando SimplePolygon2D y Polygon2DUtils.intersection() pude obtener la operación deseada.

Answer 2

¿Hay bibliotecas por ahí que ya hacen esto ...

recorte polígono es una tarea compleja. No recomendaría intentar hacerlo tú mismo a menos que quieras pasar muchos meses en él. Wikipedia enumera una serie de bibliotecas de recorte (IIRC y en esa lista única Clipper es libre para su uso en aplicaciones comerciales): http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

ps: Reconozco a un prejuicio personal para Clipper ya que soy el autor :) más información aquí: http://angusj.com/delphi/clipper.php

Answer 3

Suena como Weiler-Atherton es el que necesita:

el algoritmo requiere polígonos ser las agujas del reloj y no reentrante (auto de intersección) . El algoritmo puede admitir agujeros (como polígonos en sentido antihorario dentro de su polígono padre ), pero requiere algoritmos adicionales para decidir qué polígonos son agujeros.

Sus polígonos se ajustan a esos criterios, ¿verdad? No sé sobre implementaciones, pero parece que sería mejor implementar W-A que S-H si cualquiera de sus polígonos pudiera ser cóncavo.

Answer 4

Probar gpc.

Answer 5

He intentado muchas bibliotecas diferentes y la que mejor funcionó fue la JTS Topological Suite, que es pura Java y tiene licencia LGPL2.