Cómo cortar un polígono simple con una línea

Question

Tengo un polígono simple (convexo o cóncavo, pero sin agujeros) que necesito cortar en partes con un segmento de línea. No estoy seguro de cómo determinar realmente cuántos polígonos resultan después del corte, o cómo agrupar los vértices.

Cajas convexas básicas siempre resultan en 2 subpolígonos fáciles, pero ¿cómo podría lidiar con una forma cóncava complicada? Tome un polígono de forma de "E", por ejemplo. Un corte vertical puede producir 4 polígonos. ¿Cómo puedo determinar qué vértices forman cada uno de esos subpolígonos?

Definición del polígono: Tengo dos opciones aquí. Mi polígono puede ser una lista ordenada de vértices, o puede ser una matriz de triángulos. Preferiría una solución que utiliza la matriz de triángulos. Debería ser bastante fácil recorrer cada triángulo y cortarlo con la línea si se cruzan. Pero luego no tengo idea de cómo agrupar esos triángulos en los sub-polígonos que resultan.

Pseudocódigo o incluso consejo general es bueno; una implementación de C# es ideal.

Answer 1

Hace un tiempo dí this answer a una pregunta algo diferente.

Esa respuesta da una forma de establecer un contorno de una forma, dada una descomposición triangular de esa forma.

La idea básica es considerar los bordes de todos los triángulos como vectores dirigidos, y luego cancelar los bordes iguales pero opuestos.

En su caso, tendría un grupo de triángulos que representan la forma original. Cortarías los triángulos individuales con la línea. Luego reuniría los triángulos en formas usando el método descrito anteriormente, con la condición de que los bordes cortados no se cancelaran.

Hay detalles y fotos en la respuesta mencionada anteriormente. Pero para resumir los pasos serían

1. Realizar el triángulo divide

2. Para cada triángulo resultante, añadir las tres aristas dirigidas a un conjunto. Para determinar el orden en el sentido de las agujas del reloj, consulte the the answers to this question.

3. Go a través del borde establece la eliminación de pares de bordes que son son iguales pero opuestas (a menos que sean bordes rebanada)

4. Recogida una ventaja en el conjunto, a continuación, encontrar el borde cuya cola coincide con la cabeza de la primer borde. Luego repite para ese borde, hasta que llegues al borde inicial. Retire cada borde del conjunto de bordes a medida que lo hace. Cada vez que llegas al borde inicial tienes un circuito cerrado que representa uno de los polígonos resultantes.

5. Realice el paso 4 hasta que no queden bordes.

Todo esto acomoda su deseo de comenzar desde una triangulación de su polígono. Pero como ha señalado uno de los comentaristas de su pregunta original, es posible que desee considerar las alternativas que se brindan al Generate new polygons from a cut polygon (2D).

Answer 2

Tengo este algoritmo en mi biblioteca PolyK. Aquí está the demo. Si entiende Javascript, estoy seguro de que será fácil reescribirlo en su lenguaje de programación.