Project-OSRM · danpat · Dec 5, 2016 · Dec 9, 2016 · Feb 4, 2017 · Feb 4, 2017
diff --git a/example/isochrone-viewer.html b/example/isochrone-viewer.html
@@ -0,0 +1,142 @@
+<!DOCTYPE html>
+<html>
+
+<head>
+    <meta charset='utf-8' />
+    <title></title>
+    <meta name='viewport' content='initial-scale=1,maximum-scale=1,user-scalable=no' />
+    <script src='https://api.tiles.mapbox.com/mapbox-gl-js/v0.32.1/mapbox-gl.js'></script>
+    <link href='https://api.tiles.mapbox.com/mapbox-gl-js/v0.32.1/mapbox-gl.css' rel='stylesheet' />
+    <style>
+        body {
+            margin: 0;
+            padding: 0;
+        }
+
+        #map {
+            position: absolute;
+            top: 0;
+            bottom: 0;
+            width: 100%;
+        }
+    </style>
+    <style type='text/css'>
+        #info {
+            display: block;
+            position: relative;
+            margin: 0px auto;
+            width: 50%;
+            padding: 10px;
+            border: none;
+            border-radius: 3px;
+            font-size: 12px;
+            text-align: center;
+            color: #222;
+            background: #fff;
+        }
+    </style>
+</head>
+
+<body>
+
+    <div id='map'></div>
+    <div id="info"></div>
+    <script>
+        mapboxgl.accessToken = 'YOUR_TOKEN_HERE';
+        var map = new mapboxgl.Map({
+            container: 'map',
+            style: 'mapbox://styles/mapbox/streets-v9',
+            center: [-122.43376611457057, 37.788998452552065],
+            zoom: 13
+        });
+
+        map.on('mousemove', function (e) {
+            document.getElementById('info').innerHTML =
+                // e.point is the x, y coordinates of the mousemove event relative
+                // to the top-left corner of the map
+                JSON.stringify(e.point) + '<br />' +
+                // e.lngLat is the longitude, latitude geographical position of the event
+                JSON.stringify(e.lngLat);
+        });
+
+        map.on('click', function (e) {
+            console.log(JSON.stringify(e.lngLat));
+            var xhttp = new XMLHttpRequest();
+            xhttp.onreadystatechange = function () {
+                if (this.readyState == 4 && this.status == 200) {
+                    var j = JSON.parse(this.responseText);
+
+                    if (map.getSource("isochrone")) {
+                        map.removeSource("isochrone");
+                    }
+                    map.addSource("isochrone", {
+                        "type": "geojson",
+                        "data": j
+                    });
+
+                    if (!map.getLayer("isochrone-layer")) {
+                        /*
+                        map.addLayer({
+                            "id": "isochrone-layer",
+                            "type": "line",
+                            "source": "isochrone",
+                            "layout": {
+                                "line-join": "round",
+                                "line-cap": "round"
+                            },
+                            "paint": {
+                                "line-color": "#f00",
+                                "line-width": 4,
+                                "line-offset": 2
+                            },
+                            "filter": [
+                                "==", "direction", "forward"
+                            ]
+                        });
+                        map.addLayer({
+                            "id": "isochrone-layer-bk",
+                            "type": "line",
+                            "source": "isochrone",
+                            "layout": {
+                                "line-join": "round",
+                                "line-cap": "round"
+                            },
+                            "paint": {
+                                "line-color": "#00f",
+                                "line-width": 4,
+                                "line-offset": 4
+                            },
+                            "filter": [
+                                "==", "direction", "backward"
+                            ]
+                        });
+                        */
+                        map.addLayer({
+                            "id": "isochrone-points",
+                            "type": "circle",
+                            "source": "isochrone",
+                            "paint": {
+                                "circle-radius": 15,
+                                "circle-color": {
+                                    "property": "weight",
+                                    "stops": [
+                                        [0, 'blue'],
+                                        [2000, 'red'],
+                                        [4000, 'yellow'],
+                                        [6000, 'green'],
+                                        [8000, 'orange']
+                                    ]
+                                }
+                            }
+                        });
+                    }
+                }
+            };
+            xhttp.open("GET", "http://localhost:5000/isochrone/v1/driving/" + e.lngLat.lng + "," + e.lngLat.lat, true);
+            xhttp.send();
+        });
+    </script>
+
+</body>
+
+</html>
diff --git a/include/engine/api/isochrone_parameters.hpp b/include/engine/api/isochrone_parameters.hpp
@@ -0,0 +1,61 @@
+/*
+
+Copyright (c) 2016, Project OSRM contributors
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+Redistributions of source code must retain the above copyright notice, this list
+of conditions and the following disclaimer.
+Redistributions in binary form must reproduce the above copyright notice, this
+list of conditions and the following disclaimer in the documentation and/or
+other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+*/
+
+#ifndef ENGINE_API_ISOCHRONE_PARAMETERS_HPP
+#define ENGINE_API_ISOCHRONE_PARAMETERS_HPP
+
+#include "engine/api/base_parameters.hpp"
+
+namespace osrm
+{
+namespace engine
+{
+namespace api
+{
+
+/**
+ * Parameters specific to the OSRM Tile service.
+ *
+ * Holds member attributes:
+ *  - lon: centerpoint
+ *  - lat: centerpoint
+ *  - range: distance to travel
+ *
+ * \see OSRM, Coordinate, Hint, Bearing, RouteParame, RouteParameters, TableParameters,
+ *      NearestParameters, TripParameters, MatchParameters and TileParameters
+ */
+struct IsochroneParameters : public BaseParameters
+{
+    unsigned range = 300;
+
+    bool IsValid() const { return BaseParameters::IsValid() && range >= 1; }
+};
+}
+}
+}
+
+#endif
diff --git a/include/engine/engine.hpp b/include/engine/engine.hpp
@@ -1,6 +1,7 @@
 #ifndef ENGINE_HPP
 #define ENGINE_HPP
 
