如果您的路径受到限制,您应该考虑使用同样的最短路径问题的线性规划公式。
http://en.wikipedia.org/wiki/Shortest_path_problem
你的目标是最小化在你的.osm文件中定义的起始和结束“节点”之间采取的每个“路径”的距离总和。任何障碍都将被制定为限制条件。要使用Java实现,请参见下面的链接。
非常好的问题!
四叉树是一种解决方案,因为您还可以将线/边索引到其中,而不仅仅是节点。
但是,这种“天真”的方法的问题在于这些解决方案会占用大量内存。例如,如果您已经有一个非常大的图形用于最短路径计算,则需要相同或更多的内存用于四叉树(或者我做了一些非常愚蠢的事情)。
一种解决方案如下:
这个描述清楚吗?
更新 这已经在graphhopper中实现了!
为了获得更高效的内存解决方案,您只需排除一个条目(瓷砖)中的相同节点。
减少内存使用的一种更复杂的技术:如果图形遍历尊重瓷砖边界,则可以想象该图形被分成几个子图形以适应该瓷砖(即,图形遍历不会到达瓷砖边界之外的其他子图形)。现在,您不需要所有节点,而只需要位于不同子图形中的节点!这将减少内存使用,但在查询时,您需要遍历不止一个边缘(就像当前的graphhopper实现一样)!因为您需要遍历整个瓷砖-即使瓷砖边界没有超出。