finding routes in the "outside" world

[vkulikov@mit.edu]

>>3. We'll handle multibuilding routes (provisionally) by having some 
>>portals connect to the "outside world". A route from NE43 to 37 will look 
>>like NE43->OUTSIDE_WORLD->37.  We need to talk to Vitaly about more 
>>intelligent ways of including his basemap work in this effort.

I currently see two aspects of connecting building portals to the “outside 
world”. First, all the portals that lead outside must be mapped to a set of 
basemap locations. The mapping has to do a lot with the task of orienting 
generated building models at the basemap. We have talked with Mike about this 
and come to the conclusion that while placing buildings 100%-precisely is a 
difficult problem – the base of the model is likely to be somewhat different 
from the corresponding building space on the basemap – placing the buildings 
with some small degree of error should not be difficult. Once all buildings 
are properly placed and oriented at the basemap, the mapping of portals to 
basemap locations will be easy.

Second, the basemap should support the operation of finding a valid and 
reasonably short way from one basemap location to another. Then, by 
incorporating the route from some source office A to the source outside portal 
with the route from the source outside portal to a destination outside portal, 
and the route from the destination outside portal to the destination, we will 
have the complete route from one office to another. There are at least two 
ways to approach the problem of finding a reasonably short route from one 
basemap location to another. One way is to simply use Dijkstra algorithm on 
the graph formed by sidewalk-colored triangles. Another, a more intelligent 
way, is to choose a set of locations on the basemap, precompute paths among 
them, and then run the path-finding algorithm to find the sequence of 
locations from source to destination. Given that there is a comparatively 
small number of outside portals, the second approach should work really well.

I have modified the code so that I can now have several graph layers defined 
on the basemap. For instance, at the bottom layer I have a graph of all 
adjacent triangles on the basemap; at the layer above, I have a graph of all 
adjacent patches; finally, at the topmost layer, I can have a graph of 
connected basemap locations used to find the shortest path from some source to 
destination. I am currently working to make my coloring program robust enough 
to color the whole basemap. As soon as I have the basemap colored, I can 
implement the outside part of the path-searching algorithm. Please let me know 
if you have some thoughts/suggestions.

Vitaly