[RouterGeocoder] Re: My 3rd report on opengraphrouter

[Ashraf Hossain]

Thanks steve,
I am building this and I will let you know when I will update
something this week.

I will send you another mail tomorrow about my 2.5 months works.

Roni


On Sat, Jun 13, 2009 at 11:39 PM, Stephen
Woodbridge<woodbri at swoodbridge.com> wrote:
> 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
>