+#include "engine/api/isochrone_parameters.hpp"
 #include "engine/api/match_parameters.hpp"
 #include "engine/api/nearest_parameters.hpp"
 #include "engine/api/route_parameters.hpp"
@@ -11,6 +12,7 @@
 #include "engine/datafacade/contiguous_block_allocator.hpp"
 #include "engine/datafacade/datafacade_base.hpp"
 #include "engine/engine_config.hpp"
+#include "engine/plugins/isochrone.hpp"
 #include "engine/plugins/match.hpp"
 #include "engine/plugins/nearest.hpp"
 #include "engine/plugins/table.hpp"
@@ -47,6 +49,7 @@ class Engine final
     Status Trip(const api::TripParameters &parameters, util::json::Object &result) const;
     Status Match(const api::MatchParameters &parameters, util::json::Object &result) const;
     Status Tile(const api::TileParameters &parameters, std::string &result) const;
+    Status Isochrone(const api::IsochroneParameters &parameters, std::string &result) const;
 
   private:
     const plugins::ViaRoutePlugin route_plugin;
@@ -55,6 +58,7 @@ class Engine final
     const plugins::TripPlugin trip_plugin;
     const plugins::MatchPlugin match_plugin;
     const plugins::TilePlugin tile_plugin;
+    const plugins::IsochronePlugin isochrone_plugin;
 
     // note in case of shared memory this will be empty, since the watchdog
     // will provide us with the up-to-date facade

