Cadena poligonal

Serie conectada de segmentos de línea

Una cadena poligonal simple

Una cadena poligonal que se autointersecta

Una cadena poligonal cerrada

En geometría , una cadena poligonal ^[a] es una serie conectada de segmentos de línea . Más formalmente, una cadena poligonal es ${\displaystyle P}$ una curva especificada por una secuencia de puntos llamados sus vértices . La curva en sí consiste en los segmentos de línea que conectan los vértices consecutivos. ${\displaystyle (A_{1},A_{2},\dots ,A_{n})}$

Variaciones

Simple

Una cadena poligonal simple es aquella en la que sólo se intersecan segmentos consecutivos y sólo en sus puntos finales.

Cerrado

Una cadena poligonal cerrada es aquella en la que el primer vértice coincide con el último, o, alternativamente, el primer y el último vértice también están conectados por un segmento de línea. ^[1] 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 utiliza 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 cerrada en el espacio también se conoce como un "polígono" oblicuo .

Monótono

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

Una cadena poligonal se denomina monótona si existe una línea recta L tal que cada línea perpendicular a L interseca la cadena como máximo una vez. Toda cadena poligonal monótona no trivial es 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. ^[2] Los gráficos de funciones lineales por partes forman cadenas monótonas con respecto a una línea horizontal.

Parametrización

Cada segmento de una cadena poligonal se parametriza típicamente de forma lineal, utilizando interpolación lineal entre vértices sucesivos. Para toda la cadena, dos parametrizaciones son comunes en aplicaciones prácticas: a cada segmento de la cadena se le puede asignar un intervalo unitario del parámetro correspondiente al índice del primer vértice; alternativamente, a cada segmento de la cadena se le puede asignar un intervalo del parámetro correspondiente a la longitud del segmento, de modo que el parámetro corresponda uniformemente a la longitud de arco a lo largo de toda la cadena.

A partir de conjuntos de puntos

Todo conjunto de al menos puntos contiene una trayectoria poligonal de al menos aristas en la que todas las pendientes tienen el mismo signo. Este es un corolario del teorema de Erdős–Szekeres . ${\displaystyle n}$ ${\displaystyle \lfloor {\sqrt {n-1}}\rfloor }$

Aplicaciones

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

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 de línea recta provocaría cruces, colisiones entre bordes y vértices u otras características no deseadas. En este contexto, a menudo se desea dibujar bordes con la menor cantidad posible de segmentos y curvas, para reducir el desorden visual en el dibujo; el problema de minimizar el número de curvas se denomina minimización de curvas . ^[5]

Una curva de Bézier roja está definida por los puntos de control P ₀ , ...,  P ₄ . La cadena poligonal gris que conecta los puntos de control se denomina polígono de control.

En el diseño geométrico asistido por ordenador , las curvas suaves suelen definirse mediante una lista de puntos de control , por ejemplo, al definir segmentos de curvas de Bézier . Cuando se conectan entre sí, los puntos de control forman una cadena poligonal denominada polígono de control .

Las cadenas poligonales también son un tipo de datos fundamental en la geometría computacional . Por ejemplo, un algoritmo de localización de puntos de Lee y Preparata funciona descomponiendo subdivisiones planas arbitrarias en una secuencia ordenada de cadenas monótonas, en las que un problema de consulta de localizació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 localización de puntos. ^[6]

Con el sistema de información geográfica , las cadenas de líneas pueden representar cualquier geometría lineal y pueden describirse utilizando el marcado de texto conocido como LineStringo MultiLineString. ^[7] Los anillos lineales (o LinearRing) son cadenas poligonales cerradas y simples que se utilizan para construir geometrías poligonales.

Véase también

• Cadena (topología algebraica) , una combinación formal de símplices que en el caso unidimensional incluye cadenas poligonales.
• Curva de Bézier compuesta , generalización que reemplaza cada línea recta de una cadena poligonal con una curva suave.
• Distancia de enlace , el número de segmentos de la cadena más corta que une dos puntos dentro de un polígono
• Regresión por partes
• Trayectoria (teoría de grafos) , un concepto análogo en grafos abstractos
• Terreno poliédrico , una generalización 3D de una cadena poligonal monótona
• Espiral , una cadena poligonal en espiral
• Número de palo , un invariante de nudo basado en la representación de un nudo como una cadena poligonal cerrada
• Travesía , aplicación en topografía

Notas

1. Una cadena poligonal también puede denominarse curva poligonal , ^[8] trayectoria poligonal , ^[9] polilínea , ^[10] curva lineal por partes , ^[10] línea discontinua ^[11] o, en sistemas de información geográfica , cadena de líneas o anillo lineal . ^[7]

Referencias

1. Mehlhorn, Kurt ; Näher, Stefan (1999), LEDA: una plataforma para computación combinatoria y geométrica, Cambridge University Press, pág. 758, ISBN 9780521563291.
2. O'Rourke, Joseph (1998), Geometría computacional en C, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, pág. 45, ISBN 9780521649766.
3. Ramer, Urs (1972), "Un procedimiento iterativo para la aproximación poligonal de curvas planas", Computer Graphics and Image Processing , 1 (3): 244–256, doi :10.1016/S0146-664X(72)80017-0.
4. Douglas, David; Peucker, Thomas (1973), "Algoritmos para la reducción del número de puntos necesarios para representar una línea digitalizada o su caricatura", The Canadian Cartographer , 10 (2): 112–122, doi :10.3138/FM57-6770-U75U-7727.
5. Tamassia, Roberto (1987), "Sobre la incrustación de un gráfico en la cuadrícula con el mínimo número de curvas", SIAM Journal on Computing , 16 (3): 421–444, doi :10.1137/0216030.
6. Edelsbrunner, Herbert ; Guibas, Leonidas J. ; Stolfi, Jorge (1986), "Ubicación óptima de puntos en una subdivisión monótona", SIAM Journal on Computing , 15 (2): 317–340, doi :10.1137/0215023.
7. Open Geospatial Consortium (2011-05-28), Herring, John R. (ed.), Estándar de implementación OpenGIS® para información geográfica - Acceso simple a características - Parte 1: Arquitectura común, 1.2.1, Open Geospatial Consortium , consultado el 15 de enero de 2016
8. Gómez, Jonás; Velho, Luis; Costa Sousa, Mario (2012), Gráficos por computadora: teoría y práctica, CRC Press, p. 186, ISBN 9781568815800.
9. Cheney, Ward (2001), Análisis para matemáticas aplicadas, Textos de posgrado en matemáticas, vol. 208, Springer, pág. 13, ISBN 9780387952796.
10. Boissonnat, Jean-Daniel; Teillaud, Monique (2006), Geometría computacional efectiva para curvas y superficies, Springer, pág. 34, ISBN 9783540332596.
11. Muggeo, Vito MR (mayo de 2008), "segmentado: Un paquete R para ajustar modelos de regresión con relaciones de línea discontinua" (PDF) , R News , 8 (1): 20–25