Cadena poligonal

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 $\scriptstyle (A_{1},A_{2},\dots ,A_{n})$, denominados sus vértices. La curva en sí consiste en los segmentos que conectan los vértices consecutivos.

Nombre

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

Variaciones

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.​ 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.​ 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

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

Aplicaciones

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.​​

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.​

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.​

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.​ Los anillos lineales (o LinearRing) son cadenas poligonales simples y cerradas que se utilizan para construir geometrías poligonales.

Véase también

• Curva compuesta de Bézier, una generalización que reemplaza cada línea recta de una cadena poligonal por una curva suave
• Regresión por partes
• Camino (teoría de grafos), un concepto análogo en grafos abstractos

Enlaces externos

• Datos: Q633674