Grafo de visibilidad

Dado un conjunto de obstáculos con forma poligonal en el plano euclidiano se dice que el grafo de visibilidad es aquel grafo en el cual cada nodo representa un vértice de los polígonos y las aristas son las conexiones visibles entre tales vértices. Esto quiere decir que para cada arista en el grafo de visibilidad definida por $v_{1}$ y $v_{2}$ , el segmento de recta que conecta los vértices correspondientes en el plano no se interseca con ningún polígono (obstáculo).^[1]

Creación del grafo de visibilidad editar

Algoritmo de visibilidad de segmentos utilizando una semirrecta para procesar los vértices en sentido antihorario

El algoritmo CalcularGrafoVisibilidad consiste en recorrer los vértices de todos los polígonos y a partir de cada uno determinar que vértices son visibles^[2] .

Algoritmo CalcularGrafoVisibilidad(S)
// $S$ Conjunto de polígonos disjuntos $G$ ← $\emptyset$ // Crear un grafo vacío $G.vertices$ ← $S.vertices$ // Todos los vértices de los polígonos se agregan como nodos for $v_{i}$ in $G.vertices$ $W$ ← $VisibleVertices(v_{i},S)$ for $w_{i}$ in $W$ $G.addEdge(v_{i},w_{i})$ // Se generan aristas con todos los vértices visibes return $G$

Segmentos visibles desde un punto editar

Cuando se procesa un segmento visible pueden existir segmentos que queden ocultos, dichos segmentos pueden ser almacenados en un árbol a fin de conocer el siguiente segmento visible.

Árbol binario con los segmentos de recta.

El algoritmo para determinar que vértices son visibles recibe como entrada un punto y un conjunto de polígonos disjuntos los cuales son tratados como segmentos de recta, cabe señalar que los polígonos deben ser simples ya que en caso contrario los segmentos de recta se interesectarían entre sí dificultando mantener su estado. El algoritmo VisibleVertices se basa en la idea de utilizar una semirrecta de barrido con origen en el vértice de entrada y desplazarla en el orden inverso de las manecillas del reloj para procesar todos los vértices de los polígonos. El estado de los segmentos procesados se almacena en un árbol binario balanceado el cual ayuda a decidir que segmento es visible. Para insertar en el árbol se puede utilizar el sentido de los segmentos orientándolos de su punto inicial al final y recorrer el árbol verificando si un segmento está a la izquierda o a la derecha de otro.

Algoritmo VisibleVertices(S,p)
// $S$ Conjunto de polígonos disjuntos // $p$ Punto de referencia que no está dentro de algún polígono $V$ ← Ordenar los vértices de los polígonos en sentido antihorario con respecto al punto $p$ y una semirrecta de pendiente 0. $T$ ← $\emptyset$ // Árbol balanceado donde se almacenarán los segmentos $VerticesVisibles$ ← $\emptyset$ // lista con los vértices visibles Insertar en $T$ todos los segmentos que se intersequen con la semirrecta de origen p y pendiente 0. segmentoVisible ← Obtener el elemento más a la izquierda de $T$ for $v_{i}$ in $V$ if $Visible(p,v_{i},segmentoVisible)$ Agregar $v_{i}$ a $VerticesVisibles$ $l$ ← semirrecta que tiene origen en $p$ y pasa por $v_{i}$ Insertar en $T$ las aristas incidentes en $v_{i}$ que se encuentren del lado izquierdo de $l$ // Aquellas que se encuentran en el sentido de barrido de la recta Eliminar de $T$ las aristas que se encuentran del lado derecho de $l$ // Aquellas que ya han sido procesadas segmentoVisible ← Obtener el elemento más a la izquierda de $T$ return $VerticesVisibles$

Verificando vértices visibles editar

En un algoritmo como el anterior que únicamente trate con segmentos sería suficiente con verificar si el segmento cuyo vértice está siendo procesado se interseca con el segmento que se encuentra más a la izquierda del árbol $T$ (el segmento más a la izquierda en el árbol es el segmento visible actualmente de acuerdo a la línea de barrido). Debido a que se trata con polígonos se deben hacer otras consideraciones, además el punto $p$ pertenece a un polígono el cual obstaculiza también la línea de visión del vértice, el algoritmo presentado a continuación únicamente toma en cuenta la segunda consideración.

Algoritmo Visible( $p,v_{i},segmentoVisible$ )
// $v_{i}$ Vértice de un polígono // $p$ Punto de referencia // $segmentoVisible$ Segmento de recta que es visible en la posición actual de la semirrecta de barrido if el segmento ${\overline {pv_{i}}}$ interesecta el polígono al cual pertenece $p$ return false if el segmento ${\overline {pv_{i}}}$ interesecta al segmento visible return false else return true

Complejidad editar

El algoritmo que calcula el grafo de visibilidad procesa los $n$ vértices de los polígonos de entrada y para cada uno de ellos ejecuta el algoritmo VerticesVisibles.

El algoritmo VerticesVisibles realiza un preprocesamiento sobre los vértices al ordenarlos lo cual se puede realizar en $n\log(n)$ .Posteriormente recorre nuevamente los $n$ vértices de los polígonos almacenando y removiendo cada arista como máximo una vez del árbol, las operaciones insertar, eliminar y obtener el elemento más a la izquierda toman $\log(n)$ . La verificación de vértice visible puede ser realizada en tiempo constante.

Debido al ordenamiento y al procesamiento de los vértices con el árbol la complejidad del algoritmo VerticesVisibles es $O(n\log(n))$ y ya que este se invoca $n$ veces, entonces la complejidad del algoritmo CalcularGrafoVisibilidad es $O(n^{2}\log(n))$ .

Extensiones editar

Cuando los obstáculos son barras de diferentes alturas ordenados en una línea, pueden ser entendidos como una serie temporal. El concepto de grafo de visibilidad se emplea así con el fin de representar la estructura de una serie temporal.^[3]

Referencias editar

↑ O'Rourke, Joseph (1998). Computational Geometry in C (en inglés). Cambridge, UK: Cambridge University Press.
↑ de Berg, Mark (2000). Computational geometry (en inglés). Berlin: Springer.
↑ «Lacasa et al., From time series to complex networks: the visibility graph, PNAS 105, 13 (2008)».

Datos: Q8216024

[1] O'Rourke, Joseph (1998). Computational Geometry in C (en inglés). Cambridge, UK: Cambridge University Press.

[deBerg-2] Berg, Mark (2000). Computational geometry (en inglés). Berlin: Springer.

[3] «Lacasa et al., From time series to complex networks: the visibility graph, PNAS 105, 13 (2008)».

[1]

[2]

[3]