计算机科学
网格
能见度
德劳内三角测量
算法
多路径等成本路由
静态路由
沃罗诺图
布线(电子设计自动化)
分布式计算
数学
计算机网络
地理
路由协议
几何学
气象学
作者
Stefan Hahmann,Jakob Miksch,Bernd Resch,Johannes Lauer,Alexander Zipf
标识
DOI:10.1080/10095020.2017.1399675
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI