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 vértices . La curva en sí consta de segmentos de línea que conectan los vértices consecutivos.
Una cadena poligonal simple es aquella en la que sólo se cruzan 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 recta. [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 distinguir 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 corta la cadena como máximo una vez. Toda cadena poligonal monótona y 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. [2] Las gráficas de funciones lineales por tramos forman cadenas monótonas con respecto a una línea horizontal.
Cada segmento de una cadena poligonal suele parametrizarse linealmente, 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 del arco a lo largo de toda la cadena.
Cada conjunto de al menos puntos contiene un camino poligonal de al menos aristas en el que todas las pendientes tienen el mismo signo. Este es un corolario del teorema de Erdős-Szekeres .
Las cadenas poligonales a menudo se pueden utilizar para aproximar curvas más complejas. En este contexto, el algoritmo de Ramer-Douglas-Peucker se puede utilizar para encontrar una cadena poligonal con pocos segmentos que sirva como una 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 causaría cruces, colisiones entre bordes y vértices u otras características no deseadas. En este contexto, a menudo se desea dibujar bordes con el menor número posible de segmentos y curvaturas, para reducir el desorden visual en el dibujo; El problema de minimizar el número de curvas se llama 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 llamada polígono de control .
Las cadenas poligonales también son un tipo de datos fundamental en geometría computacional . Por ejemplo, un algoritmo de localizació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 localización de puntos puede resolverse mediante búsqueda binaria ; Este método se perfeccionó posteriormente para proporcionar límites de tiempo óptimos para el problema de ubicació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.
