Cadena poligonal

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

Cada segmento de una cadena poligonal se parametriza típicamente de forma lineal, mediante interpolación lineal entre vértices sucesivos. Para la cadena completa, son comunes dos parametrizaciones en aplicaciones prácticas: a cada segmento se le puede asignar un intervalo unitario del parámetro correspondiente al índice del primer vértice; alternativamente, a cada segmento 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.

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

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

En el dibujo de grafos , las cadenas poligonales se utilizan a menudo para representar las aristas, en estilos de dibujo donde dibujar las aristas como segmentos de línea recta provocaría cruces, colisiones entre aristas y vértices u otras características indeseadas. En este contexto, suele ser deseable dibujar las aristas con la menor cantidad posible de segmentos y curvas, para reducir la complejidad visual del dibujo; el problema de minimizar el número de curvas se denomina minimización de curvas . ^{[ 5 ]}

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 . Al conectarse entre sí, los puntos de control forman una cadena poligonal denominada polígono de control .

Las cadenas poligonales también constituyen un tipo de dato 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 la que un problema de consulta de localización de puntos puede resolverse mediante búsqueda binaria ; este método se perfeccionó posteriormente para obtener 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 conocido marcado de texto como LineStringo MultiLineString. ^{[ 7 ]} Los anillos lineales (o LinearRing) son cadenas poligonales cerradas y simples que se utilizan para construir geometrías poligonales.

• Cadena (topología algebraica) , una combinación formal de símplices que en el caso unidimensional incluye cadenas poligonales.
• Curva de Bézier compuesta , una 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
• Camino (teoría de grafos) , un concepto análogo en grafos abstractos.
• Terreno poliédrico , una generalización 3D de una cadena poligonal monótona
• Spirangle , 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