S2 Relleno de polígonos
From hpcwiki
Contents |
Relleno de polígonos
Polígonos
Definición: Figura plana cerrada, especificada por un conjunto ordenado de 3 o más puntos (vértices) conectados en secuencia mediante lineas rectas (aristas).
Clasificación de polígonos
- Convexo: Si todos los ángulos interiores del polígono son menores a 180° se dice que el polígono es convexo. Alternativamente cuando es convexo cualquier línea construida a partir de dos puntos que pertenecen al área del polígono esta completamente contenida en este. De la misma forma la extensión infinita de cualquiera de sus aristas no atravisa el área del polígono.
- Cóncavo: si no es convexo es cóncavo.
- Degenerado: cuando los vértices son co-lineales o en el que algunos de sus vértices coinciden
Según la forma de su contorno otras definiciones de polígono son:
- Simple: si ninguna de sus aristas se corta.
- Complejo: si dos de sus aristas no consecutivas se intersecan.
- Equilátero: si tiene todos sus lados iguales.
- Equiángulo: si tiene todos sus ángulos iguales.
- Regular: si es equilátero y equiángulo a la vez.
- Irregular: si tiene sus ángulos y lados desiguales.
- Ortogonal o isotético: si todos sus lados son paralelos a los ejes cartesianos
- Alabeado: si sus lados no están en el mismo plano.
- Estrellado, si se construye a partir de trazar diagonales en polígonos regulares. Se obtienen diferentes construcciones dependiendo de la unión de los vértices: de dos en dos, de tres en tres, etc.
Algoritmo para identificar polígonos convexos
Un polígono convexo tiene todos sus ángulos interiores menores a 180°. Si alguno de los ángulos no cumple esta condición es cóncavo. Usando una propiedad del producto vectorial se contruye el algoritmo para identificar el tipo de polígono.
- Ubicar el polígono en el plano XY
- Asignar un vector a cada arista siguiendo el orden del perímetro del polígono
- Entre cada par de aristas consecutivas hacer el producto vectorial con los vectores asignados
- Extraer el signo de la coordenada Z de los productos vectoriales
- Si todos tienen el mismo signo es convexo sino es cóncavo
Dividir un polígono cóncavo en varios convexos
El algoritmo anterior se puede extender para dividir polígonos cóncavos en varios convexos, usando los puntos en los que el signo es diferente. Cuando es cóncavo la extensión de una arista que forma un ángulo mayor a 180° atraviesa alguna de las aristas del polígono. Por lo que se debe buscar con cada una de las aristas del polígono el punto de intersección. Este punto parte la arista en dos de la cual se forman dos nuevos polígonos a los que se aplica de manera iterativa este proceso hasta que todos los polígonos sean convexos.
Algoritmo de barrido de lineas para relleno de polígonos cóncavos
Se asumen polígonos simples que se cierran cuando el último punto coincide con el primero. Antes de especificar los pasos del algoritmo las estructuras a usar son las siguientes:
- Vector de valores que representan los puntos del polígono
- Estructura punto 2D, que actúa sobre el vector agrupando dos valores.
- Estructura arista, que actúa sobre puntos agrupando dos puntos y cuatro valores.
- Generar aristas omitiendo las horizontales
- Pre-procesar aristas - desplazando un punto
- Aplicar Barrido horizontal de líneas
- Crear un vector con las intersecciones de aristas con un nivel horizontal
- Ordenar vector
- Pinta lineas entre pares de puntos
