Grafo de visibilitat

Archiu:Grafo de visibilidad.png

Grafo de visibilitat, els nodos representen els vèrtiços i les arestes unixen vèrtiços visibles entre sí

Donat un conjunt d'obstàculs en forma poligonal en el pla euclidiano es diu que el grafo de visibilitat és aquell grafo en el qual cada nodo representa un vèrtiç dels polígons i les arestes són les conexions visibles entre tals vèrtiços. Açò vol dir que per a cada aresta en el grafo de visibilitat definida per $v_1$ i $v_2$, el segment de recta que conecta els vèrtiços corresponents en el pla no es interseca en cap polígon (obstàcul).

Creació del grafo de visibilitat

Archiu:Algoritmo de visibilidad de segmentos con barrido de recta.png

Algoritme de visibilitat de segments utilisant una semirrecta per a processar els vèrtiços en sentit antihorario

L'algoritme CalcularGrafoVisibilidad consistix en recórrer els vèrtiços de tots els polígons i a partir de cada u determinar que vèrtiços són visibles .

Segments visibles des d'un punt

Archiu:Segmentos procesados durante el algoritmo de barrido de recta para visibilidad de segmentos a partir de un punto.png

Quan es processa un segment visible poden existir segments que queden amagats, dits segments poden ser almagasenats en un arbre a fi de conéixer el següent segment visible.

Archiu:Árbol binario algoritmo de visibilidad de segmentos.png

Arbre binario en els segments de recta.

l'algoritme per a determinar que vèrtiços són visibles rep com a entrada un punt i un conjunt de polígons disjuntos els quals són tractats com a segments de recta, cal senyalar que els polígons deuen ser simples ya que en cas contrari els segments de recta es interesectarían entre sí dificultant mantindre el seu estat. L'algoritme VisibleVertices es basa en l'idea d'utilisar una semirrecta d'agranada en orige en el vèrtiç d'entrada i desplaçar-la en l'orde invers de les manetes del rellonge per a processar tots els vèrtiços dels polígons. L'estat dels segments processats s'almagasena en un arbre binario balancejat el qual ajuda a decidir que segment és visible. Per a insertar en l'arbre es pot utilisar el sentit dels segments orientant-los del seu punt inicial al final i recórrer l'arbre verificant si un segment està a l'esquerra o a la dreta d'un atre.

Verificant vèrtiços visibles

En un algoritme com l'anterior que únicament tracte en segments seria suficient en verificar si el segment el vèrtiç del qual està sent processat es interseca en el segment que es troba més a l'esquerra de l'arbre $T$ (el segment més a l'esquerra en l'arbre és el segment visible actualment d'acort a la llínea d'agranada). Degut a que es tracta en polígons es deuen fer atres consideracions, ademés el punt $p$ pertany a un polígon el qual obstaculisa també la llínea de visió del vèrtiç, l'algoritme presentat a continuació únicament pren en conte la segona consideració.

Complexitat

L'algoritme que calcula el grafo de visibilitat processa els $n$ vèrtiços dels polígons d'entrada i per a cada u d'ells eixecuta l'algoritme VerticesVisibles.

L'algoritme VerticesVisibles realisa un preprocesamiento sobre els vèrtiços en ordenar-los la qual cosa es pot realisar en $n\log (n)$.Posteriorment recorre novament els $n$ vèrtiços dels polígons almagasenant i removent cada aresta com a màxim una volta de l'arbre, les operacions insertar, eliminar i obtindre l'element més a l'esquerra prenen $\log (n)$. La verificació de vèrtiç visible pot ser realisada en temps constant.

Per l'ordenament i al processament dels vèrtiços en l'arbre la complexitat de l'algoritme VerticesVisibles és $O(n\log (n))$ i ya que este s'invoca $n$ voltes, llavors la complexitat de l'algoritme CalcularGrafoVisibilidad és $O(n^2\log (n))$.

Extensions

Quan els obstàculs són barres de diferents altures ordenats en una llínea, poden ser entesos com una série temporal. El concepte de grafo de visibilitat s'ampra aixina en la finalitat de representar l'estructura d'una série temporal.