En geometría , una cadena poligonal [a] es una serie conectada de segmentos de línea . Más formalmente, una cadena poligonal es 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.
Una cadena poligonal simple es aquella en la que sólo se intersecan segmentos consecutivos y sólo en sus puntos finales.
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 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.
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.
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 .
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]
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.
