[core] Annotation refactor

23 files changed, 464 insertions, 666 deletions

diff --git a/android/cpp/jni.cpp b/android/cpp/jni.cpp
index d5fcd34e57..7397c6f5df 100644
--- a/android/cpp/jni.cpp
+++ b/android/cpp/jni.cpp
@@ -1096,7 +1096,7 @@ jlongArray JNICALL nativeGetAnnotationsInBounds(JNIEnv *env, jobject obj, jlong
     bounds.ne = { neLat, neLon };
 
     // assume only points for now
-    std::vector<uint32_t> annotations = nativeMapView->getMap().getAnnotationsInBounds(bounds, mbgl::AnnotationType::Point);
+    std::vector<uint32_t> annotations = nativeMapView->getMap().getPointAnnotationsInBounds(bounds);
 
     return std_vector_uint_to_jobject(env, annotations);
 }
diff --git a/include/mbgl/annotation/annotation.hpp b/include/mbgl/annotation/annotation.hpp
index fd21cd5f6a..b3e3ab52b6 100644
--- a/include/mbgl/annotation/annotation.hpp
+++ b/include/mbgl/annotation/annotation.hpp
@@ -6,12 +6,6 @@
 
 namespace mbgl {
 
-enum class AnnotationType : uint8_t {
-    Any   = 0,
-    Point = 1 << 0,
-    Shape = 1 << 1,
-};
-
 using AnnotationID = uint32_t;
 using AnnotationIDs = std::vector<AnnotationID>;
 
diff --git a/include/mbgl/map/map.hpp b/include/mbgl/map/map.hpp
index 8a381cda65..70807f126f 100644
--- a/include/mbgl/map/map.hpp
+++ b/include/mbgl/map/map.hpp
@@ -135,9 +135,6 @@ public:
     const LatLng latLngForPixel(const vec2<double> pixel) const;
 
     // Annotations
-    void setDefaultPointAnnotationSymbol(const std::string&);
-    double getTopOffsetPixelsForAnnotationSymbol(const std::string&);
-
     AnnotationID addPointAnnotation(const PointAnnotation&);
     AnnotationIDs addPointAnnotations(const std::vector<PointAnnotation>&);
 
@@ -147,8 +144,9 @@ public:
     void removeAnnotation(AnnotationID);
     void removeAnnotations(const AnnotationIDs&);
 
-    AnnotationIDs getAnnotationsInBounds(const LatLngBounds&, const AnnotationType& = AnnotationType::Any);
+    AnnotationIDs getPointAnnotationsInBounds(const LatLngBounds&);
     LatLngBounds getBoundsForAnnotations(const AnnotationIDs&);
+    double getTopOffsetPixelsForAnnotationSymbol(const std::string&);
 
     // Sprites
     void setSprite(const std::string&, std::shared_ptr<const SpriteImage>);
diff --git a/include/mbgl/util/geo.hpp b/include/mbgl/util/geo.hpp
index 1f073ded8f..307134f666 100644
--- a/include/mbgl/util/geo.hpp
+++ b/include/mbgl/util/geo.hpp
@@ -1,6 +1,8 @@
 #ifndef MBGL_UTIL_GEO
 #define MBGL_UTIL_GEO
 
+#include <mbgl/util/vec.hpp>
+
 namespace mbgl {
 
 class TileID;
@@ -14,6 +16,8 @@ struct LatLng {
 
     // Constructs a LatLng object with the top left position of the specified tile.
     LatLng(const TileID& id);
+
+    vec2<double> project() const;
 };
 
 struct ProjectedMeters {
diff --git a/platform/ios/MGLMapView.mm b/platform/ios/MGLMapView.mm
index 163f3c6c7f..4810e0b44b 100644
--- a/platform/ios/MGLMapView.mm
+++ b/platform/ios/MGLMapView.mm
@@ -285,9 +285,6 @@ std::chrono::steady_clock::duration secondsAsDuration(float duration)
 
     _annotationImages = [NSMutableDictionary dictionary];
 
-    std::string defaultSymbolName([MGLDefaultStyleMarkerSymbolName UTF8String]);
-    _mbglMap->setDefaultPointAnnotationSymbol(defaultSymbolName);
-
     // setup logo bug
     //
     UIImage *logo = [[MGLMapView resourceImageNamed:@"mapbox.png"] imageWithAlignmentRectInsets:UIEdgeInsetsMake(1.5, 4, 3.5, 2)];
@@ -1159,7 +1156,7 @@ std::chrono::steady_clock::duration secondsAsDuration(float duration)
         tapBounds.extend(MGLLatLngFromLocationCoordinate2D(coordinate));
 
         // query for nearby annotations
-        std::vector<uint32_t> nearbyAnnotations = _mbglMap->getAnnotationsInBounds(tapBounds, mbgl::AnnotationType::Point);
+        std::vector<uint32_t> nearbyAnnotations = _mbglMap->getPointAnnotationsInBounds(tapBounds);
 
         int32_t newSelectedAnnotationID = -1;
 
diff --git a/src/mbgl/annotation/annotation_manager.cpp b/src/mbgl/annotation/annotation_manager.cpp
index 786ca42433..5e589bf289 100644
--- a/src/mbgl/annotation/annotation_manager.cpp
+++ b/src/mbgl/annotation/annotation_manager.cpp
@@ -1,490 +1,126 @@
 #include <mbgl/annotation/annotation_manager.hpp>
-#include <mbgl/annotation/point_annotation.hpp>
-#include <mbgl/annotation/shape_annotation.hpp>
-#include <mbgl/map/tile_id.hpp>
-#include <mbgl/map/live_tile.hpp>
-#include <mbgl/util/constants.hpp>
-#include <mbgl/util/geojsonvt/geojsonvt_convert.hpp>
-#include <mbgl/util/ptr.hpp>
-#include <mbgl/util/string.hpp>
+#include <mbgl/annotation/annotation_tile.hpp>
 #include <mbgl/style/style.hpp>
 #include <mbgl/style/style_bucket.hpp>
 #include <mbgl/style/style_layer.hpp>
 
-#include <algorithm>
+#include <boost/function_output_iterator.hpp>
 
 namespace mbgl {
 
-class Annotation : private util::noncopyable {
-public:
-    Annotation(AnnotationType, const AnnotationSegments&, const StyleProperties&);
+const std::string AnnotationManager::SourceID = "com.mapbox.annotations";
+const std::string AnnotationManager::PointLayerID = "com.mapbox.annotations.points";
 
-    const StyleProperties styleProperties;
-
-    LatLng getPoint() const;
-    LatLngBounds getBounds() const { return bounds; }
-
-    const AnnotationType type = AnnotationType::Point;
-    const AnnotationSegments geometry;
-    std::unordered_map<TileID, std::weak_ptr<const LiveTileFeature>, TileID::Hash> tilePointFeatures;
-    const LatLngBounds bounds;
-};
-
-Annotation::Annotation(AnnotationType type_,
-                       const AnnotationSegments& geometry_,
-                       const StyleProperties& styleProperties_)
-    : styleProperties(styleProperties_),
-      type(type_),
-      geometry(geometry_),
-      bounds([this] {
-          LatLngBounds bounds_;
-          assert(type != AnnotationType::Any);
-          if (type == AnnotationType::Point) {
-              bounds_ = { getPoint(), getPoint() };
-          } else {
-              for (auto& segment : geometry) {
-                  for (auto& point : segment) {
-                      bounds_.extend(point);
-                  }
-              }
-          }
-          return bounds_;
-      }()) {
-}
-
-LatLng Annotation::getPoint() const {
-    // Return the first line's first point. Shortcut for point annotations.
-    assert(!geometry.empty());
-    assert(!geometry[0].empty());
-    return geometry[0][0];
-}
-
-AnnotationManager::AnnotationManager() {}
-
-AnnotationManager::~AnnotationManager() {
-    // leave this here because the header file doesn't have a definition of
-    // Annotation so we can't destruct the object with just the header file.
-}
-
-void AnnotationManager::setDefaultPointAnnotationSymbol(const std::string& symbol) {
-    defaultPointAnnotationSymbol = symbol;
-}
-
-uint32_t AnnotationManager::nextID() {
-    return nextID_++;
-}
-
-vec2<double> AnnotationManager::projectPoint(const LatLng& point) {
-    // Clamp to the latitude limits of Mercator.
-    const double constrainedLatitude = ::fmin(::fmax(point.latitude, -util::LATITUDE_MAX), util::LATITUDE_MAX);
-
-    // Project a coordinate into unit space in a square map.
-    const double sine = std::sin(constrainedLatitude * M_PI / 180.0);
-    const double x = point.longitude / 360.0 + 0.5;
-    const double y = 0.5 - 0.25 * std::log((1.0 + sine) / (1.0 - sine)) / M_PI;
-    return { x, y };
-}
-
-uint32_t
-AnnotationManager::addShapeAnnotation(const ShapeAnnotation& shape, const uint8_t maxZoom) {
-    const uint32_t annotationID = nextID();
-
-    annotations.emplace(annotationID, std::make_unique<Annotation>(
-        AnnotationType::Shape,
-        shape.segments,
-        shape.styleProperties));
-
-    orderedShapeAnnotations.push_back(annotationID);
-
-    using namespace mapbox::util::geojsonvt;
-
-    const uint32_t z2 = 1 << maxZoom;
-    const double baseTolerance = 3;
-    const uint16_t extent = 4096;
-
-    const double tolerance = baseTolerance / (z2 * extent);
-
-    ProjectedGeometryContainer rings;
-
-    std::vector<LonLat> points;
-
-    for (size_t i = 0; i < shape.segments[0].size(); ++i) { // first segment for now (no holes)
-        const double constraintedLatitude = ::fmin(::fmax(shape.segments[0][i].latitude, -util::LATITUDE_MAX), util::LATITUDE_MAX);
-        points.push_back(LonLat(shape.segments[0][i].longitude, constraintedLatitude));
-    }
-
-    ProjectedFeatureType featureType;
-
-    if (shape.styleProperties.is<FillProperties>()) {
-        featureType = ProjectedFeatureType::Polygon;
-        
-        if (points.front().lon != points.back().lon || points.front().lat != points.back().lat) {
-            points.push_back(LonLat(points.front().lon, points.front().lat));
-        }
-    } else {
-        featureType = ProjectedFeatureType::LineString;
-    }
-
-    ProjectedGeometryContainer ring = Convert::project(points, tolerance);
-    rings.members.push_back(ring);
-
-    std::vector<ProjectedFeature> features;
-    features.push_back(Convert::create(Tags(), featureType, rings));
-
-    shapeTilers.emplace(annotationID, std::make_unique<GeoJSONVT>(features, maxZoom, 4, 100, 10));
-
-    return annotationID;
-}
-
-uint32_t
-AnnotationManager::addPointAnnotation(const PointAnnotation& point, const uint8_t maxZoom) {
-    // We pre-generate tiles to contain each annotation up to the map's max zoom.
-    // We do this for fast rendering without projection conversions on the fly, as well as
-    // to simplify bounding box queries of annotations later. Tiles get invalidated when
-    // annotations are added or removed in order to refresh the map render without
-    // touching the base map underneath.
-
-    const uint32_t annotationID = nextID();
-
-    // at render time we style the point according to its {sprite} field
-    std::unordered_map<std::string, std::string> featureProperties;
-    if (point.icon.length()) {
-        featureProperties.emplace("sprite", point.icon);
-    } else {
-        featureProperties.emplace("sprite", defaultPointAnnotationSymbol);
-    }
-
-    std::unique_ptr<Annotation> annotation = std::make_unique<Annotation>(
-        AnnotationType::Point,
-        AnnotationSegments({{ point.position }}),
-        StyleProperties({{ }}));
-
-    const uint16_t extent = 4096;
-
-    // projection conversion into unit space
-    vec2<double> pp = projectPoint(point.position);
-
-    for (int8_t z = maxZoom; z >= 0; z--) {
-        uint32_t z2 = 1 << z;
-        uint32_t x = pp.x * z2;
-        uint32_t y = pp.y * z2;
-
-        const Coordinate coordinate(extent * (pp.x * z2 - x), extent * (pp.y * z2 - y));
-
-        GeometryCollection geometries = {{ {{ coordinate }} }};
-        TileID featureTileID = TileID(z, x, y, z);
-
-        auto feature = std::make_shared<const LiveTileFeature>(FeatureType::Point, geometries, featureProperties);
-
-        // check for tile & create if necessary
-        auto tile_pos = tiles.emplace(featureTileID,
-                                      std::make_pair(std::unordered_set<uint32_t>({ annotationID }),
-                                                     std::make_unique<LiveTile>()));
-
-        // check for annotation layer & create if necessary
-        util::ptr<LiveTileLayer> layer;
-        std::string layerID = PointSourceID;
-
-        if (tile_pos.second || tile_pos.first->second.second->getMutableLayer(layerID) == nullptr) {
-            layer = std::make_shared<LiveTileLayer>();
-            tile_pos.first->second.second->addLayer(layerID, layer);
-        } else {
-            layer = tile_pos.first->second.second->getMutableLayer(layerID);
-
-            // associate annotation with tile
-            tile_pos.first->second.first.insert(annotationID);
-        }
-
-        // add feature to layer
-        layer->addFeature(feature);
-
-        // Record annotation association with tile and tile feature. This is used to determine stale tiles,
-        // as well as to remove the feature from the tile upon annotation deletion.
-        annotation->tilePointFeatures.emplace(featureTileID, std::weak_ptr<const LiveTileFeature>(feature));
-
-        // track affected tile
-        stalePointTileIDs.insert(featureTileID);
-    }
-
-    annotations.emplace(annotationID, std::move(annotation));
-
-    return annotationID;
-}
+AnnotationManager::AnnotationManager() = default;
+AnnotationManager::~AnnotationManager() = default;
 
 AnnotationIDs
-AnnotationManager::addPointAnnotations(const std::vector<PointAnnotation>& points,
-                                       const uint8_t maxZoom) {
+AnnotationManager::addPointAnnotations(const std::vector<PointAnnotation>& points, const uint8_t) {
     AnnotationIDs annotationIDs;
     annotationIDs.reserve(points.size());
 
     for (const auto& point : points) {
-        annotationIDs.push_back(addPointAnnotation(point, maxZoom));
+        const uint32_t annotationID = nextID++;
+        auto annotation = std::make_shared<PointAnnotationImpl>(annotationID, point);
+        pointTree.insert(annotation);
+        pointAnnotations.emplace(annotationID, annotation);
+        annotationIDs.push_back(annotationID);
     }
 
     return annotationIDs;
 }
 
 AnnotationIDs
-AnnotationManager::addShapeAnnotations(const std::vector<ShapeAnnotation>& shapes,
-                                       const uint8_t maxZoom) {
+AnnotationManager::addShapeAnnotations(const std::vector<ShapeAnnotation>& shapes, const uint8_t maxZoom) {
     AnnotationIDs annotationIDs;
     annotationIDs.reserve(shapes.size());
 
     for (const auto& shape : shapes) {
-        annotationIDs.push_back(addShapeAnnotation(shape, maxZoom));
+        const uint32_t annotationID = nextID++;
+        shapeAnnotations.emplace(annotationID,
+            std::make_unique<ShapeAnnotationImpl>(annotationID, shape, maxZoom));
+        annotationIDs.push_back(annotationID);
     }
 
     return annotationIDs;
 }
 
-void AnnotationManager::removeAnnotations(const AnnotationIDs& ids, const uint8_t maxZoom) {
-    std::vector<uint32_t> z2s;
-    const uint8_t zoomCount = maxZoom + 1;
-    z2s.reserve(zoomCount);
-    for (uint8_t z = 0; z < zoomCount; ++z) {
-        z2s.emplace_back(1<< z);
-    }
-
-    LatLng latLng;
-    vec2<double> p;
-    uint32_t x, y;
-
-    // iterate annotation id's passed
-    for (const auto& annotationID : ids) {
-        // grab annotation object
-        const auto& annotation_it = annotations.find(annotationID);
-        if (annotation_it != annotations.end()) {
-            const auto& annotation = annotation_it->second;
-            // remove feature(s) from relevant tiles
-            if (annotation->type == AnnotationType::Point) {
-                // calculate annotation's affected tile for each zoom
-                for (uint8_t z = 0; z < zoomCount; ++z) {
-                    latLng = annotation->getPoint();
-                    p = projectPoint(latLng);
-                    x = z2s[z] * p.x;
-                    y = z2s[z] * p.y;
-                    TileID tid(z, x, y, z);
-                    // erase annotation from tile's list
-                    auto& tileAnnotations = tiles[tid].first;
-                    tileAnnotations.erase(annotationID);
-                    // remove annotation's features from tile
-                    const auto& features_it = annotation->tilePointFeatures.find(tid);
-                    if (features_it != annotation->tilePointFeatures.end()) {
-                        // points share a layer; remove feature
-                        auto layer = tiles[tid].second->getMutableLayer(PointSourceID);
-                        layer->removeFeature(features_it->second);
-                        stalePointTileIDs.insert(tid);
-                    }
-                }
-            } else {
-                // remove shape layer from tiles if relevant
-                for (auto tile_it = tiles.begin(); tile_it != tiles.end(); ++tile_it) {
-                    if (tile_it->second.first.count(annotationID)) {
-                        tile_it->second.second->removeLayer(ShapeSourceID + "." + util::toString(annotationID));
-                    }
-                }
-
-                // clear shape from render order
-                auto shape_it = std::find(orderedShapeAnnotations.begin(), orderedShapeAnnotations.end(), annotationID);
-                orderedShapeAnnotations.erase(shape_it);
-
-                // clear shape tiler
-                shapeTilers.erase(annotationID);
-            }
-
-            annotations.erase(annotationID);
+void AnnotationManager::removeAnnotations(const AnnotationIDs& ids) {
+    for (const auto& id : ids) {
+        if (pointAnnotations.find(id) != pointAnnotations.end()) {
+            pointTree.remove(pointAnnotations.at(id));
+            pointAnnotations.erase(id);
+        } else if (shapeAnnotations.find(id) != shapeAnnotations.end()) {
+            // TODO: remove style layer
+            shapeAnnotations.erase(id);
         }
     }
 }
 
-AnnotationIDs AnnotationManager::getAnnotationsInBounds(const LatLngBounds& queryBounds,
-                                                        const uint8_t maxZoom,
-                                                        const AnnotationType& type) const {
-    const uint8_t z = maxZoom;
-    const uint32_t z2 = 1 << z;
-    const vec2<double> swPoint = projectPoint(queryBounds.sw);
-    const vec2<double> nePoint = projectPoint(queryBounds.ne);
+AnnotationIDs AnnotationManager::getPointAnnotationsInBounds(const LatLngBounds& bounds) const {
+    AnnotationIDs result;
 
-    // tiles number y from top down
-    const TileID nwTile(z, swPoint.x * z2, nePoint.y * z2, z);
-    const TileID seTile(z, nePoint.x * z2, swPoint.y * z2, z);
+    pointTree.query(boost::geometry::index::intersects(bounds),
+        boost::make_function_output_iterator([&](const auto& val){
+            result.push_back(val->id);
+        }));
 
-    std::unordered_set<uint32_t> matchingAnnotations;
-
-    for (auto& tile : tiles) {
-        TileID id = tile.first;
-        if (id.z == z) {
-            if (id.x >= nwTile.x && id.x <= seTile.x && id.y >= nwTile.y && id.y <= seTile.y) {
-                if (id.x > nwTile.x && id.x < seTile.x && id.y > nwTile.y && id.y < seTile.y) {
-                    // Trivial accept; this tile is completely inside the query bounds, so
-                    // we'll return all of its annotations that match type (if specified).
-                    if (type != AnnotationType::Any) {
-                        std::copy_if(tile.second.first.begin(), tile.second.first.end(),
-                                     std::inserter(matchingAnnotations, matchingAnnotations.begin()),
-                                     [&](const uint32_t annotationID) -> bool {
-                            const auto it = annotations.find(annotationID);
-                            if (it != annotations.end()) {
-                                return (it->second->type == type);
-                            } else {
-                                return false;
-                            }
-                        });
-                    } else {
-                        std::copy(tile.second.first.begin(), tile.second.first.end(),
-                                  std::inserter(matchingAnnotations, matchingAnnotations.begin()));
-                    }
-                } else {
-                    // This tile is intersected by the query bounds. We need to check the
-                    // tile's annotations' bounding boxes individually.
-                    std::copy_if(tile.second.first.begin(), tile.second.first.end(),
-                                 std::inserter(matchingAnnotations, matchingAnnotations.begin()),
-                                 [&](const uint32_t annotationID) -> bool {
-                        const auto it = annotations.find(annotationID);
-                        if (it != annotations.end()) {
-                            // check type
-                            if (type != AnnotationType::Any && it->second->type != type) {
-                                return false;
-                            }
-
-                            // check bounds
-                            if (it->second->type == AnnotationType::Point) {
-                                return queryBounds.contains(it->second->getPoint());
-                            } else if (it->second->type == AnnotationType::Shape) {
-                                return queryBounds.intersects(it->second->getBounds());
-                            }
-                        }
-                        return false;
-                    });
-                }
-            }
-        }
-    }
-
-    return AnnotationIDs(matchingAnnotations.begin(), matchingAnnotations.end());
+    return result;
 }
 
 LatLngBounds AnnotationManager::getBoundsForAnnotations(const AnnotationIDs& ids) const {
-    LatLngBounds bounds;
-    for (auto id : ids) {
-        const auto annotation_it = annotations.find(id);
-        if (annotation_it != annotations.end()) {
-            bounds.extend(annotation_it->second->getBounds());
+    LatLngBounds result;
+
+    for (const auto& id : ids) {
+        if (pointAnnotations.find(id) != pointAnnotations.end()) {
+            result.extend(pointAnnotations.at(id)->bounds());
+        } else if (shapeAnnotations.find(id) != shapeAnnotations.end()) {
+            result.extend(shapeAnnotations.at(id)->bounds());
         }
     }
 
-    return bounds;
+    return result;
 }
 
-const LiveTile* AnnotationManager::getTile(const TileID& id) {
-    // look up any existing annotation tile
-    LiveTile *renderTile = nullptr;
-    const auto tile_lookup_it = tiles.find(id);
-    if (tile_lookup_it != tiles.end()) {
-        // it exists and may have annotations already
-        renderTile = tile_lookup_it->second.second.get();
-    } else if (!orderedShapeAnnotations.empty()) {
-        // it needs created, but only for on-demand shapes
-        renderTile = tiles.emplace(id,
-            std::make_pair(std::unordered_set<uint32_t>(), std::make_unique<LiveTile>())
-        ).first->second.second.get();
-    }
-
-    if (renderTile != nullptr && !orderedShapeAnnotations.empty()) {
-
-        // create shape tile layers from GeoJSONVT queries
-        for (auto& tiler_it : shapeTilers) {
-            const auto annotationID = tiler_it.first;
-            const std::string layerID = ShapeSourceID + "." + util::toString(annotationID);
-
-            // check for existing render layer
-            auto renderLayer = renderTile->getMutableLayer(layerID);
-
-            if (renderLayer == nullptr) {
-                // we might need to create a tile layer for this shape
-                const auto& shapeTile = tiler_it.second->getTile(id.z, id.x, id.y);
-
-                if (shapeTile) {
+std::unique_ptr<AnnotationTile> AnnotationManager::getTile(const TileID& tileID) {
+    auto tile = std::make_unique<AnnotationTile>();
 
-                    // shape exists on this tile; let's make a layer
-                    renderLayer = std::make_shared<LiveTileLayer>();
+    AnnotationTileLayer& pointLayer = *tile->layers.emplace(
+        PointLayerID,
+        std::make_unique<AnnotationTileLayer>()).first->second;
 
-                    // convert the features and add to render layer
-                    for (auto& shapeFeature : shapeTile.features) {
+    LatLngBounds tileBounds(tileID);
 
-                        using namespace mapbox::util::geojsonvt;
+    pointTree.query(boost::geometry::index::intersects(tileBounds),
+        boost::make_function_output_iterator([&](const auto& val){
+            val->updateLayer(tileID, pointLayer);
+        }));
 
-                        FeatureType renderType = FeatureType::Unknown;
-
-                        if (shapeFeature.type == TileFeatureType::LineString) {
-                            renderType = FeatureType::LineString;
-                        } else if (shapeFeature.type == TileFeatureType::Polygon) {
-                            renderType = FeatureType::Polygon;
-                        }
-
-                        assert(renderType != FeatureType::Unknown);
-
-                        GeometryCollection renderGeometry;
-
-                        for (auto& shapeGeometry : shapeFeature.geometry) {
-
-                            std::vector<Coordinate> renderLine;
-
-                            auto& shapeRing = shapeGeometry.get<TileRing>();
-
-                            for (auto& shapePoint : shapeRing.points) {
-                                renderLine.emplace_back(shapePoint.x, shapePoint.y);
-                            }
-
-                            renderGeometry.push_back(renderLine);
-                        }
-
-                        auto renderFeature = std::make_shared<LiveTileFeature>(renderType, renderGeometry);
-
-                        renderLayer->addFeature(renderFeature);
-                    }
-
-                    // move the layer to the render tile
-                    renderTile->addLayer(layerID, renderLayer);
-
-                    // associate the annotation with the tile
-                    auto tile_update_it = tiles.find(id);
-                    assert(tile_update_it != tiles.end());
-                    tile_update_it->second.first.insert(annotationID);
-                }
-            }
-        }
+    for (const auto& shape : shapeAnnotations) {
+        shape.second->updateTile(tileID, *tile);
     }
 
-    return renderTile;
+    return tile;
 }
 
 void AnnotationManager::updateStyle(Style& style) {
-    // Create shape source
-    if (!style.getSource(ShapeSourceID)) {
-        std::unique_ptr<Source> shapeSource = std::make_unique<Source>();
-        shapeSource->info.type = SourceType::Annotations;
-        shapeSource->info.source_id = ShapeSourceID;
-        shapeSource->enabled = true;
-        style.addSource(std::move(shapeSource));
-    }
-
-    // Create point source and singular layer and bucket
-    if (!style.getSource(PointSourceID)) {
-        std::unique_ptr<Source> pointSource = std::make_unique<Source>();
-        pointSource->info.type = SourceType::Annotations;
-        pointSource->info.source_id = PointSourceID;
-        pointSource->enabled = true;
-        style.addSource(std::move(pointSource));
+    // Create annotation source, point layer, and point bucket
+    if (!style.getSource(SourceID)) {
+        std::unique_ptr<Source> source = std::make_unique<Source>();
+        source->info.type = SourceType::Annotations;
+        source->info.source_id = SourceID;
+        source->enabled = true;
+        style.addSource(std::move(source));
 
         std::map<ClassID, ClassProperties> pointPaints;
         pointPaints.emplace(ClassID::Default, ClassProperties());
-        std::unique_ptr<StyleLayer> pointLayer = std::make_unique<StyleLayer>(PointSourceID, std::move(pointPaints));
+        std::unique_ptr<StyleLayer> pointLayer = std::make_unique<StyleLayer>(PointLayerID, std::move(pointPaints));
         pointLayer->type = StyleLayerType::Symbol;
 
         util::ptr<StyleBucket> pointBucket = std::make_shared<StyleBucket>(pointLayer->type);
         pointBucket->name = pointLayer->id;
-        pointBucket->source = PointSourceID;
-        pointBucket->source_layer = pointLayer->id;
+        pointBucket->source = SourceID;
+        pointBucket->source_layer = PointLayerID;
         pointBucket->layout.set(PropertyKey::IconImage, ConstantFunction<std::string>("{sprite}"));
         pointBucket->layout.set(PropertyKey::IconAllowOverlap, ConstantFunction<bool>(true));
 
@@ -492,52 +128,11 @@ void AnnotationManager::updateStyle(Style& style) {
         style.addLayer(std::move(pointLayer));
     }
 
-    // Create new shape layers and buckets
-    for (const auto& shapeID : orderedShapeAnnotations) {
-        const std::string shapeLayerID = ShapeSourceID + "." + util::toString(shapeID);
-        if (style.getLayer(shapeLayerID)) {
-            continue;
-        }
-
-        const StyleProperties& shapeStyle = annotations.at(shapeID)->styleProperties;
-        ClassProperties paintProperties;
-
-        if (shapeStyle.is<LineProperties>()) {
-            const LineProperties& lineProperties = shapeStyle.get<LineProperties>();
-            paintProperties.set(PropertyKey::LineOpacity, ConstantFunction<float>(lineProperties.opacity));
-            paintProperties.set(PropertyKey::LineWidth, ConstantFunction<float>(lineProperties.width));
-            paintProperties.set(PropertyKey::LineColor, ConstantFunction<Color>(lineProperties.color));
-        } else if (shapeStyle.is<FillProperties>()) {
-            const FillProperties& fillProperties = shapeStyle.get<FillProperties>();
-            paintProperties.set(PropertyKey::FillOpacity, ConstantFunction<float>(fillProperties.opacity));
-            paintProperties.set(PropertyKey::FillColor, ConstantFunction<Color>(fillProperties.fill_color));
-            paintProperties.set(PropertyKey::FillOutlineColor, ConstantFunction<Color>(fillProperties.stroke_color));
-        }
-
-        std::map<ClassID, ClassProperties> shapePaints;
-        shapePaints.emplace(ClassID::Default, std::move(paintProperties));
-        std::unique_ptr<StyleLayer> shapeLayer = std::make_unique<StyleLayer>(shapeLayerID, std::move(shapePaints));
-        shapeLayer->type = (shapeStyle.is<LineProperties>() ? StyleLayerType::Line : StyleLayerType::Fill);
-
-        util::ptr<StyleBucket> shapeBucket = std::make_shared<StyleBucket>(shapeLayer->type);
-        shapeBucket->name = shapeLayer->id;
-        shapeBucket->source = ShapeSourceID;
-        shapeBucket->source_layer = shapeLayer->id;
-        if (shapeStyle.is<LineProperties>()) {
-            shapeBucket->layout.set(PropertyKey::LineJoin, ConstantFunction<JoinType>(JoinType::Round));
-        }
-
-        shapeLayer->bucket = shapeBucket;
-        style.addLayer(std::move(shapeLayer), PointSourceID);
+    for (const auto& shape : shapeAnnotations) {
+        shape.second->updateStyle(style);
     }
 
-    style.getSource(PointSourceID)->invalidateTiles(stalePointTileIDs);
-    style.getSource(ShapeSourceID)->invalidateTiles();
-
-    stalePointTileIDs.clear();
+    style.getSource(SourceID)->invalidateTiles();
 }
 
-const std::string AnnotationManager::PointSourceID = "com.mapbox.annotations.points";
-const std::string AnnotationManager::ShapeSourceID = "com.mapbox.annotations.shape";
-
 }
diff --git a/src/mbgl/annotation/annotation_manager.hpp b/src/mbgl/annotation/annotation_manager.hpp
index 2173442da8..1251585b00 100644
--- a/src/mbgl/annotation/annotation_manager.hpp
+++ b/src/mbgl/annotation/annotation_manager.hpp
@@ -1,66 +1,45 @@
-#ifndef MBGL_MAP_ANNOTATIONS
-#define MBGL_MAP_ANNOTATIONS
+#ifndef MBGL_ANNOTATION_MANAGER
+#define MBGL_ANNOTATION_MANAGER
 
 #include <mbgl/annotation/annotation.hpp>
-#include <mbgl/map/geometry_tile.hpp>
-#include <mbgl/map/tile_id.hpp>
-#include <mbgl/style/style_properties.hpp>
-#include <mbgl/style/types.hpp>
+#include <mbgl/annotation/point_annotation_impl.hpp>
+#include <mbgl/annotation/shape_annotation_impl.hpp>
 #include <mbgl/util/geo.hpp>
-#include <mbgl/util/geojsonvt/geojsonvt.hpp>
 #include <mbgl/util/noncopyable.hpp>
-#include <mbgl/util/vec.hpp>
 
 #include <string>
 #include <vector>
-#include <memory>
-#include <unordered_map>
-#include <unordered_set>
 
 namespace mbgl {
 
-class Annotation;
 class PointAnnotation;
 class ShapeAnnotation;
-class LiveTile;
+class AnnotationTile;
 class Style;
 
-using GeoJSONVT = mapbox::util::geojsonvt::GeoJSONVT;
-
 class AnnotationManager : private util::noncopyable {
 public:
     AnnotationManager();
     ~AnnotationManager();
 
-    void setDefaultPointAnnotationSymbol(const std::string& symbol);
-
     AnnotationIDs addPointAnnotations(const std::vector<PointAnnotation>&, const uint8_t maxZoom);
     AnnotationIDs addShapeAnnotations(const std::vector<ShapeAnnotation>&, const uint8_t maxZoom);
-    void removeAnnotations(const AnnotationIDs&, const uint8_t maxZoom);
+    void removeAnnotations(const AnnotationIDs&);
 
-    AnnotationIDs getAnnotationsInBounds(const LatLngBounds&, const uint8_t maxZoom, const AnnotationType& = AnnotationType::Any) const;
+    AnnotationIDs getPointAnnotationsInBounds(const LatLngBounds&) const;
     LatLngBounds getBoundsForAnnotations(const AnnotationIDs&) const;
 
     void updateStyle(Style&);
-    const LiveTile* getTile(const TileID& id);
+    std::unique_ptr<AnnotationTile> getTile(const TileID&);
 
-    static const std::string PointSourceID;
-    static const std::string ShapeSourceID;
+    static const std::string SourceID;
+    static const std::string PointLayerID;
 
 private:
-    inline uint32_t nextID();
-    static vec2<double> projectPoint(const LatLng& point);
-
-    uint32_t addShapeAnnotation(const ShapeAnnotation&, const uint8_t maxZoom);
-    uint32_t addPointAnnotation(const PointAnnotation&, const uint8_t maxZoom);
-
-    std::string defaultPointAnnotationSymbol;
-    std::unordered_map<uint32_t, std::unique_ptr<Annotation>> annotations;
-    std::vector<uint32_t> orderedShapeAnnotations;
-    std::unordered_map<TileID, std::pair<std::unordered_set<uint32_t>, std::unique_ptr<LiveTile>>, TileID::Hash> tiles;
-    std::unordered_map<uint32_t, std::unique_ptr<GeoJSONVT>> shapeTilers;
-    std::unordered_set<TileID, TileID::Hash> stalePointTileIDs;
-    uint32_t nextID_ = 0;
+    AnnotationID nextID = 0;
+    PointAnnotationImpl::Tree pointTree;
+    PointAnnotationImpl::Map pointAnnotations;
+    ShapeAnnotationImpl::Map shapeAnnotations;
 };
 
 }
diff --git a/src/mbgl/annotation/annotation_tile.cpp b/src/mbgl/annotation/annotation_tile.cpp
new file mode 100644
index 0000000000..71a6870cdb
--- /dev/null
+++ b/src/mbgl/annotation/annotation_tile.cpp
@@ -0,0 +1,28 @@
+#include <mbgl/annotation/annotation_tile.hpp>
+#include <mbgl/util/constants.hpp>
+
+namespace mbgl {
+
+AnnotationTileFeature::AnnotationTileFeature(FeatureType type_, GeometryCollection geometries_,
+                                 std::unordered_map<std::string, std::string> properties_)
+    : type(type_),
+      properties(properties_),
+      geometries(geometries_) {}
+
+mapbox::util::optional<Value> AnnotationTileFeature::getValue(const std::string& key) const {
+    auto it = properties.find(key);
+    if (it != properties.end()) {
+        return mapbox::util::optional<Value>(it->second);
+    }
+    return mapbox::util::optional<Value>();
+}
+
+util::ptr<GeometryTileLayer> AnnotationTile::getLayer(const std::string& name) const {
+    auto it = layers.find(name);
+    if (it != layers.end()) {
+        return it->second;
+    }
+    return nullptr;
+}
+
+}
diff --git a/src/mbgl/annotation/annotation_tile.hpp b/src/mbgl/annotation/annotation_tile.hpp
new file mode 100644
index 0000000000..bb7ec5d047
--- /dev/null
+++ b/src/mbgl/annotation/annotation_tile.hpp
@@ -0,0 +1,43 @@
+#ifndef MBGL_ANNOTATION_TILE
+#define MBGL_ANNOTATION_TILE
+
+#include <mbgl/map/geometry_tile.hpp>
+#include <mbgl/map/tile_id.hpp>
+
+#include <map>
+#include <unordered_map>
+
+namespace mbgl {
+
+class AnnotationTileFeature : public GeometryTileFeature {
+public:
+    AnnotationTileFeature(FeatureType, GeometryCollection,
+                          std::unordered_map<std::string, std::string> properties = {{}});
+
+    FeatureType getType() const override { return type; }
+    mapbox::util::optional<Value> getValue(const std::string&) const override;
+    GeometryCollection getGeometries() const override { return geometries; }
+
+    const FeatureType type;
+    const std::unordered_map<std::string, std::string> properties;
+    const GeometryCollection geometries;
+};
+
+class AnnotationTileLayer : public GeometryTileLayer {
+public:
+    std::size_t featureCount() const override { return features.size(); }
+    util::ptr<const GeometryTileFeature> getFeature(std::size_t i) const override { return features[i]; }
+
+    std::vector<util::ptr<const AnnotationTileFeature>> features;
+};
+
+class AnnotationTile : public GeometryTile {
+public:
+    util::ptr<GeometryTileLayer> getLayer(const std::string&) const override;
+
+    std::map<std::string, util::ptr<AnnotationTileLayer>> layers;
+};
+
+}
+
+#endif
diff --git a/src/mbgl/annotation/point_annotation_impl.cpp b/src/mbgl/annotation/point_annotation_impl.cpp
new file mode 100644
index 0000000000..a5f4ac269e
--- /dev/null
+++ b/src/mbgl/annotation/point_annotation_impl.cpp
@@ -0,0 +1,32 @@
+#include <mbgl/annotation/point_annotation_impl.hpp>
+#include <mbgl/annotation/annotation_tile.hpp>
+
+namespace mbgl {
+
+PointAnnotationImpl::PointAnnotationImpl(const AnnotationID id_, const PointAnnotation& point_)
+: id(id_),
+  point(point_) {
+}
+
+void PointAnnotationImpl::updateLayer(const TileID& tileID, AnnotationTileLayer& layer) const {
+    std::unordered_map<std::string, std::string> featureProperties;
+    featureProperties.emplace("sprite", point.icon.empty() ? std::string("default_marker") : point.icon);
+
+    const uint16_t extent = 4096;
+    const vec2<double> pp = point.position.project();
+    const uint32_t z2 = 1 << tileID.z;
+    const uint32_t x = pp.x * z2;
+    const uint32_t y = pp.y * z2;
+    const Coordinate coordinate(extent * (pp.x * z2 - x), extent * (pp.y * z2 - y));
+
+    layer.features.emplace_back(
+        std::make_shared<const AnnotationTileFeature>(FeatureType::Point,
+                                                      GeometryCollection {{ {{ coordinate }} }},
+                                                      featureProperties));
+}
+
+LatLngBounds PointAnnotationImpl::bounds() const {
+    return LatLngBounds(point.position, point.position);
+}
+
+}
diff --git a/src/mbgl/annotation/point_annotation_impl.hpp b/src/mbgl/annotation/point_annotation_impl.hpp
new file mode 100644
index 0000000000..2977caf577
--- /dev/null
+++ b/src/mbgl/annotation/point_annotation_impl.hpp
@@ -0,0 +1,72 @@
+#ifndef MBGL_POINT_ANNOTATION_IMPL
+#define MBGL_POINT_ANNOTATION_IMPL
+
+#include <mbgl/annotation/annotation.hpp>
+#include <mbgl/annotation/point_annotation.hpp>
+#include <mbgl/util/geo.hpp>
+
+#include <string>
+
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wunused-function"
+#pragma GCC diagnostic ignored "-Wunused-parameter"
+#pragma GCC diagnostic ignored "-Wunused-variable"
+#pragma GCC diagnostic ignored "-Wshadow"
+#ifdef __clang__
+#pragma GCC diagnostic ignored "-Wunknown-pragmas"
+#endif
+#pragma GCC diagnostic ignored "-Wpragmas"
+#pragma GCC diagnostic ignored "-Wdeprecated-register"
+#pragma GCC diagnostic ignored "-Wshorten-64-to-32"
+#pragma GCC diagnostic ignored "-Wunused-local-typedefs"
+#pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
+#include <boost/geometry.hpp>
+#include <boost/geometry/geometries/point.hpp>
+#include <boost/geometry/geometries/box.hpp>
+#include <boost/geometry/geometries/register/point.hpp>
+#include <boost/geometry/geometries/register/box.hpp>
+#include <boost/geometry/index/rtree.hpp>
+#pragma GCC diagnostic pop
+
+// Make Boost Geometry aware of our LatLng type
+BOOST_GEOMETRY_REGISTER_POINT_2D(mbgl::LatLng, double, boost::geometry::cs::cartesian, longitude, latitude)
+BOOST_GEOMETRY_REGISTER_BOX(mbgl::LatLngBounds, mbgl::LatLng, sw, ne)
+
+namespace mbgl {
+
+class AnnotationTileLayer;
+
+class PointAnnotationImpl {
+public:
+    using Map = std::map<AnnotationID, std::shared_ptr<PointAnnotationImpl>>;
+    using Tree = boost::geometry::index::rtree<std::shared_ptr<const PointAnnotationImpl>, boost::geometry::index::rstar<16, 4>>;
+
+    PointAnnotationImpl(const AnnotationID, const PointAnnotation&);
+
+    LatLngBounds bounds() const;
+    void updateLayer(const TileID&, AnnotationTileLayer&) const;
+
+    const AnnotationID id;
+    const PointAnnotation point;
+};
+
+}
+
+// Tell Boost Geometry how to access a std::shared_ptr<mbgl::PointAnnotation> object.
+namespace boost {
+namespace geometry {
+namespace index {
+
+template <>
+struct indexable<std::shared_ptr<const mbgl::PointAnnotationImpl>> {
+    using result_type = const mbgl::LatLng&;
+    inline const mbgl::LatLng& operator()(const std::shared_ptr<const mbgl::PointAnnotationImpl>& v) const {
+        return v->point.position;
+    }
+};
+
+} // end namespace index
+} // end namespace geometry
+} // end namespace boost
+
+#endif
diff --git a/src/mbgl/annotation/shape_annotation_impl.cpp b/src/mbgl/annotation/shape_annotation_impl.cpp
new file mode 100644
index 0000000000..e17509d669
--- /dev/null
+++ b/src/mbgl/annotation/shape_annotation_impl.cpp
@@ -0,0 +1,137 @@
+#include <mbgl/annotation/shape_annotation_impl.hpp>
+#include <mbgl/annotation/annotation_manager.hpp>
+#include <mbgl/annotation/annotation_tile.hpp>
+#include <mbgl/util/geojsonvt/geojsonvt_convert.hpp>
+#include <mbgl/util/constants.hpp>
+#include <mbgl/util/string.hpp>
+#include <mbgl/style/style.hpp>
+#include <mbgl/style/style_bucket.hpp>
+#include <mbgl/style/style_layer.hpp>
+
+namespace mbgl {
+
+using namespace mapbox::util::geojsonvt;
+
+ShapeAnnotationImpl::ShapeAnnotationImpl(const AnnotationID id_,
+                                         const ShapeAnnotation& shape_,
+                                         const uint8_t maxZoom)
+: id(id_),
+  layerID("com.mapbox.annotations.shape." + util::toString(id)),
+  shape(shape_),
+  shapeTiler(([&] {
+    const double baseTolerance = 3;
+    const uint16_t extent = 4096;
+    const double tolerance = baseTolerance / ((1 << maxZoom) * extent);
+
+    ProjectedGeometryContainer rings;
+    std::vector<LonLat> points;
+
+    for (size_t i = 0; i < shape.segments[0].size(); ++i) { // first segment for now (no holes)
+        const double constraintedLatitude = ::fmin(::fmax(shape.segments[0][i].latitude, -util::LATITUDE_MAX), util::LATITUDE_MAX);
+        points.push_back(LonLat(shape.segments[0][i].longitude, constraintedLatitude));
+    }
+
+    ProjectedFeatureType featureType;
+
+    if (shape.styleProperties.is<FillProperties>()) {
+        featureType = ProjectedFeatureType::Polygon;
+
+        if (points.front().lon != points.back().lon || points.front().lat != points.back().lat) {
+            points.push_back(LonLat(points.front().lon, points.front().lat));
+        }
+    } else {
+        featureType = ProjectedFeatureType::LineString;
+    }
+
+    ProjectedGeometryContainer ring = Convert::project(points, tolerance);
+    rings.members.push_back(ring);
+
+    std::vector<ProjectedFeature> features;
+    features.push_back(Convert::create(Tags(), featureType, rings));
+    return features;
+  })(), maxZoom, 4, 100, 10) {}
+
+void ShapeAnnotationImpl::updateStyle(Style& style) {
+    if (style.getLayer(layerID))
+        return;
+
+    ClassProperties paintProperties;
+
+    if (shape.styleProperties.is<LineProperties>()) {
+        const LineProperties& lineProperties = shape.styleProperties.get<LineProperties>();
+        paintProperties.set(PropertyKey::LineOpacity, ConstantFunction<float>(lineProperties.opacity));
+        paintProperties.set(PropertyKey::LineWidth, ConstantFunction<float>(lineProperties.width));
+        paintProperties.set(PropertyKey::LineColor, ConstantFunction<Color>(lineProperties.color));
+    } else if (shape.styleProperties.is<FillProperties>()) {
+        const FillProperties& fillProperties = shape.styleProperties.get<FillProperties>();
+        paintProperties.set(PropertyKey::FillOpacity, ConstantFunction<float>(fillProperties.opacity));
+        paintProperties.set(PropertyKey::FillColor, ConstantFunction<Color>(fillProperties.fill_color));
+        paintProperties.set(PropertyKey::FillOutlineColor, ConstantFunction<Color>(fillProperties.stroke_color));
+    }
+
+    std::map<ClassID, ClassProperties> shapePaints;
+    shapePaints.emplace(ClassID::Default, std::move(paintProperties));
+    std::unique_ptr<StyleLayer> shapeLayer = std::make_unique<StyleLayer>(layerID, std::move(shapePaints));
+    shapeLayer->type = (shape.styleProperties.is<LineProperties>() ? StyleLayerType::Line : StyleLayerType::Fill);
+
+    util::ptr<StyleBucket> shapeBucket = std::make_shared<StyleBucket>(shapeLayer->type);
+    shapeBucket->name = shapeLayer->id;
+    shapeBucket->source = AnnotationManager::SourceID;
+    shapeBucket->source_layer = shapeLayer->id;
+    if (shape.styleProperties.is<LineProperties>()) {
+        shapeBucket->layout.set(PropertyKey::LineJoin, ConstantFunction<JoinType>(JoinType::Round));
+    }
+
+    shapeLayer->bucket = shapeBucket;
+    style.addLayer(std::move(shapeLayer), AnnotationManager::PointLayerID);
+}
+
+void ShapeAnnotationImpl::updateTile(const TileID& tileID, AnnotationTile& tile) {
+    const auto& shapeTile = shapeTiler.getTile(tileID.z, tileID.x, tileID.y);
+    if (!shapeTile)
+        return;
+
+    AnnotationTileLayer& layer = *tile.layers.emplace(layerID,
+        std::make_unique<AnnotationTileLayer>()).first->second;
+
+    for (auto& shapeFeature : shapeTile.features) {
+        FeatureType featureType = FeatureType::Unknown;
+
+        if (shapeFeature.type == TileFeatureType::LineString) {
+            featureType = FeatureType::LineString;
+        } else if (shapeFeature.type == TileFeatureType::Polygon) {
+            featureType = FeatureType::Polygon;
+        }
+
+        assert(featureType != FeatureType::Unknown);
+
+        GeometryCollection renderGeometry;
+        for (auto& shapeGeometry : shapeFeature.geometry) {
+            std::vector<Coordinate> renderLine;
+            auto& shapeRing = shapeGeometry.get<TileRing>();
+
+            for (auto& shapePoint : shapeRing.points) {
+                renderLine.emplace_back(shapePoint.x, shapePoint.y);
+            }
+
+            renderGeometry.push_back(renderLine);
+        }
+
+        layer.features.emplace_back(
+            std::make_shared<AnnotationTileFeature>(featureType, renderGeometry));
+    }
+}
+
+LatLngBounds ShapeAnnotationImpl::bounds() const {
+    LatLngBounds result;
+
+    for (const auto& segment : shape.segments) {
+        for (const auto& point : segment) {
+            result.extend(point);
+        }
+    }
+
+    return result;
+}
+
+}
diff --git a/src/mbgl/annotation/shape_annotation_impl.hpp b/src/mbgl/annotation/shape_annotation_impl.hpp
new file mode 100644
index 0000000000..6e00a50e39
--- /dev/null
+++ b/src/mbgl/annotation/shape_annotation_impl.hpp
@@ -0,0 +1,36 @@
+#ifndef MBGL_SHAPE_ANNOTATION_IMPL
+#define MBGL_SHAPE_ANNOTATION_IMPL
+
+#include <mbgl/annotation/annotation.hpp>
+#include <mbgl/annotation/shape_annotation.hpp>
+#include <mbgl/util/geo.hpp>
+#include <mbgl/util/geojsonvt/geojsonvt.hpp>
+
+#include <string>
+#include <map>
+
+namespace mbgl {
+
+class Style;
+class AnnotationTile;
+
+class ShapeAnnotationImpl {
+public:
+    using Map = std::map<AnnotationID, std::unique_ptr<ShapeAnnotationImpl>>;
+
+    ShapeAnnotationImpl(const AnnotationID, const ShapeAnnotation&, const uint8_t maxZoom);
+
+    LatLngBounds bounds() const;
+    void updateStyle(Style&);
+    void updateTile(const TileID&, AnnotationTile&);
+
+private:
+    const AnnotationID id;
+    const std::string layerID;
+    const ShapeAnnotation shape;
+    mapbox::util::geojsonvt::GeoJSONVT shapeTiler;
+};
+
+}
+
+#endif
diff --git a/src/mbgl/map/live_tile.cpp b/src/mbgl/map/live_tile.cpp
deleted file mode 100644
index f7a70f7d46..0000000000
--- a/src/mbgl/map/live_tile.cpp
+++ /dev/null
@@ -1,61 +0,0 @@
-#include <mbgl/map/live_tile.hpp>
-#include <mbgl/util/constants.hpp>
-
-namespace mbgl {
-
-LiveTileFeature::LiveTileFeature(FeatureType type_, GeometryCollection geometries_,
-                                 std::unordered_map<std::string, std::string> properties_)
-    : type(type_),
-      properties(properties_),
-      geometries(geometries_) {}
-
-mapbox::util::optional<Value> LiveTileFeature::getValue(const std::string& key) const {
-    auto it = properties.find(key);
-    if (it != properties.end()) {
-        return mapbox::util::optional<Value>(it->second);
-    }
-    return mapbox::util::optional<Value>();
-}
-
-LiveTileLayer::LiveTileLayer() {}
-
-void LiveTileLayer::prepareToAddFeatures(size_t count) {
-    features.reserve(features.size() + count);
-}
-
-void LiveTileLayer::addFeature(util::ptr<const LiveTileFeature> feature) {
-    features.push_back(std::move(feature));
-}
-
-void LiveTileLayer::removeFeature(util::ptr<const LiveTileFeature> feature) {
-    for (auto it = features.begin(); it != features.end(); ++it) {
-        if (feature == *it) {
-            features.erase(it);
-            return;
-        }
-    }
-}
-
-LiveTile::LiveTile() {}
-
-void LiveTile::addLayer(const std::string& name, util::ptr<LiveTileLayer> layer) {
-    layers.emplace(name, std::move(layer));
-}
-
-void LiveTile::removeLayer(const std::string& name) {
-    layers.erase(name);
-}
-
-util::ptr<GeometryTileLayer> LiveTile::getLayer(const std::string& name) const {
-    return getMutableLayer(name);
-}
-
-util::ptr<LiveTileLayer> LiveTile::getMutableLayer(const std::string& name) const {
-    auto layer_it = layers.find(name);
-    if (layer_it != layers.end()) {
-        return layer_it->second;
-    }
-    return nullptr;
-}
-
-}
diff --git a/src/mbgl/map/live_tile.hpp b/src/mbgl/map/live_tile.hpp
deleted file mode 100644
index 5b4c2d1c16..0000000000
--- a/src/mbgl/map/live_tile.hpp
+++ /dev/null
@@ -1,55 +0,0 @@
-#ifndef MBGL_MAP_LIVE_TILE
-#define MBGL_MAP_LIVE_TILE
-
-#include <map>
-#include <unordered_map>
-
-#include <mbgl/map/geometry_tile.hpp>
-
-namespace mbgl {
-
-class LiveTileFeature : public GeometryTileFeature {
-public:
-    LiveTileFeature(FeatureType, GeometryCollection,
-                    std::unordered_map<std::string, std::string> properties = {{}});
-
-    FeatureType getType() const override { return type; }
-    mapbox::util::optional<Value> getValue(const std::string&) const override;
-    GeometryCollection getGeometries() const override { return geometries; }
-
-private:
-    FeatureType type = FeatureType::Unknown;
-    std::unordered_map<std::string, std::string> properties;
-    GeometryCollection geometries;
-};
-
-class LiveTileLayer : public GeometryTileLayer {
-public:
-    LiveTileLayer();
-
-    void prepareToAddFeatures(size_t count);
-    void addFeature(util::ptr<const LiveTileFeature>);
-    void removeFeature(util::ptr<const LiveTileFeature>);
-    std::size_t featureCount() const override { return features.size(); }
-    util::ptr<const GeometryTileFeature> getFeature(std::size_t i) const override { return features[i]; }
-
-private:
-    std::vector<util::ptr<const LiveTileFeature>> features;
-};
-
-class LiveTile : public GeometryTile {
-public:
-    LiveTile();
-
-    void addLayer(const std::string&, util::ptr<LiveTileLayer>);
-    void removeLayer(const std::string&);
-    util::ptr<GeometryTileLayer> getLayer(const std::string&) const override;
-    util::ptr<LiveTileLayer> getMutableLayer(const std::string&) const;
-
-private:
-    std::map<std::string, util::ptr<LiveTileLayer>> layers;
-};
-
-}
-
-#endif
diff --git a/src/mbgl/map/live_tile_data.cpp b/src/mbgl/map/live_tile_data.cpp
index 15a1c6a3f4..f6e14fad10 100644
--- a/src/mbgl/map/live_tile_data.cpp
+++ b/src/mbgl/map/live_tile_data.cpp
@@ -1,5 +1,5 @@
 #include <mbgl/map/live_tile_data.hpp>
-#include <mbgl/map/live_tile.hpp>
+#include <mbgl/annotation/annotation_tile.hpp>
 #include <mbgl/style/style_layer.hpp>
 #include <mbgl/map/source.hpp>
 #include <mbgl/text/collision_tile.hpp>
@@ -12,7 +12,7 @@
 using namespace mbgl;
 
 LiveTileData::LiveTileData(const TileID& id_,
-                           const LiveTile* tile_,
+                           std::unique_ptr<AnnotationTile> tile_,
                            Style& style_,
                            const SourceInfo& source_,
                            std::function<void()> callback)
@@ -24,7 +24,7 @@ LiveTileData::LiveTileData(const TileID& id_,
                  style_.layers,
                  state,
                  std::make_unique<CollisionTile>(0, 0, false)),
-      tile(tile_) {
+      tile(std::move(tile_)) {
     state = State::loaded;
 
     if (!tile) {
diff --git a/src/mbgl/map/live_tile_data.hpp b/src/mbgl/map/live_tile_data.hpp
index c6507bbc3e..6be9fa73df 100644
--- a/src/mbgl/map/live_tile_data.hpp
+++ b/src/mbgl/map/live_tile_data.hpp
@@ -9,12 +9,12 @@ namespace mbgl {
 class Style;
 class SourceInfo;
 class WorkRequest;
-class LiveTile;
+class AnnotationTile;
 
 class LiveTileData : public TileData {
 public:
     LiveTileData(const TileID&,
-                 const LiveTile*,
+                 std::unique_ptr<AnnotationTile>,
                  Style&,
                  const SourceInfo&,
                  std::function<void ()> callback);
@@ -30,7 +30,7 @@ private:
     TileWorker tileWorker;
     std::unique_ptr<WorkRequest> workRequest;
     bool parsing = false;
-    const LiveTile* tile;
+    std::unique_ptr<AnnotationTile> tile;
 };
 
 }
diff --git a/src/mbgl/map/map.cpp b/src/mbgl/map/map.cpp
index 2fce648f2e..4b6c9c8085 100644
--- a/src/mbgl/map/map.cpp
+++ b/src/mbgl/map/map.cpp
@@ -341,10 +341,6 @@ const LatLng Map::latLngForPixel(const vec2<double> pixel) const {
 
 #pragma mark - Annotations
 
-void Map::setDefaultPointAnnotationSymbol(const std::string& symbol) {
-    data->getAnnotationManager()->setDefaultPointAnnotationSymbol(symbol);
-}
-
 double Map::getTopOffsetPixelsForAnnotationSymbol(const std::string& symbol) {
     return context->invokeSync<double>(&MapContext::getTopOffsetPixelsForAnnotationSymbol, symbol);
 }
@@ -374,12 +370,12 @@ void Map::removeAnnotation(AnnotationID annotation) {
 }
 
 void Map::removeAnnotations(const AnnotationIDs& annotations) {
-    data->getAnnotationManager()->removeAnnotations(annotations, getMaxZoom());
+    data->getAnnotationManager()->removeAnnotations(annotations);
     update(Update::Annotations);
 }
 
-AnnotationIDs Map::getAnnotationsInBounds(const LatLngBounds& bounds, const AnnotationType& type) {
-    return data->getAnnotationManager()->getAnnotationsInBounds(bounds, getMaxZoom(), type);
+AnnotationIDs Map::getPointAnnotationsInBounds(const LatLngBounds& bounds) {
+    return data->getAnnotationManager()->getPointAnnotationsInBounds(bounds);
 }
 
 LatLngBounds Map::getBoundsForAnnotations(const AnnotationIDs& annotations) {
diff --git a/src/mbgl/map/source.cpp b/src/mbgl/map/source.cpp
index 0f42796e41..49e1d81610 100644
--- a/src/mbgl/map/source.cpp
+++ b/src/mbgl/map/source.cpp
@@ -23,6 +23,7 @@
 #include <mbgl/map/vector_tile_data.hpp>
 #include <mbgl/map/raster_tile_data.hpp>
 #include <mbgl/map/live_tile_data.hpp>
+#include <mbgl/annotation/annotation_tile.hpp>
 #include <mbgl/style/style.hpp>
 #include <mbgl/gl/debugging.hpp>
 
@@ -295,7 +296,7 @@ TileData::State Source::addTile(MapData& data,
             new_tile.data = tileData;
         } else if (info.type == SourceType::Annotations) {
             new_tile.data = std::make_shared<LiveTileData>(normalized_id,
-                data.getAnnotationManager()->getTile(normalized_id), style, info, callback);
+                	data.getAnnotationManager()->getTile(normalized_id), style, info, callback);
         } else {
             throw std::runtime_error("source type not implemented");
         }
@@ -515,15 +516,6 @@ bool Source::update(MapData& data,
     return allTilesUpdated;
 }
 
-void Source::invalidateTiles(const std::unordered_set<TileID, TileID::Hash>& ids) {
-    cache.clear();
-    for (const auto& id : ids) {
-        tiles.erase(id);
-        tile_data.erase(id);
-    }
-    updateTilePtrs();
-}
-
 void Source::invalidateTiles() {
     cache.clear();
     tiles.clear();
diff --git a/src/mbgl/map/source.hpp b/src/mbgl/map/source.hpp
index 421f819640..fceb5962a4 100644
--- a/src/mbgl/map/source.hpp
+++ b/src/mbgl/map/source.hpp
@@ -77,7 +77,6 @@ public:
                 TexturePool&,
                 bool shouldReparsePartialTiles);
 
-    void invalidateTiles(const std::unordered_set<TileID, TileID::Hash>&);
     void invalidateTiles();
 
     void updateMatrices(const mat4 &projMatrix, const TransformState &transform);
diff --git a/src/mbgl/util/geo.cpp b/src/mbgl/util/geo.cpp
index 21a591cb43..035eb2d20a 100644
--- a/src/mbgl/util/geo.cpp
+++ b/src/mbgl/util/geo.cpp
@@ -1,4 +1,5 @@
 #include <mbgl/util/geo.hpp>
+#include <mbgl/util/constants.hpp>
 #include <mbgl/map/tile_id.hpp>
 
 #include <cmath>
@@ -11,6 +12,17 @@ LatLng::LatLng(const TileID& id) {
     latitude = 180.0 / M_PI * std::atan(0.5 * (std::exp(n) - std::exp(-n)));
 }
 
+vec2<double> LatLng::project() const {
+    // Clamp to the latitude limits of Mercator.
+    const double constrainedLatitude = ::fmin(::fmax(latitude, -util::LATITUDE_MAX), util::LATITUDE_MAX);
+
+    // Project a coordinate into unit space in a square map.
+    const double sine = std::sin(constrainedLatitude * M_PI / 180.0);
+    const double x = longitude / 360.0 + 0.5;
+    const double y = 0.5 - 0.25 * std::log((1.0 + sine) / (1.0 - sine)) / M_PI;
+    return { x, y };
+}
+
 LatLngBounds::LatLngBounds(const TileID& id)
     : sw(TileID{ id.z, id.x, id.y + 1, id.sourceZ }),
       ne(TileID{ id.z, id.x + 1, id.y, id.sourceZ }) {
diff --git a/src/mbgl/util/worker.cpp b/src/mbgl/util/worker.cpp
index b238071bc5..71c930b4ef 100644
--- a/src/mbgl/util/worker.cpp
+++ b/src/mbgl/util/worker.cpp
@@ -3,7 +3,7 @@
 #include <mbgl/util/work_request.hpp>
 #include <mbgl/platform/platform.hpp>
 #include <mbgl/map/vector_tile.hpp>
-#include <mbgl/map/live_tile.hpp>
+#include <mbgl/annotation/annotation_tile.hpp>
 #include <mbgl/util/pbf.hpp>
 #include <mbgl/renderer/raster_bucket.hpp>
 
@@ -38,7 +38,7 @@ public:
         }
     }
 
-    void parseLiveTile(TileWorker* worker, const LiveTile* tile, std::function<void (TileParseResult)> callback) {
+    void parseLiveTile(TileWorker* worker, const AnnotationTile* tile, std::function<void (TileParseResult)> callback) {
         try {
             callback(worker->parse(*tile));
         } catch (const std::exception& ex) {
@@ -71,7 +71,7 @@ std::unique_ptr<WorkRequest> Worker::parseVectorTile(TileWorker& worker, std::st
     return threads[current]->invokeWithCallback(&Worker::Impl::parseVectorTile, callback, &worker, data);
 }
 
-std::unique_ptr<WorkRequest> Worker::parseLiveTile(TileWorker& worker, const LiveTile& tile, std::function<void (TileParseResult)> callback) {
+std::unique_ptr<WorkRequest> Worker::parseLiveTile(TileWorker& worker, const AnnotationTile& tile, std::function<void (TileParseResult)> callback) {
     current = (current + 1) % threads.size();
     return threads[current]->invokeWithCallback(&Worker::Impl::parseLiveTile, callback, &worker, &tile);
 }
diff --git a/src/mbgl/util/worker.hpp b/src/mbgl/util/worker.hpp
index 3ecc402ad2..4e63b45abf 100644
--- a/src/mbgl/util/worker.hpp
+++ b/src/mbgl/util/worker.hpp
@@ -12,7 +12,7 @@ namespace mbgl {
 
 class WorkRequest;
 class RasterBucket;
-class LiveTile;
+class AnnotationTile;
 
 class Worker : public mbgl::util::noncopyable {
 public:
@@ -43,7 +43,7 @@ public:
 
     Request parseLiveTile(
         TileWorker&,
-        const LiveTile&,
+        const AnnotationTile&,
         std::function<void (TileParseResult)> callback);
 
     Request redoPlacement(