Cadena poligonal

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Una cadena poligonal simple
Una cadena poligonal que se interseca consigo misma
Una cadena poligonal cerrada

En geometría, una cadena poligonal es una serie conectada de segmentos. Más formalmente, una cadena poligonal P es una curva determinada por una secuencia de puntos , denominados sus vértices. La curva en sí consiste en los segmentos que conectan los vértices consecutivos.

Nombre[editar]

Una cadena poligonal también puede denominarse curva poligonal,[1]trayectoria poligonal,[2]polilínea,[3]curva lineal por partes, línea discontinua [4]​ o, en los sistemas de información geográfica, cadena lineal o anillo lineal.[5]

Variaciones[editar]

Una cadena poligonal simple es aquella en la que solo los segmentos consecutivos (o el primero y el último) se intersecan entre sí y únicamente en sus extremos.

Una cadena poligonal cerrada es aquella en la que el primer vértice coincide con el último o, alternativamente, el primero y el último vértices también están conectados por un segmento.[6]​ Una cadena poligonal cerrada simple en el plano es el límite de un polígono simple. A menudo, el término «polígono» se usa con el significado de «cadena poligonal cerrada», pero en algunos casos es importante establecer una distinción entre un área poligonal y una cadena poligonal.

Una cadena poligonal se llama monótona si hay una línea recta L tal que cada línea perpendicular a L se interseca con la cadena como máximo una vez. Cada cadena poligonal monótona no trivial está abierta. En comparación, un polígono monótono es un polígono (una cadena cerrada) que se puede dividir en exactamente dos cadenas monótonas.[7]​ Las gráficas de funciones lineales por partes forman cadenas monótonas con respecto a una línea horizontal.

Un conjunto de n = 17 puntos tiene una trayectoria poligonal con 4 pendientes del mismo signo.

Propiedades[editar]

Cada conjunto de al menos puntos contiene una trayectoria poligonal de al menos bordes en los que todas las pendientes tienen el mismo signo. Este es un corolario del teorema de Erdős-Szekeres.

Aplicaciones[editar]

Las cadenas poligonales se pueden utilizar a menudo para aproximar curvas más complejas. En este contexto, el algoritmo Ramer-Douglas-Peucker se puede emplear para encontrar una cadena poligonal con pocos segmentos que sirva como una aproximación precisa.[8][9]

En el dibujo de gráficos, las cadenas poligonales se utilizan a menudo para representar los bordes de los gráficos, en estilos de dibujo en los que dibujar los bordes como segmentos rectos provocaría cruces, colisiones borde-vértice u otras características no deseadas. En este contexto, a menudo se desea dibujar bordes con el menor número posible de segmentos y dobleces, para reducir el desorden visual en el dibujo; el problema de minimizar el número de curvas se denomina minimización de curvas.[10]

Las cadenas poligonales también son un tipo de datos fundamental en geometría computacional. Por ejemplo, un algoritmo de ubicación de puntos de Lee y Preparata opera descomponiendo subdivisiones planas arbitrarias en una secuencia ordenada de cadenas monótonas, en las que un problema de consulta de ubicación de puntos puede resolverse mediante una búsqueda binaria; este método se perfeccionó posteriormente para proporcionar límites de tiempo óptimos para el problema de ubicación de puntos.[11]

En los sistemas de información geográfica, las cadenas lineales pueden representar cualquier geometría lineal y pueden describirse empleando el lenguaje de marcado Well Known Text como LineString o MultiLineString.[5]​ Los anillos lineales (o LinearRing) son cadenas poligonales simples y cerradas que se utilizan para construir geometrías poligonales.

Véase también[editar]

Referencias[editar]

  1. Gomes, Jonas; Velho, Luiz; Costa Sousa, Mario (2012), Computer Graphics: Theory and Practice [Gráficos computacionales: Teoría y práctica] (en inglés), CRC Press, p. 186, ISBN 9781568815800 .
  2. Cheney, Ward (2001), Analysis for Applied Mathematics [Análisis para matemáticas aplicadas], Graduate Texts in Mathematics (en inglés) 208, Springer, p. 13, ISBN 9780387952796 ..
  3. Boissonnat, Jean-Daniel; Teillaud, Monique (2006), Effective Computational Geometry for Curves and Surfaces [Geometría computacional efectiva para curvas y superfies] (en inglés), Springer, p. 34, ISBN 9783540332596 ..
  4. Muggeo, Vito M. R. (mayo de 2008), «segmented: An R package to fit regression models with broken-line relationships» [segmentado: Un paquete R para ajustar los modelos de regresión con relaciones de líneas rotas], R News (en inglés) 8 (1): 20-25 .
  5. a b Open Geospatial Consortium (28 de mayo de 2011), Herring, John R., ed., OpenGIS® Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture [Estándar de implementación de OpenGIS® para información geográfica - Acceso simple a las características - Parte 1: Arquitectura común], 1.2.1 (en inglés), Open Geospatial Consortium, consultado el 15 de enero de 2016 .
  6. Mehlhorn, Kurt; Näher, Stefan (1999), LEDA: A Platform for Combinatorial and Geometric Computing [LEDA: Una plataforma para computación geométrica y combinatoria] (en inglés), Cambridge University Press, p. 758, ISBN 9780521563291 ..
  7. O'Rourke, Joseph (1998), Computational Geometry in C [Geometría computacional en C], Cambridge Tracts in Theoretical Computer Science (en inglés), Cambridge University Press, p. 45, ISBN 9780521649766 ..
  8. Ramer, Urs (1972), «An iterative procedure for the polygonal approximation of plane curves» [Un procedimiento iterativo para la aproximación poligonal de curvas planas], Computer Graphics and Image Processing (en inglés) 1 (3): 244-256, doi:10.1016/S0146-664X(72)80017-0 ..
  9. Douglas, David; Peucker, Thomas (1973), «Algorithms for the reduction of the number of points required to represent a digitized line or its caricature» [Algoritmos para la reducción del número de puntos necesarios para representar una línea digitalizada o su caricatura], The Canadian Cartographer (en inglés) 10 (2): 112-122, doi:10.3138/FM57-6770-U75U-7727 ..
  10. Tamassia, Roberto (1987), «On embedding a graph in the grid with the minimum number of bends» [Sobre incrustar un gráfico en la cuadrícula con el número mínimo de curvas], SIAM Journal on Computing (en inglés) 16 (3): 421-444, doi:10.1137/0216030 ..
  11. Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge (1986), «Optimal point location in a monotone subdivision» [Ubicación óptima del punto en una subdivisión monótona], SIAM Journal on Computing (en inglés) 15 (2): 317-340, doi:10.1137/0215023 ..

Enlaces externos[editar]