diff --git a/include/engine/plugins/isochrone.hpp b/include/engine/plugins/isochrone.hpp
@@ -0,0 +1,37 @@
+#ifndef ISOCHRONEPLUGIN_HPP
+#define ISOCHRONEPLUGIN_HPP
+
+#include "engine/api/isochrone_parameters.hpp"
+#include "engine/plugins/plugin_base.hpp"
+#include "engine/routing_algorithms/many_to_many.hpp"
+#include "engine/search_engine_data.hpp"
+
+#include <string>
+
+/**
+ * TODO
+ */
+namespace osrm
+{
+namespace engine
+{
+namespace plugins
+{
+
+class IsochronePlugin final : public BasePlugin
+{
+  private:
+    mutable SearchEngineData heaps;
+
+  public:
+    explicit IsochronePlugin();
+
+    Status HandleRequest(const std::shared_ptr<const datafacade::BaseDataFacade> facade,
+                         const api::IsochroneParameters &parameters,
+                         std::string &pbf_buffer) const;
+};
+}
+}
+}
+
+#endif /* TILEPLUGIN_HPP */
diff --git a/include/engine/routing_algorithms/many_to_many.hpp b/include/engine/routing_algorithms/many_to_many.hpp
@@ -50,20 +50,23 @@ class ManyToManyRouting final : public BasicRoutingInterface
     operator()(const std::shared_ptr<const datafacade::BaseDataFacade> facade,
                const std::vector<PhantomNode> &phantom_nodes,
                const std::vector<std::size_t> &source_indices,
-               const std::vector<std::size_t> &target_indices) const;
+               const std::vector<std::size_t> &target_indices,
+               const EdgeWeight max_weight = std::numeric_limits<EdgeWeight>::max()) const;
 
     void ForwardRoutingStep(const std::shared_ptr<const datafacade::BaseDataFacade> facade,
                             const unsigned row_idx,
                             const unsigned number_of_targets,
                             QueryHeap &query_heap,
                             const SearchSpaceWithBuckets &search_space_with_buckets,
                             std::vector<EdgeWeight> &weights_table,
-                            std::vector<EdgeWeight> &durations_table) const;
+                            std::vector<EdgeWeight> &durations_table,
+                            const EdgeWeight max_weight) const;
 
     void BackwardRoutingStep(const std::shared_ptr<const datafacade::BaseDataFacade> facade,
                              const unsigned column_idx,
                              QueryHeap &query_heap,
-                             SearchSpaceWithBuckets &search_space_with_buckets) const;
+                             SearchSpaceWithBuckets &search_space_with_buckets,
+                             const EdgeWeight max_weight) const;
 
     template <bool forward_direction>
     inline void RelaxOutgoingEdges(const std::shared_ptr<const datafacade::BaseDataFacade> facade,

diff --git a/include/osrm/isochrone_parameters.hpp b/include/osrm/isochrone_parameters.hpp
@@ -0,0 +1,38 @@
+/*
+
+Copyright (c) 2016, Project OSRM contributors
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without modification,
+are permitted provided that the following conditions are met:
+
+Redistributions of source code must retain the above copyright notice, this list
+of conditions and the following disclaimer.
+Redistributions in binary form must reproduce the above copyright notice, this
+list of conditions and the following disclaimer in the documentation and/or
+other materials provided with the distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+*/
+
+#ifndef GLOBAL_ISOCHRONE_PARAMETERS_HPP
+#define GLOBAL_ISOCHRONE_PARAMETERS_HPP
+
+#include "engine/api/isochrone_parameters.hpp"
+
+namespace osrm
+{
+using engine::api::IsochroneParameters;
+}
+
+#endif
diff --git a/include/osrm/osrm.hpp b/include/osrm/osrm.hpp
@@ -44,6 +44,7 @@ using engine::api::NearestParameters;
 using engine::api::TripParameters;
 using engine::api::MatchParameters;
 using engine::api::TileParameters;
+using engine::api::IsochroneParameters;
 
 /**
  * Represents a Open Source Routing Machine with access to its services.
@@ -130,6 +131,11 @@ class OSRM final
      */
     Status Tile(const TileParameters &parameters, std::string &result) const;
 
+    /**
+     * Isochrone: isochrone (range polygon) from a point
+     */
+    Status Isochrone(const IsochroneParameters &parameters, std::string &result) const;
+
   private:
     std::unique_ptr<engine::Engine> engine_;
 };

diff --git a/include/osrm/osrm_fwd.hpp b/include/osrm/osrm_fwd.hpp
@@ -52,6 +52,7 @@ struct NearestParameters;
 struct TripParameters;
 struct MatchParameters;
 struct TileParameters;
+struct IsochroneParameters;
 } // ns api
 
 class Engine;