====== Filling Cellular Spaces with Distances ======

transitivity as a way to fill cellular spaces

  - descobrir o ponto mais proximo
  - descobrir as arestas deste ponto
  - a menor distancia ou é o ponto mais proximo ou é algum ponto destas arestas

um grafo de relacoes da rede armazena a distancia entre todos os pares de pontos. dada a rede, calcular todas as relacoes de proximidade entre todos os vertices. note que para uma rede de distancias, as conexoes sao sempre maiores ou iguais a zero, e portanto existem algoritmos eficientes para isto. armazenar a matriz com as relacoes da rede no banco, permitindo que a GPM seja executada várias vezes sem repetir a construção deste grafo.

dado o grafo representando a rede e um espaço celular:
  * **closed network:** solução é uma consulta a (i,j), onde i é o ponto de entrada e j é o ponto de saída
  * **open network:** precisa das geometrias apenas para encontrar os pontos de entrada e de saída da rede. Depois basta usar a estratégia abaixo.

{{  http://www.leg.ufpr.br/~pedro/figures/dist-rede-aberta.jpg?270  }}

dist = min(a+dist(A,C)+c, a+dist(A,D)+d, b+dist(B,C)+c, b+dist(B,D)+d)