[RouterGeocoder] Re: My 3rd report on opengraphrouter

[Stephen Woodbridge]

Ashraf Hossain wrote:
> Hi,
> 
> I was thinking about the navigation service and accurate routing and
> got this method(in the link) is the best so far.
> Because we can not allow every point in a polyline feature as vertex.
> If we allow then the size of the graph will be huge.
> So if we think about virtual vertex and virtual edge then the problem
> will be solved.
> The virtual vertex and virtual edges will not be added with the main
> vertex and edge list in the graph.
> This will be calculated locally in the shortest path algorithm functions.
> 
> I will be glad if any one has better idea regarding this.
> 
> The report link is below with 2 attached figure.
> 
> https://sourceforge.net/apps/trac/opengraphrouter/wiki/OpenRouter_Network_builder_report_20090612
> 
> 
> Regards
> Roni


Roni,

Right we do not want to put every polygon node in the graph, only the 
intersections nodes, but we do want to maintain access to the polylines 
for both this kind of edge selection and for post processing the results 
for things like driving directions.

So when you load shapefiles:

1) build a table that relates edges to shape objects from the files or 
copy the shape objects into our own table somewhere.
2) load the shape objects' bbox into the rtree to do the look up you 
describe above
3) build the graph

Later when we get a route request, we look up the possible edges in the 
rtree, and compute the distance to each edge and select the closest edge 
and add the virtual edges that represents the edge split at the point 
projected onto the edge. Do this for the start and end points. Then 
solve the graph.

-Steve