Gráfico de línea recta plana
En la geometría computacional , un gráfico planar en línea recta , en definitiva PSLG , (o gráfico plano de la línea recta , o de avión en línea recta gráfico ) es un término utilizado para una incrustación de un grafo planar en el plano de tal manera que sus bordes se asignan en segmentos de línea recta. [1] El teorema de Fáry (1948) establece que todo gráfico plano tiene este tipo de incrustación.
En geometría computacional, los PSLG a menudo se denominan subdivisiones planas , con la suposición o afirmación de que las subdivisiones son poligonales en lugar de tener límites curvos.
Los PSLG pueden servir como representaciones de varios mapas , por ejemplo, mapas geográficos en sistemas de información geográfica . [2]
Los casos especiales de PSLG son las triangulaciones ( triangulación de polígonos , triangulación de conjuntos de puntos ). Las triangulaciones de conjuntos de puntos son PSLG máximos en el sentido de que es imposible agregarles bordes rectos mientras se mantiene el gráfico plano. Las triangulaciones tienen numerosas aplicaciones en diversas áreas.
Los PSLG pueden verse como un tipo especial de gráficos euclidianos . Sin embargo, en las discusiones que involucran gráficas euclidianas, el interés principal son sus propiedades métricas, es decir, las distancias entre vértices, mientras que para los PSLG el interés principal son las propiedades topológicas. Para algunos gráficos, como las triangulaciones de Delaunay , son importantes las propiedades métricas y topológicas.
Existen tres estructuras de datos bien conocidas para representar PSLG, estas son la estructura de datos de borde alado , Halfedge y Quadedge . La estructura de datos de borde alado es la más antigua de las tres, pero manipularla a menudo requiere distinciones de casos complicadas. Esto se debe a que las referencias de los bordes no almacenan la dirección del borde y las direcciones de los bordes alrededor de una cara no necesitan ser consistentes. La estructura de datos de medio borde almacena ambas orientaciones de un borde y las vincula correctamente, lo que simplifica las operaciones y el esquema de almacenamiento. La estructura de datos de Quadedge almacena tanto la subdivisión plana como su doble simultáneamente. Sus registros constan explícitamente solo de registros de borde, cuatro para cada borde, y en una forma simplificada es adecuado para almacenar PSLG. [3]
