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

Question

I tiene un polígono sencillo (convexo o cóncavo, pero sin agujeros) que necesito cortar en piezas con un segmento de línea. No estoy seguro de cómo determinar realmente cuántos polígonos resultado después de la rebanada, o cómo agrupar los vértices.

Básico convexa casos los resultados siempre en 2 sub-polígonos son fáciles, pero ¿cómo iba a lidiar con una forma cóncava complicado? Tome una "E" una forma poligonal, por ejemplo. Una rebanada vertical puede dar 4 polígonos. ¿Cómo puedo determinar qué vértices conforman cada uno de los sub-polígonos?

La definición del polígono: Tengo dos opciones aquí. Mi polígono puede ser una lista ordenada de vértices, o puede ser un conjunto de triángulos. Yo preferiría una solución que utiliza el conjunto de triángulos. Debe ser bastante fácil de bucle a través de cada triángulo y cortarlo con la línea si se intersecan. Pero entonces no tengo idea de cómo agrupar los triángulos en la subcategoría polígonos ese resultado.

Pseudo-código o incluso consejo general es buena; una aplicación de C # es ideal.

Answer 1

Hace un tiempo me dio esta respuesta a una pregunta un tanto diferente.

Esa respuesta le da una forma de establecer un esquema 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 bordes iguales pero opuestas.

En su caso, usted tendría un montón de triángulos representan la forma original. Se podría cortar los triángulos individuales con la línea. A continuación, reunirá a los triángulos en formas utilizando el método descrito anteriormente, con la condición de que los bordes en rodajas no cancelarían.

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

1. realizar las fracturas triángulo

2. Para cada triángulo resultante, añadir los tres bordes dirigidos a un conjunto. Para determinar el orden de las agujas del reloj, visita las respuestas a esta pregunta .

3. pasar por el borde conjunto eliminación de pares de bordes que se están igual pero opuesta (a menos que sean bordes rebanada)

4. Escoja una ventaja en el set, y luego encontrar el borde cuya cola coincide con el jefe del primer borde. A continuación, repita para ese borde, hasta llegar al borde principio. Retire cada borde del borde conjunto como se llega a él. Siempre que reciba al borde principio tiene un circuito cerrado que representa uno de los polígonos de resultados.

5. realizar el paso 4 hasta que no hay bordes izquierdos.

Todo esto se ajuste a su deseo de comenzar a partir de una triangulación de su polígono. Pero como uno de los comentaristas a su pregunta original ha señalado, es posible que desee considerar las alternativas dadas a Crear nuevo polígonos de un polígono de corte (2D) .

Answer 2

Tengo este algoritmo en mi biblioteca PolyK . Aquí es la demo . Si usted entiende Javascript, estoy seguro de que será fácil volver a escribir en el lenguaje de programación.