c# polygon intersection

c# - ¿Cómo se cruzan dos polígonos?



polygon intersection (9)

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, dados 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. Sé que no son necesariamente convexos.

Salida : 3 polígonos que representan A, B y el polígono de intersección AB. Cualquiera de los cuales puede ser un polígono vacío (?), Por ejemplo, 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.

EDITAR : Por lo que parece, no soy del todo un gallina para desmayarme ante la perspectiva de hacer esto. Me gustaría volver a exponer el resultado deseado aquí, ya que este es un caso especial y podría simplificar el cálculo:

Salida : primer polígono menos todos los bits que se cortan, polígonos de intersección (el plural está bien). 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 hace esto realmente fácil!

Clipper es una biblioteca de código poligonal freeware de código abierto (escrita en Delphi y C ++) que hace exactamente lo que estás pidiendo: http://sourceforge.net/projects/polyclipping/

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

La biblioteca FastGEO de Arash Partow contiene implementaciones de muchos algoritmos interesantes en geometría computacional. La intersección de polígonos es una de ellas. 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 hacer esto es no hacer esto . Encuentre otra forma de abordar su problema que no implique intersecciones de polígonos arbitrarias.

Si está programando en .NET Framework, es posible que desee echar un vistazo a la clase de SqlGeometry disponible en los ensamblados .NET que se envían como tipos CLR del sistema Microsoft SQL Server.

La clase STIntersection proporciona el método STIntersection

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

También puede echarle un vistazo a NetTopologySuite o incluso intentar importarlo al servidor Sql 2008 y sus herramientas espaciales.

Trate de usar herramientas SIG para eso, como ArcObjects, TopologySuite, GEOS, OGR, etc. No estoy seguro de que todas estas distribuciones estén disponibles para .net, pero todas hacen lo mismo.

Un polígono se describe por completo mediante una lista ordenada 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 encuentra un punto fuera, puede calcular el punto de cruce. Encuentre el borde correspondiente del polígono B y sígalo con roles resersados ​​= ahora verifique 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 solo una idea y tal vez mejores maneras. Si encuentra una solución funcional y probada, le recomendaría que la use ...

narozed

Lo que creo que deberías hacer

No intente hacer esto usted mismo si puede ayudarlo. En su lugar, use uno de los muchos algoritmos de intersección de polígonos disponibles que ya existen.

Estaba considerando seriamente la siguiente base de código por la solidez de su código de demostración y el hecho de que mencionaron su manejo de la mayoría de los casos extraños. Necesitaría donar una cantidad (de usted / la elección de su compañía) 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 realmente hice fue utilizar un algoritmo de intersección de polígonos que es parte de las bibliotecas de Java2D. Posiblemente puedas encontrar algo similar en las propias bibliotecas de C # de MS para usar.

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

Una vez que tenga una biblioteca de recorte de polígonos, solo debe 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 hacer la tuya, para el irremediablemente masoquista

Cuando estaba considerando enrollar el mío, encontré que el algoritmo Weiler-Atherton tiene el mayor potencial para el corte general de polígonos. Usé lo siguiente como referencia:

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

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

Los detalles, como dicen, son demasiado densos para incluirlos aquí, pero no tengo dudas de que podrá encontrar referencias sobre Weiler-Atherton en los próximos años. 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 de polígono querer. Al cambiar la forma en que define y trata los polígonos "entrando" y "saliendo", puede lograr varias intersecciones poligonales posibles (AND, OR, 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.