Filling Cellular Spaces with Distances

transitivity as a way to fill cellular spaces

1. descobrir o ponto mais proximo
2. descobrir as arestas deste ponto
3. 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.

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