Finding the shortest path through open spaces is a well-known challenge for pedestrian routing engines.A common solution is routing on the open space boundary,which causes in most cases an unnecessarily long route.A p...Finding the shortest path through open spaces is a well-known challenge for pedestrian routing engines.A common solution is routing on the open space boundary,which causes in most cases an unnecessarily long route.A possible alternative is to create a subgraph within the open space.This paper assesses this approach and investigates its implications for routing engines.A number of algorithms(Grid,Spider-Grid,Visibility,Delaunay,Voronoi,Skeleton)have been evaluated by four different criteria:(i)Number of additional created graph edges,(ii)additional graph creation time,(iii)route computation time,(iv)routing quality.We show that each algorithm has advantages and disadvantages depending on the use case.We identify the algorithms Visibility with a reduced number of edges in the subgraph and Spider-Grid with a large grid size to be a good compromise in many scenarios.展开更多
基金supported by European Commission[grant number 612096(CAP4Access)].
文摘Finding the shortest path through open spaces is a well-known challenge for pedestrian routing engines.A common solution is routing on the open space boundary,which causes in most cases an unnecessarily long route.A possible alternative is to create a subgraph within the open space.This paper assesses this approach and investigates its implications for routing engines.A number of algorithms(Grid,Spider-Grid,Visibility,Delaunay,Voronoi,Skeleton)have been evaluated by four different criteria:(i)Number of additional created graph edges,(ii)additional graph creation time,(iii)route computation time,(iv)routing quality.We show that each algorithm has advantages and disadvantages depending on the use case.We identify the algorithms Visibility with a reduced number of edges in the subgraph and Spider-Grid with a large grid size to be a good compromise in many scenarios.
