¿Cómo puedo sumar y restar polígonos convexos?

Tengo dos polígonos convexos 2D superpuestos entre sí . Estoy buscando un algoritmo para restarlos y agregarlos . El resultado debe ser un único polígono cóncavo o (incluso mejor) un conjunto de los convexos más grandes que forman el resultado cóncavo (por ejemplo, triángulos).

( Izquierda: los polígonos superpuestos iniciales. Medio: el polígono cóncavo resultante después de sumar. Derecha: un conjunto de polígonos convexos que forman el resultado cóncavo. Aquí sería mejor obtener polígonos convexos más grandes que un triángulo por razones de rendimiento. dos polígonos superpuestos conducirían a la misma imagen que a la izquierda pero con el área superpuesta que no forma parte del polígono resultante).

¿Cómo puedo hacer esto?

TL; DR Debe implementar operaciones booleanas utilizando árboles BSP.

Bueno, parece que estamos hablando de geometría sólida constructiva aquí. He implementado CSG a nivel comercial, así que sé una o dos cosas al respecto.

El artículo clásico sobre CSG se llama Combinar operaciones de conjuntos poliédricos de rendimientos de árboles BSP , para ser sincero, es demasiado para explicar aquí, pero hablando brevemente, el algoritmo trata con polígonos que se encuentran en el mismo plano que una partición de espacio binario, básicamente construyendo un árbol BSP de cada malla poligonal. El segundo paso es fusionar esos árboles BSP; simplemente toma un árbol e insértalo en el otro. Luego, el algoritmo procede a explicar cómo lidiar con cada nodo de hoja para dividir y restar los nodos, los nodos que no se necesitan en la forma final se eliminarán, otros recibirán el padre apropiado.

¡Pero espera! Ese documento básicamente habla de mallas poligonales y planos 3D, ¿NO?

El algoritmo puede generalizarse en cualquier dimensión, por lo que en su caso 2D es fácil usar segmentos de línea en lugar de planos como particiones binarias. Por lo tanto, cada polígono se convertirá en un árbol BSP que los dos se fusionarán. Finalmente atraviesas el árbol resultante para generar el polígono final,

Tenga en cuenta que este algoritmo y CSG en general no se ocupan de la representación y las caras de malla directamente y realmente no están listas para la representación, por lo que debe extraer las caras de los árboles BSP finales. También encuentro que el trazado de rayos es un enfoque más fácil para representar el resultado CSG, solo necesita los rayos para atravesar el árbol en lugar de extraer y dividir las caras (recuerde que solo tratamos con particiones binarias).

Respecto a la robustez numérica. Es bueno tener en cuenta que hay dos tipos de cálculos geométricos,

• Los que se basan en la construcción, construye una forma basada en el resultado de una operación anterior. Por ejemplo y = sqrt(x)y luego usar yen una nueva operación. Esto se llama construcción; El problema es que los errores numéricos se acumularán rápidamente.
• Alternativamente, hay operaciones que usan predicados en su lugar, esencialmente en lugar de usar construcción, simplemente pregunta si una condición es verdadera / falsa y usa el mismo valor en una operación diferente. Las pruebas clásicas incluyen incircle y la prueba de orientación; Esto también es sospechoso de errores numéricos, especialmente si usa precisión simple o doble, pero generalmente dará resultados mucho mejores. existen otras soluciones que varían en velocidad y precisión. Este es uno de los documentos recientes que evitan la construcción mediante el uso de una geometría basada en el plano para obtener resultados precisos. También citaré del artículo:

Sugihara e Iri [SI89] describieron por primera vez el concepto de representación basada en planos de mallas poligonales. Este tipo de representación proporciona una ventaja importante cuando se trata de tareas que implican cambiar la topología de sólidos representados por mallas como la evaluación de expresiones booleanas: no se debe construir nueva información de geometría primaria para obtener el poliedro resultante

Y finalmente me gustaría agregar, si desea comenzar su implementación de BSP CSG, recomendaría comenzar con las preguntas frecuentes de BSP .

Siguiendo tu ejemplo:

Elija un vértice inicial en el polígono A y luego comience a verificar si hay bordes de intersección en el sentido de las agujas del reloj (o en sentido contrario). Si no hay una intersección, agregue el vértice anterior a su polígono resultante. Si hay una intersección, agregue el punto en el que se intersectaron con su polígono resultante y luego comience a iterar sobre el polígono B, en el mismo orden de enrollamiento. Haga lo mismo, nuevamente cambiando al polígono A si ocurre una intersección.

Una vez que haya acumulado todos los vértices para el nuevo polígono, realice un algoritmo de triangulación en él. El método de recorte del oído es fácil de implementar, pero existen opciones más rápidas.

Importante: asegúrese de que el vértice en el que comienza no esté dentro del otro polígono (consulte este artículo para ver las pruebas de punto en polígonos).

Iterando sobre cada borde, para verificar una intersección sería un algoritmo O (n ^ 2). Puede acelerarlo buscando primero los vértices que están dentro del otro polígono, ya que los bordes vinculados a esos vértices serán los que se cruzan.

Si desea un polígono cóncavo , simplemente elija el borde más cercano entre los dos polígonos de entrada y agregue dos bordes nuevos:

Convexo se vuelve un poco más complicado:

Un enfoque es iterativo porque agrega vértices desde el segundo polígono al primero, uno a la vez, evolucionando el primer polígono en un contenedor que lo abarca todo.

Básicamente:

• Iterar a través de los vértices del segundo polígono.
• Para cada vértice V, itera a través de los bordes del primer polígono:
• Encuentre un "rango" de bordes que estén todos de cara al vértice
• tome el par externo de vértices que definen ese rango y elimine todos los bordes en el rango que los conecta
• Dibuja dos nuevos segmentos desde esos vértices exteriores hasta el nuevo vértice (desde el segundo polígono), asegurándote de que los nuevos bordes estén orientados en la dirección correcta.
• Pase al siguiente vértice del segundo polígono.

Aquí hay un diagrama que ilustra el proceso para el primer vértice:

Un método más rápido es encontrar la lista de bordes en cada polígono que no están frente al otro polígono, eliminar todo lo demás y conectar los puntos finales de las tiras de línea restantes entre sí.

Quizás alguien más pueda intervenir con algunos consejos de resta.