Un algoritmo simple para la intersección de polígonos.
Estoy buscando un algoritmo muy simple para calcular la intersección/recorte del polígono. Es decir, dados los polígonos P, Qdeseo encontrar el polígono Tque esté contenido en Py en Q, y deseo Tque sea máximo entre todos los polígonos posibles.
No me importa el tiempo de ejecución (tengo algunos polígonos muy pequeños), también puedo darme el lujo de obtener una aproximación de la intersección de los polígonos (es decir, un polígono con menos puntos, pero que todavía está contenido en la intersección de los polígonos). ).
Pero para mí es realmente importante que el algoritmo sea simple (pruebas más baratas) y preferiblemente corto (menos código).
editar: tenga en cuenta que deseo obtener un polígono que represente la intersección. No necesito sólo una respuesta booleana a la pregunta de si los dos polígonos se cruzan.
Entiendo que el cartel original buscaba una solución simple, pero desafortunadamente no existe una solución simple.
Sin embargo, recientemente creé una biblioteca de recorte gratuita de código abierto (escrita en Delphi, C++ y C#) que recorta todo tipo de polígonos (incluidos los que se intersectan solos). Esta biblioteca es bastante sencilla de usar: https://github.com/AngusJohnson/Clipper2
Podrías usar un algoritmo de recorte de polígonos para encontrar la intersección entre dos polígonos. Sin embargo, estos tienden a ser algoritmos complicados cuando se tienen en cuenta todos los casos extremos.
Una implementación de recorte de polígonos que puede buscar con su motor de búsqueda favorito es Weiler-Atherton . artículo de wikipedia sobre Weiler-Atherton
Alan Murta tiene una implementación completa de un GPC recortador de polígonos .
Editar:
Otro enfoque consiste en dividir primero cada polígono en un conjunto de triángulos, que son más fáciles de manejar. El teorema de las dos orejas de Gary H. Meisters funciona. Esta página en McGill hace un buen trabajo al explicar la subdivisión triangular.
Si usa C++ y no desea crear el algoritmo usted mismo, puede usar Boost.Geometry . Utiliza una versión adaptada del algoritmo de Weiler-Atherton mencionado anteriormente.
No nos has dado tu representación de un polígono. Así que elijo (más bien te sugiero) uno para ti :)
Representa cada polígono como un polígono convexo grande y una lista de polígonos convexos más pequeños que deben "restarse" de ese polígono convexo grande.
Ahora, dados dos polígonos en esa representación, puedes calcular la intersección como:
Calcule la intersección de los polígonos convexos grandes para formar el polígono grande de la intersección. Luego 'resta' las intersecciones de todas las más pequeñas de ambos para obtener una lista de polígonos restados.
Obtienes un nuevo polígono siguiendo la misma representación.
Dado que la intersección de polígonos convexos es fácil, este hallazgo de intersección también debería serlo.
Parece que esto debería funcionar, pero no lo he pensado más profundamente en cuanto a la corrección/complejidad temporal/espacial.
Feb 16 '2010 17:02