¿Cómo se cruzan dos polígonos?

Question

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

Entrada: 2 polígonos (A y B) en 2D, como una lista de bordes [(x0, y0, x1, y2), ...] cada uno. Los puntos están representados por pares de double s. No sé si se dan en sentido horario, en sentido antihorario o en cualquier dirección. I do saben que no son necesariamente convexos.

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

Sugerencia para la optimización: Estos polígonos representan los límites de la sala y el piso. Por lo tanto, el límite de la habitación normalmente se intersectará por completo 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.

EDIT: Parece que no estoy del todo de pollo por estar débil ante la perspectiva de hacer esto. Me gustaría repetir la salida deseada aquí, ya que este es un caso especial y podría hacer el cálculo más simple:

de salida: En primer polígono menos todos los bits que se cruzan, los polígonos de intersección (plural es aceptable). No estoy realmente interesado en el segundo polígono, solo su intersección con el primero.

EDIT2: ¡Actualmente estoy usando la biblioteca GPC (General Polygon Clipper) que lo hace realmente fácil!

Answer 1

lo que creo que debe hacer

No intente hacerlo usted mismo si puedes evitarlo. En su lugar, use uno de los muchos algoritmos de intersección de polígonos disponibles que ya existen.

Estaba considerando la siguiente base de código por la fuerza de su código de demostración y el hecho de que mencionaron el manejo de la mayoría de los casos extraños. Debería donar una cantidad (de su elección o la de su empresa) si la usa comercialmente, pero vale la pena obtener una versión sólida de este tipo de código.

http://www.cs.man.ac.uk/~toby/gpc/

Lo que en realidad hizo fue utilizar un algoritmo de polígono-intersección que forma parte de las bibliotecas Java2D. Posiblemente pueda encontrar algo similar en las bibliotecas de C# de MS para usar.

También hay otras opciones disponibles; busque "clipper de polígono" o "recorte de polígono", ya que los mismos algoritmos básicos que manejan la intersección de polígono también tienden a ser utilizables para los casos de recorte general.

Una vez que realmente tiene una biblioteca de recorte de polígono, solo necesita restar el polígono B del polígono A para obtener su primera pieza de salida, e intersecar los polígonos A y B para obtener su segunda pieza de salida.

cómo rodar su propio, para el masoquista irremediablemente

Cuando yo estaba considerando rodar mi cuenta, me encontré con el algoritmo de Weiler-Atherton a tener el mayor potencial para el polígono de corte general. He utilizado el siguiente como referencia:

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/Weiler-Atherton

Los detalles, como se dice, son demasiado densos para incluir aquí, pero no tengo ninguna duda de que usted será capaz de encontrar referencias en Weiler-Atherton en los años venideros. Esencialmente, divide todos los puntos en aquellos que ingresan al polígono final o salen del polígono final, luego forma un gráfico de todos los puntos y luego recorre el gráfico en las direcciones apropiadas para extraer todas las piezas poligonales que querer. Al cambiar la forma en que define y trata los polígonos "entrando" y "saliendo", puede lograr varias intersecciones poligonales posibles (Y, O, XOR, etc.).

En realidad es bastante implementable, pero al igual que con cualquier código de geometría computacional, el diablo está en las degeneraciones.

Answer 2

La biblioteca FastGEO de Arash Partow contiene implementaciones de muchos algoritmos interesantes en geometría computacional. La intersección de polígonos es uno de ellos. Está escrito en Pascal, pero solo está implementando las matemáticas, por lo que es bastante legible. Tenga en cuenta que sin duda necesitará preprocesar sus bordes un poco, para que entren en sentido horario o antihorario.

ETA: Pero realmente, la mejor manera de hacerlo es no hacer esto. Encuentre otra forma de abordar su problema que no implique intersecciones de polígonos arbitrarias.

Answer 3

Es posible que también desee echarle un vistazo al NetTopologySuite o incluso intentar importarlo al servidor Sql 2008 & sus herramientas espaciales.

Answer 4

Si se atreve a echar un vistazo al código de otras personas GPL C++, se puede ver cómo lo hacen en Inkscape:

http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (línea 126)

Answer 5

Un polígono está totalmente descrito por un pedido lista de puntos (P1, P2, ..., Pn). Los bordes son (P1 - P2), (P2 - P3), ..., (Pn - P1). Si tiene dos polígonos A y B que se superponen, habrá un punto An (de la lista de puntos que describe el polígono A) que se encuentra dentro del área rodeada por el polígono B o viceversa (un punto de B se encuentra en A). Si no se encuentra tal punto, entonces los polígonos no se superponen. Si se encuentra dicho punto (es decir, Ai), compruebe los puntos adyacentes del polígono A (i-1) y A (i + 1). Repita hasta que encuentre un punto fuera del área o se verifiquen todos los puntos (entonces el primer polígono se encuentra completamente dentro del segundo polígono). Si encontró un punto afuera, entonces puede calcular el punto de cruce. Encuentre el borde correspondiente del polígono B y sígalo con roles compartidos = ahora compruebe si los puntos del polígono B se encuentran dentro del polígono A. De esta manera puede construir una lista de puntos que describan el polígono superpuesto. Si es necesario, debe verificar si los polígonos son idénticos, (P1, P2, P3) === (P2, P3, P1).

Esto es sólo una idea y tal vez hay mejores formas. Si encuentra un trabajo y solución probada que te recomiendo que lo usa ...

narozed

Answer 6

intenta utilizar herramientas SIG para que, como ArcObjects, TopologySuite, GEOS, OGR, etc.No estoy seguro de si todas estas distribuciones están disponibles para .net, pero todas hacen lo mismo.

Answer 7

Si está programando en .NET Framework, es posible que desee echar un vistazo a la clase SqlGeometry disponible en NET transportado de manera que Microsoft SQL Server System CLR Types

La clase SqlGeometry ofrece STIntersection método

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))"); 
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))"); 
SqlGeometry intersection = g1.STIntersection(g2); 

Answer 8

Clipper es un freeware de código abierto biblioteca de recorte de polígonos (escrita en Delphi y C++) que hace exactamente lo que está pidiendo - http://sourceforge.net/projects/polyclipping/

En mi prueba, Clipper es mucho más rápido y menos propenso a errores que GPC (ver comparaciones más detalladas aquí - http://www.angusj.com/delphi/clipper.php#features). Además, aunque hay código fuente para Delphi y C++, la biblioteca de Clipper también incluye una DLL compilada para que sea muy fácil usar las funciones de recorte en otros idiomas (Windows) también.

Answer 9

Este academic paper explica cómo hacerlo.