6 ms·
Show HN: Dijkstra’s algorithm in the web browser with OpenStreetMap
- soperj 10y agothis is unbelievably relevant for me right now, because this is exactly what I was looking to implement. Any gotchas? Lessons learned?
- ctcliff 10y agoThe geographic rendering APIs tend to be incompatible with the graphing algorithms and data structures. It's better to optimize your data on the server for algorithmic simplicity and convert to a render-friendly format at render time. Also, immutability is great when you're juggling 1000s of lon/lat arrays.
- maxerickson 10y agoSmall discussion of a previous routing algorithm implemented in a similar way: https://news.ycombinator.com/item?id=12187275 https://news.ycombinator.com/item?id=12187275
- ddlutz 10y agoHave you tried this with A* and seen any performance differences? This is very fast in the browser with a small map, but I imagine with a much larger map the difference would be noticeable.
- ctcliff 10y agoI haven't, but even at this size the rendering is quite a bit slower than the calculation. For example, the delay on reload is almost entirely from rendering the shortest path tree.
- d33 10y agoHow about an open source version?
- teraflop 10y agoAnyone who's interested in this might want to check out the OSRM project, which uses a much more complex routing algorithm to efficiently find paths through the entire OSM graph, instead of just a tiny subset: http://map.project-osrm.org/ http://map.project-osrm.org/ (Also, it's open-source.)
- mastazi 10y agoAre there any instructions? It took me a long while to figure out how to drop pins (the placeholder text says you have to press Enter, but you actually need to use the mouse), and now I have no idea how to display the route.
- danpat 10y agoYou can type place names into the entry boxes on the front-end - they get converted to lon/lat using a geocoding database. OR you can drop pins on the map.
- kornish 10y agoIs the geocoding database public as well? If so, do you know where it's hosted?
- maxerickson 10y agoIt's https://nominatim.openstreetmap.org/ https://nominatim.openstreetmap.org/. There's a use policy: http://wiki.openstreetmap.org/wiki/Nominatim_usage_policy http://wiki.openstreetmap.org/wiki/Nominatim_usage_policy
- alex_minimax 10y agoI've got the two markers but no route being displayed, is there a third step (firefox and chrome)?
- Doctor_Fegg 10y agoOSRM is wonderful. I run bike routing for North America and Western Europe using a heavily customised instance of OSRM (based on OSM data, of course): http://cycle.travel/map http://cycle.travel/map
- _RPM 10y agoInteresting. It'd be pretty cooler if this was free software though.
- jlarocco 10y agoBug report: if I open this in a background tab the map is zoomed in very close at a weird spot near the middle and it's confusing what is being demonstrated.
- kevan 10y agoRelated: A few friends and I built a similar visualization for pathfinding algorithms with OSM data for an AI class: http://www.kevanahlquist.com/osm_pathfinding/ http://www.kevanahlquist.com/osm_pathfinding/ It shows how nodes are explored on the map with different search algorithms and the optimal path once the search is completed.
- grawlinson 10y agoThat is very cool, some of the results are hilarious, i.e. depth first.
- kevan 10y agoDFS is my favorite, but if you let it run long enough it might crash your browser tab.
- kevan 10y agoRelated: A few friends and I built a similar visualization for pathfinding algorithms with OSM data for an AI class: http://www.kevanahlquist.com/osm_pathfinding/ http://www.kevanahlquist.com/osm_pathfinding/ It shows how nodes are explored on the map with different search algorithms and the optimal path once the search is completed.
- mgalka 10y agoVery cool project. Great presentation.
- janci 10y agoIt would be more interesting, if the path is animated and shows the computation of the algorithm, not only the result.
- liotier 10y agoI thought that Dijkstra required rasterization... But here it appears that it works with graph... Is there something I have missed ?
- EllipticCurve 10y agoWhat would you need rasterization for? Dijkstra works fine on arbitrary graphs with non-negative edges!
- liotier 10y agoOk, I'll go read a few papers... I'm guessing I misled myself because I needed routing across open spaces around obstacles and that required rasterization - made me forget that the graph routing works just fine.
- deleted 10y ago[deleted]
- sapien13 10y agoNice work. I think we are doing somethings correlated. https://news.ycombinator.com/item?id=12647348 https://news.ycombinator.com/item?id=12647348