GeoJSON point clustering (#5724)

* add supercluster dependency
* prepare GeoJSONTile for Supercluster
* prepare GeoJSONSource for accepting options
* try removing mbgl::GeoJSON
* fix setGeoJSON types
* add GeoJSONSource getURL
* add geojson to include path
* add Supercluster index in GeoJSONSource
* fix GeoJSONSource getZoomRange
* bring back mbgl::GeoJSON header
* fix tidy warnings hopefully
* try test-suite with enabled cluster test
* fix formatting in clustering-related files

6 files changed, 102 insertions, 60 deletions

diff --git a/src/mbgl/style/sources/geojson_source.cpp b/src/mbgl/style/sources/geojson_source.cpp
index a3eec4f4ef..2bf27880b4 100644
--- a/src/mbgl/style/sources/geojson_source.cpp
+++ b/src/mbgl/style/sources/geojson_source.cpp
@@ -4,17 +4,22 @@
 namespace mbgl {
 namespace style {
 
-GeoJSONSource::GeoJSONSource(const std::string& id)
-    : Source(SourceType::GeoJSON, std::make_unique<GeoJSONSource::Impl>(std::move(id), *this))
-    , impl(static_cast<Impl*>(baseImpl.get())) {
+GeoJSONSource::GeoJSONSource(const std::string& id, const GeoJSONOptions options)
+    : Source(SourceType::GeoJSON,
+             std::make_unique<GeoJSONSource::Impl>(std::move(id), *this, options)),
+      impl(static_cast<Impl*>(baseImpl.get())) {
 }
 
 void GeoJSONSource::setURL(const std::string& url) {
     impl->setURL(url);
 }
 
-void GeoJSONSource::setGeoJSON(GeoJSON&& geoJSON) {
-    impl->setGeoJSON(std::move(geoJSON));
+void GeoJSONSource::setGeoJSON(const mapbox::geojson::geojson& geoJSON) {
+    impl->setGeoJSON(geoJSON);
+}
+
+std::string GeoJSONSource::getURL() {
+    return impl->getURL();
 }
 
 } // namespace style
diff --git a/src/mbgl/style/sources/geojson_source_impl.cpp b/src/mbgl/style/sources/geojson_source_impl.cpp
index 9e6b3d34f6..0821ac0232 100644
--- a/src/mbgl/style/sources/geojson_source_impl.cpp
+++ b/src/mbgl/style/sources/geojson_source_impl.cpp
@@ -1,43 +1,37 @@
-#include <mbgl/style/sources/geojson_source_impl.hpp>
-#include <mbgl/style/source_observer.hpp>
+#include <mbgl/platform/log.hpp>
+#include <mbgl/storage/file_source.hpp>
 #include <mbgl/style/conversion/geojson.hpp>
+#include <mbgl/style/source_observer.hpp>
+#include <mbgl/style/sources/geojson_source_impl.hpp>
 #include <mbgl/tile/geojson_tile.hpp>
-#include <mbgl/storage/file_source.hpp>
-#include <mbgl/platform/log.hpp>
 #include <mbgl/util/rapidjson.hpp>
 
 #include <mapbox/geojson.hpp>
 #include <mapbox/geojson/rapidjson.hpp>
 #include <mapbox/geojsonvt.hpp>
 #include <mapbox/geojsonvt/convert.hpp>
+#include <supercluster.hpp>
 
 #include <rapidjson/error/en.h>
 
 #include <sstream>
 
-using namespace mapbox::geojsonvt;
-
 namespace mbgl {
 namespace style {
 namespace conversion {
 
 template <>
 Result<GeoJSON> convertGeoJSON(const JSValue& value) {
-    Options options;
-    options.buffer = util::EXTENT / util::tileSize * 128;
-    options.extent = util::EXTENT;
-
     try {
-        const auto geojson = mapbox::geojson::convert(value);
-        return GeoJSON { std::make_unique<GeoJSONVT>(geojson, options) };
+        return mapbox::geojson::convert(value);
     } catch (const std::exception& ex) {
-        return Error { ex.what() };
+        return Error{ ex.what() };
     }
 }
 } // namespace conversion
 
-GeoJSONSource::Impl::Impl(std::string id_, Source& base_)
-    : Source::Impl(SourceType::GeoJSON, std::move(id_), base_) {
+GeoJSONSource::Impl::Impl(std::string id_, Source& base_, const GeoJSONOptions options_)
+    : Source::Impl(SourceType::GeoJSON, std::move(id_), base_), options(options_) {
 }
 
 GeoJSONSource::Impl::~Impl() = default;
@@ -46,12 +40,36 @@ void GeoJSONSource::Impl::setURL(std::string url) {
     urlOrGeoJSON = std::move(url);
 }
 
-void GeoJSONSource::Impl::setGeoJSON(GeoJSON&& geoJSON) {
-    urlOrGeoJSON = std::move(geoJSON);
+std::string GeoJSONSource::Impl::getURL() {
+    assert(urlOrGeoJSON.is<std::string>());
+    return urlOrGeoJSON.get<std::string>();
+}
+
+void GeoJSONSource::Impl::setGeoJSON(const GeoJSON& geoJSON) {
+    double scale = util::EXTENT / util::tileSize;
+
+    if (!options.cluster) {
+        mapbox::geojsonvt::Options vtOptions;
+        vtOptions.maxZoom = options.maxzoom;
+        vtOptions.extent = util::EXTENT;
+        vtOptions.buffer = std::round(scale * options.buffer);
+        vtOptions.tolerance = scale * options.tolerance;
+        urlOrGeoJSON = std::make_unique<mapbox::geojsonvt::GeoJSONVT>(geoJSON, vtOptions);
+
+    } else {
+        mapbox::supercluster::Options clusterOptions;
+        clusterOptions.maxZoom = options.clusterMaxZoom;
+        clusterOptions.extent = util::EXTENT;
+        clusterOptions.radius = std::round(scale * options.clusterRadius);
+
+        const auto& features = geoJSON.get<mapbox::geometry::feature_collection<double>>();
+        urlOrGeoJSON =
+            std::make_unique<mapbox::supercluster::Supercluster>(features, clusterOptions);
+    }
 }
 
 void GeoJSONSource::Impl::load(FileSource& fileSource) {
-    if (urlOrGeoJSON.is<GeoJSON>()) {
+    if (!urlOrGeoJSON.is<std::string>()) {
         loaded = true;
         return;
     }
@@ -63,19 +81,23 @@ void GeoJSONSource::Impl::load(FileSource& fileSource) {
     const std::string& url = urlOrGeoJSON.get<std::string>();
     req = fileSource.request(Resource::source(url), [this](Response res) {
         if (res.error) {
-            observer->onSourceError(base, std::make_exception_ptr(std::runtime_error(res.error->message)));
+            observer->onSourceError(
+                base, std::make_exception_ptr(std::runtime_error(res.error->message)));
         } else if (res.notModified) {
             return;
         } else if (res.noContent) {
-            observer->onSourceError(base, std::make_exception_ptr(std::runtime_error("unexpectedly empty GeoJSON")));
+            observer->onSourceError(
+                base, std::make_exception_ptr(std::runtime_error("unexpectedly empty GeoJSON")));
         } else {
             rapidjson::GenericDocument<rapidjson::UTF8<>, rapidjson::CrtAllocator> d;
             d.Parse<0>(res.data->c_str());
 
             if (d.HasParseError()) {
                 std::stringstream message;
-                message << d.GetErrorOffset() << " - " << rapidjson::GetParseError_En(d.GetParseError());
-                observer->onSourceError(base, std::make_exception_ptr(std::runtime_error(message.str())));
+                message << d.GetErrorOffset() << " - "
+                        << rapidjson::GetParseError_En(d.GetParseError());
+                observer->onSourceError(base,
+                                        std::make_exception_ptr(std::runtime_error(message.str())));
                 return;
             }
 
@@ -83,13 +105,13 @@ void GeoJSONSource::Impl::load(FileSource& fileSource) {
 
             conversion::Result<GeoJSON> geoJSON = conversion::convertGeoJSON<JSValue>(d);
             if (!geoJSON) {
-                Log::Error(Event::ParseStyle, "Failed to parse GeoJSON data: %s", geoJSON.error().message.c_str());
+                Log::Error(Event::ParseStyle, "Failed to parse GeoJSON data: %s",
+                           geoJSON.error().message.c_str());
                 // Create an empty GeoJSON VT object to make sure we're not infinitely waiting for
                 // tiles to load.
-                mapbox::geojson::feature_collection features;
-                urlOrGeoJSON = GeoJSON { std::make_unique<GeoJSONVT>(features) };
+                setGeoJSON(GeoJSON{ FeatureCollection{} });
             } else {
-                urlOrGeoJSON = std::move(*geoJSON);
+                setGeoJSON(*geoJSON);
             }
 
             loaded = true;
@@ -100,13 +122,20 @@ void GeoJSONSource::Impl::load(FileSource& fileSource) {
 
 Range<uint8_t> GeoJSONSource::Impl::getZoomRange() {
     assert(loaded);
-    return { 0, urlOrGeoJSON.get<GeoJSON>().impl->options.maxZoom };
+    return { 0, options.maxzoom };
 }
 
 std::unique_ptr<Tile> GeoJSONSource::Impl::createTile(const OverscaledTileID& tileID,
                                                       const UpdateParameters& parameters) {
     assert(loaded);
-    return std::make_unique<GeoJSONTile>(tileID, base.getID(), parameters, *urlOrGeoJSON.get<GeoJSON>().impl);
+    if (urlOrGeoJSON.is<GeoJSONVTPointer>()) {
+        return std::make_unique<GeoJSONTile>(tileID, base.getID(), parameters,
+                                             *urlOrGeoJSON.get<GeoJSONVTPointer>());
+    } else {
+        assert(urlOrGeoJSON.is<SuperclusterPointer>());
+        return std::make_unique<GeoJSONTile>(tileID, base.getID(), parameters,
+                                             *urlOrGeoJSON.get<SuperclusterPointer>());
+    }
 }
 
 } // namespace style
diff --git a/src/mbgl/style/sources/geojson_source_impl.hpp b/src/mbgl/style/sources/geojson_source_impl.hpp
index e6e01c06e9..eb3563e85a 100644
--- a/src/mbgl/style/sources/geojson_source_impl.hpp
+++ b/src/mbgl/style/sources/geojson_source_impl.hpp
@@ -1,7 +1,7 @@
 #pragma once
 
-#include <mbgl/style/sources/geojson_source.hpp>
 #include <mbgl/style/source_impl.hpp>
+#include <mbgl/style/sources/geojson_source.hpp>
 #include <mbgl/util/variant.hpp>
 
 namespace mbgl {
@@ -12,11 +12,13 @@ namespace style {
 
 class GeoJSONSource::Impl : public Source::Impl {
 public:
-    Impl(std::string id, Source&);
+    Impl(std::string id, Source&, const GeoJSONOptions);
     ~Impl() final;
 
     void setURL(std::string);
-    void setGeoJSON(GeoJSON&&);
+    void setGeoJSON(const GeoJSON&);
+
+    std::string getURL();
 
     void load(FileSource&) final;
 
@@ -24,16 +26,14 @@ public:
         return util::tileSize;
     }
 
-    const variant<std::string, GeoJSON>& getURLOrGeoJSON() const {
-        return urlOrGeoJSON;
-    }
-
 private:
     Range<uint8_t> getZoomRange() final;
     std::unique_ptr<Tile> createTile(const OverscaledTileID&, const UpdateParameters&) final;
 
-    variant<std::string, GeoJSON> urlOrGeoJSON;
+    variant<std::string, GeoJSONVTPointer, SuperclusterPointer> urlOrGeoJSON;
     std::unique_ptr<AsyncRequest> req;
+
+    GeoJSONOptions options;
 };
 
 } // namespace style
diff --git a/src/mbgl/tile/geojson_tile.cpp b/src/mbgl/tile/geojson_tile.cpp
index 0dc4ac9107..ab596bd9ba 100644
--- a/src/mbgl/tile/geojson_tile.cpp
+++ b/src/mbgl/tile/geojson_tile.cpp
@@ -3,6 +3,7 @@
 #include <mbgl/style/update_parameters.hpp>
 
 #include <mapbox/geojsonvt.hpp>
+#include <supercluster.hpp>
 
 namespace mbgl {
 
@@ -46,17 +47,16 @@ private:
 };
 
 // Converts the geojsonvt::Tile to a a GeoJSONTile. They have a differing internal structure.
-std::unique_ptr<GeoJSONTileData> convertTile(const mapbox::geojsonvt::Tile& tile) {
+std::unique_ptr<GeoJSONTileData> convertTile(const mapbox::geometry::feature_collection<int16_t>& features) {
     std::shared_ptr<GeoJSONTileLayer> layer;
 
-    if (!tile.features.empty()) {
-        std::vector<std::shared_ptr<const GeoJSONTileFeature>> features;
-        GeometryCoordinates line;
+    if (!features.empty()) {
+        std::vector<std::shared_ptr<const GeoJSONTileFeature>> convertedFeatures;
 
         ToFeatureType toFeatureType;
         ToGeometryCollection toGeometryCollection;
 
-        for (auto& feature : tile.features) {
+        for (auto& feature : features) {
             const FeatureType featureType = apply_visitor(toFeatureType, feature.geometry);
 
             if (featureType == FeatureType::Unknown) {
@@ -72,11 +72,11 @@ std::unique_ptr<GeoJSONTileData> convertTile(const mapbox::geojsonvt::Tile& tile
 
             PropertyMap properties = feature.properties;
 
-            features.emplace_back(std::make_shared<GeoJSONTileFeature>(
+            convertedFeatures.emplace_back(std::make_shared<GeoJSONTileFeature>(
                 featureType, std::move(geometry), std::move(properties)));
         }
 
-        layer = std::make_unique<GeoJSONTileLayer>(std::move(features));
+        layer = std::make_unique<GeoJSONTileLayer>(std::move(convertedFeatures));
     }
 
     return std::make_unique<GeoJSONTileData>(layer);
@@ -87,7 +87,15 @@ GeoJSONTile::GeoJSONTile(const OverscaledTileID& overscaledTileID,
                          const style::UpdateParameters& parameters,
                          mapbox::geojsonvt::GeoJSONVT& geojsonvt)
     : GeometryTile(overscaledTileID, sourceID_, parameters.style, parameters.mode) {
-    setData(convertTile(geojsonvt.getTile(id.canonical.z, id.canonical.x, id.canonical.y)));
+    setData(convertTile(geojsonvt.getTile(id.canonical.z, id.canonical.x, id.canonical.y).features));
+}
+
+GeoJSONTile::GeoJSONTile(const OverscaledTileID& overscaledTileID,
+                         std::string sourceID_,
+                         const style::UpdateParameters& parameters,
+                         mapbox::supercluster::Supercluster& supercluster)
+    : GeometryTile(overscaledTileID, sourceID_, parameters.style, parameters.mode) {
+    setData(convertTile(supercluster.getTile(id.canonical.z, id.canonical.x, id.canonical.y)));
 }
 
 void GeoJSONTile::setNecessity(Necessity) {}
diff --git a/src/mbgl/tile/geojson_tile.hpp b/src/mbgl/tile/geojson_tile.hpp
index 09fdd1ec9b..422101b767 100644
--- a/src/mbgl/tile/geojson_tile.hpp
+++ b/src/mbgl/tile/geojson_tile.hpp
@@ -3,9 +3,15 @@
 #include <mbgl/tile/geometry_tile.hpp>
 
 namespace mapbox {
+
 namespace geojsonvt {
 class GeoJSONVT;
 } // namespace geojsonvt
+
+namespace supercluster {
+class Supercluster;
+} // namespace supercluster
+
 } // namespace mapbox
 
 namespace mbgl {
@@ -21,6 +27,11 @@ public:
                 const style::UpdateParameters&,
                 mapbox::geojsonvt::GeoJSONVT&);
 
+    GeoJSONTile(const OverscaledTileID&,
+                std::string sourceID,
+                const style::UpdateParameters&,
+                mapbox::supercluster::Supercluster&);
+
     void setNecessity(Necessity) final;
 };
 
diff --git a/src/mbgl/util/geojson.cpp b/src/mbgl/util/geojson.cpp
deleted file mode 100644
index a17d01f933..0000000000
--- a/src/mbgl/util/geojson.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-#include <mbgl/util/geojson.hpp>
-
-#include <mapbox/geojsonvt.hpp>
-
-namespace mbgl {
-
-GeoJSON::GeoJSON(std::unique_ptr<mapbox::geojsonvt::GeoJSONVT> impl_) : impl(std::move(impl_)) {}
-GeoJSON::GeoJSON(GeoJSON&&) = default;
-GeoJSON::~GeoJSON() = default;
-
-} // namespace mbgl