Difference between revisions of "S2 Relleno de polígonos"
From hpcwiki
Jvictorinog (Talk | contribs) |
Jvictorinog (Talk | contribs) |
||
| Line 1: | Line 1: | ||
==Relleno de polígonos== | ==Relleno de polígonos== | ||
===Polígonos=== | ===Polígonos=== | ||
| − | Definición: Figura plana cerrada, especificada por un conjunto ordenado de 3 o más puntos (vértices) | + | 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=== | ===Clasificación de polígonos=== | ||
| Line 21: | Line 21: | ||
===Algoritmo para identificar polígonos convexos=== | ===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. | + | 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 | # Ubicar el polígono en el plano XY | ||
| − | # Asignar un vector a cada arista siguiendo el | + | # 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 | # 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 | # Extraer el signo de la coordenada Z de los productos vectoriales | ||
# Si todos tienen el mismo signo es convexo sino es cóncavo | # 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=== | ===Algoritmo de barrido de lineas para relleno de polígonos cóncavos=== | ||
| + | |||
===Algoritmo de relleno por contorno e inundación=== | ===Algoritmo de relleno por contorno e inundación=== | ||
| − | |||
Revision as of 23:11, 23 August 2013
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.
