[ios, osx] Holes in polygons

MGLPolygon (and by extension MGLMultiPolygon) now supports interior rings. The data is preserved in feature querying results, and interior rings are respected when adding polygon overlays to the map.

Fixes #1729.

[ios, osx] Updated changelog

7 files changed, 136 insertions, 46 deletions

diff --git a/platform/darwin/src/MGLFeature.mm b/platform/darwin/src/MGLFeature.mm
index 3e60b2061b..066d3609a9 100644
--- a/platform/darwin/src/MGLFeature.mm
+++ b/platform/darwin/src/MGLFeature.mm
@@ -171,33 +171,44 @@ class GeometryEvaluator {
 public:
     MGLShape <MGLFeaturePrivate> * operator()(const mapbox::geometry::point<T> &geometry) const {
         MGLPointFeature *feature = [[MGLPointFeature alloc] init];
-        feature.coordinate = coordinateFromPoint(geometry);
+        feature.coordinate = coordinateFromPointGeometry(geometry);
         return feature;
     }
     
     MGLShape <MGLFeaturePrivate> * operator()(const mapbox::geometry::line_string<T> &geometry) const {
         std::vector<CLLocationCoordinate2D> coordinates;
         coordinates.reserve(geometry.size());
-        std::transform(geometry.begin(), geometry.end(), std::back_inserter(coordinates), coordinateFromPoint);
+        std::transform(geometry.begin(), geometry.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
         
-        return [[MGLPolylineFeature alloc] initWithCoordinates:&coordinates[0] count:coordinates.size()];
+        return [MGLPolylineFeature polylineWithCoordinates:&coordinates[0] count:coordinates.size()];
     }
     
     MGLShape <MGLFeaturePrivate> * operator()(const mapbox::geometry::polygon<T> &geometry) const {
-        // TODO: MGLPolygon doesn’t support holes, so what to do?
-        auto &linearRing = geometry.front();
-        
+        auto &outerRing = geometry.front();
         std::vector<CLLocationCoordinate2D> coordinates;
-        coordinates.reserve(linearRing.size());
-        std::transform(linearRing.begin(), linearRing.end(), std::back_inserter(coordinates), coordinateFromPoint);
+        coordinates.reserve(outerRing.size());
+        std::transform(outerRing.begin(), outerRing.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
+        
+        NSMutableArray *innerPolygons;
+        if (geometry.size() > 1) {
+            innerPolygons = [NSMutableArray arrayWithCapacity:geometry.size() - 1];
+            for (auto iter = geometry.begin() + 1; iter != geometry.end(); iter++) {
+                auto &innerRing = *iter;
+                std::vector<CLLocationCoordinate2D> coordinates;
+                coordinates.reserve(innerRing.size());
+                std::transform(innerRing.begin(), innerRing.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
+                MGLPolygon *innerPolygon = [MGLPolygon polygonWithCoordinates:&coordinates[0] count:coordinates.size()];
+                [innerPolygons addObject:innerPolygon];
+            }
+        }
         
-        return [[MGLPolygonFeature alloc] initWithCoordinates:&coordinates[0] count:coordinates.size()];
+        return [MGLPolygonFeature polygonWithCoordinates:&coordinates[0] count:coordinates.size() interiorPolygons:innerPolygons];
     }
     
     MGLShape <MGLFeaturePrivate> * operator()(const mapbox::geometry::multi_point<T> &geometry) const {
         std::vector<CLLocationCoordinate2D> coordinates;
         coordinates.reserve(geometry.size());
-        std::transform(geometry.begin(), geometry.end(), std::back_inserter(coordinates), coordinateFromPoint);
+        std::transform(geometry.begin(), geometry.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
         
         return [[MGLMultiPointFeature alloc] initWithCoordinates:&coordinates[0] count:coordinates.size()];
     }
@@ -207,7 +218,7 @@ public:
         for (auto &lineString : geometry) {
             std::vector<CLLocationCoordinate2D> coordinates;
             coordinates.reserve(lineString.size());
-            std::transform(lineString.begin(), lineString.end(), std::back_inserter(coordinates), coordinateFromPoint);
+            std::transform(lineString.begin(), lineString.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
             
             MGLPolyline *polyline = [MGLPolyline polylineWithCoordinates:&coordinates[0] count:coordinates.size()];
             [polylines addObject:polyline];
@@ -219,14 +230,25 @@ public:
     MGLShape <MGLFeaturePrivate> * operator()(const mapbox::geometry::multi_polygon<T> &geometry) const {
         NSMutableArray *polygons = [NSMutableArray arrayWithCapacity:geometry.size()];
         for (auto &polygon : geometry) {
-            // TODO: MGLPolygon doesn’t support holes, so what to do?
             auto &linearRing = polygon.front();
-            
             std::vector<CLLocationCoordinate2D> coordinates;
             coordinates.reserve(linearRing.size());
-            std::transform(linearRing.begin(), linearRing.end(), std::back_inserter(coordinates), coordinateFromPoint);
+            std::transform(linearRing.begin(), linearRing.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
+            
+            NSMutableArray *innerPolygons;
+            if (polygon.size() > 1) {
+                innerPolygons = [NSMutableArray arrayWithCapacity:polygon.size() - 1];
+                for (auto iter = polygon.begin() + 1; iter != polygon.end(); iter++) {
+                    auto &innerRing = *iter;
+                    std::vector<CLLocationCoordinate2D> coordinates;
+                    coordinates.reserve(innerRing.size());
+                    std::transform(innerRing.begin(), innerRing.end(), std::back_inserter(coordinates), coordinateFromPointGeometry);
+                    MGLPolygon *innerPolygon = [MGLPolygon polygonWithCoordinates:&coordinates[0] count:coordinates.size()];
+                    [innerPolygons addObject:innerPolygon];
+                }
+            }
             
-            MGLPolygon *polygonObject = [MGLPolygon polygonWithCoordinates:&coordinates[0] count:coordinates.size()];
+            MGLPolygon *polygonObject = [MGLPolygon polygonWithCoordinates:&coordinates[0] count:coordinates.size() interiorPolygons:innerPolygons];
             [polygons addObject:polygonObject];
         }
         
@@ -245,7 +267,7 @@ public:
     }
     
 private:
-    static CLLocationCoordinate2D coordinateFromPoint(const mapbox::geometry::point<T> &point) {
+    static CLLocationCoordinate2D coordinateFromPointGeometry(const mapbox::geometry::point<T> &point) {
         return CLLocationCoordinate2DMake(point.y, point.x);
     }
 };
diff --git a/platform/darwin/src/MGLMultiPoint.h b/platform/darwin/src/MGLMultiPoint.h
index 041c52e8f2..2d6b327086 100644
--- a/platform/darwin/src/MGLMultiPoint.h
+++ b/platform/darwin/src/MGLMultiPoint.h
@@ -17,7 +17,10 @@ NS_ASSUME_NONNULL_BEGIN
  */
 @interface MGLMultiPoint : MGLShape
 
-/** The number of points associated with the shape. (read-only) */
+/** The array of coordinates associated with the shape. */
+@property (nonatomic, readonly) CLLocationCoordinate2D *coordinates NS_RETURNS_INNER_POINTER;
+
+/** The number of coordinates associated with the shape. (read-only) */
 @property (nonatomic, readonly) NSUInteger pointCount;
 
 /**
diff --git a/platform/darwin/src/MGLMultiPoint.mm b/platform/darwin/src/MGLMultiPoint.mm
index a864b7bce7..aaf8447274 100644
--- a/platform/darwin/src/MGLMultiPoint.mm
+++ b/platform/darwin/src/MGLMultiPoint.mm
@@ -14,7 +14,6 @@ mbgl::Color MGLColorObjectFromCGColorRef(CGColorRef cgColor) {
 
 @implementation MGLMultiPoint
 {
-    CLLocationCoordinate2D *_coords;
     size_t _count;
     MGLCoordinateBounds _bounds;
 }
@@ -27,13 +26,13 @@ mbgl::Color MGLColorObjectFromCGColorRef(CGColorRef cgColor) {
     if (self)
     {
         _count = count;
-        _coords = (CLLocationCoordinate2D *)malloc(_count * sizeof(CLLocationCoordinate2D));
+        _coordinates = (CLLocationCoordinate2D *)malloc(_count * sizeof(CLLocationCoordinate2D));
 
         mbgl::LatLngBounds bounds = mbgl::LatLngBounds::empty();
 
         for (NSUInteger i = 0; i < _count; i++)
         {
-            _coords[i] = coords[i];
+            _coordinates[i] = coords[i];
             bounds.extend(mbgl::LatLng(coords[i].latitude, coords[i].longitude));
         }
 
@@ -45,7 +44,7 @@ mbgl::Color MGLColorObjectFromCGColorRef(CGColorRef cgColor) {
 
 - (void)dealloc
 {
-    free(_coords);
+    free(_coordinates);
 }
 
 - (CLLocationCoordinate2D)coordinate
@@ -59,7 +58,7 @@ mbgl::Color MGLColorObjectFromCGColorRef(CGColorRef cgColor) {
 
     assert(_count > 0);
 
-    return CLLocationCoordinate2DMake(_coords[0].latitude, _coords[0].longitude);
+    return CLLocationCoordinate2DMake(_coordinates[0].latitude, _coordinates[0].longitude);
 }
 
 - (NSUInteger)pointCount
@@ -89,7 +88,7 @@ mbgl::Color MGLColorObjectFromCGColorRef(CGColorRef cgColor) {
 
     for (NSUInteger i = range.location; i < range.location + range.length; i++)
     {
-        coords[index] = _coords[i];
+        coords[index] = _coordinates[i];
         index++;
     }
 }
@@ -104,24 +103,16 @@ mbgl::Color MGLColorObjectFromCGColorRef(CGColorRef cgColor) {
     return MGLLatLngBoundsFromCoordinateBounds(_bounds).intersects(MGLLatLngBoundsFromCoordinateBounds(overlayBounds));
 }
 
-- (void)addShapeAnnotationObjectToCollection:(std::vector<mbgl::ShapeAnnotation> &)shapes withDelegate:(id <MGLMultiPointDelegate>)delegate {
+- (mbgl::AnnotationSegments)annotationSegments {
     NSUInteger count = self.pointCount;
-    if (count == 0) {
-        return;
-    }
-    
-    CLLocationCoordinate2D *coordinates = (CLLocationCoordinate2D *)malloc(count * sizeof(CLLocationCoordinate2D));
-    NSAssert(coordinates, @"Unable to allocate annotation with %lu points", (unsigned long)count);
-    [self getCoordinates:coordinates range:NSMakeRange(0, count)];
+    CLLocationCoordinate2D *coordinates = self.coordinates;
     
     mbgl::AnnotationSegment segment;
     segment.reserve(count);
     for (NSUInteger i = 0; i < count; i++) {
         segment.push_back(MGLLatLngFromLocationCoordinate2D(coordinates[i]));
     }
-    free(coordinates);
-    shapes.emplace_back(mbgl::AnnotationSegments {{ segment }},
-                        [self shapeAnnotationPropertiesObjectWithDelegate:delegate]);
+    return { segment };
 }
 
 - (mbgl::ShapeAnnotation::Properties)shapeAnnotationPropertiesObjectWithDelegate:(__unused id <MGLMultiPointDelegate>)delegate {
diff --git a/platform/darwin/src/MGLMultiPoint_Private.h b/platform/darwin/src/MGLMultiPoint_Private.h
index c1f1fa1584..2c1e0b7222 100644
--- a/platform/darwin/src/MGLMultiPoint_Private.h
+++ b/platform/darwin/src/MGLMultiPoint_Private.h
@@ -21,8 +21,8 @@ NS_ASSUME_NONNULL_BEGIN
 - (instancetype)initWithCoordinates:(CLLocationCoordinate2D *)coords count:(NSUInteger)count;
 - (BOOL)intersectsOverlayBounds:(MGLCoordinateBounds)overlayBounds;
 
-/** Adds a shape annotation to the given vector by asking the delegate for style values. */
-- (void)addShapeAnnotationObjectToCollection:(std::vector<mbgl::ShapeAnnotation> &)shapes withDelegate:(id <MGLMultiPointDelegate>)delegate;
+/** Returns the shape’s annotation segments. */
+- (mbgl::AnnotationSegments)annotationSegments;
 
 /** Constructs a shape annotation properties object by asking the delegate for style values. */
 - (mbgl::ShapeAnnotation::Properties)shapeAnnotationPropertiesObjectWithDelegate:(id <MGLMultiPointDelegate>)delegate;
diff --git a/platform/darwin/src/MGLPolygon.h b/platform/darwin/src/MGLPolygon.h
index a12e62b106..e1dc553f30 100644
--- a/platform/darwin/src/MGLPolygon.h
+++ b/platform/darwin/src/MGLPolygon.h
@@ -17,6 +17,17 @@ NS_ASSUME_NONNULL_BEGIN
 @interface MGLPolygon : MGLMultiPoint <MGLOverlay>
 
 /**
+ The array of polygons nested inside the receiver.
+ 
+ The area occupied by any interior polygons is excluded from the overall shape.
+ Interior polygons should not overlap. An interior polygon should not have
+ interior polygons of its own.
+ 
+ If there are no interior polygons, the value of this property is `nil`.
+ */
+@property (nonatomic, nullable, readonly) NS_ARRAY_OF(MGLPolygon *) *interiorPolygons;
+
+/**
  Creates and returns an `MGLPolygon` object from the specified set of
  coordinates.
  
@@ -25,8 +36,21 @@ NS_ASSUME_NONNULL_BEGIN
  @param count The number of items in the `coords` array.
  @return A new polygon object.
  */
-+ (instancetype)polygonWithCoordinates:(CLLocationCoordinate2D *)coords
-                                 count:(NSUInteger)count;
++ (instancetype)polygonWithCoordinates:(CLLocationCoordinate2D *)coords count:(NSUInteger)count;
+
+/**
+ Creates and returns an `MGLPolygon` object from the specified set of
+ coordinates and interior polygons.
+ 
+ @param coords The array of coordinates defining the shape. The data in this
+    array is copied to the new object.
+ @param count The number of items in the `coords` array.
+ @param interiorPolygons An array of `MGLPolygon` objects that define regions
+    excluded from the overall shape. If this array is `nil` or empty, the shape
+    is considered to have no interior polygons.
+ @return A new polygon object.
+ */
++ (instancetype)polygonWithCoordinates:(CLLocationCoordinate2D *)coords count:(NSUInteger)count interiorPolygons:(nullable NS_ARRAY_OF(MGLPolygon *) *)interiorPolygons;
 
 @end
 
diff --git a/platform/darwin/src/MGLPolygon.mm b/platform/darwin/src/MGLPolygon.mm
index 6febf6d81b..5a24cb0791 100644
--- a/platform/darwin/src/MGLPolygon.mm
+++ b/platform/darwin/src/MGLPolygon.mm
@@ -7,10 +7,30 @@
 
 @dynamic overlayBounds;
 
-+ (instancetype)polygonWithCoordinates:(CLLocationCoordinate2D *)coords
-                                 count:(NSUInteger)count
-{
-    return [[self alloc] initWithCoordinates:coords count:count];
++ (instancetype)polygonWithCoordinates:(CLLocationCoordinate2D *)coords count:(NSUInteger)count {
+    return [self polygonWithCoordinates:coords count:count interiorPolygons:nil];
+}
+
++ (instancetype)polygonWithCoordinates:(CLLocationCoordinate2D *)coords count:(NSUInteger)count interiorPolygons:(NSArray<MGLPolygon *> *)interiorPolygons {
+    return [[self alloc] initWithCoordinates:coords count:count interiorPolygons:interiorPolygons];
+}
+
+- (instancetype)initWithCoordinates:(CLLocationCoordinate2D *)coords count:(NSUInteger)count interiorPolygons:(NSArray<MGLPolygon *> *)interiorPolygons {
+    if (self = [super initWithCoordinates:coords count:count]) {
+        if (interiorPolygons.count) {
+            _interiorPolygons = interiorPolygons;
+        }
+    }
+    return self;
+}
+
+- (mbgl::AnnotationSegments)annotationSegments {
+    auto segments = super.annotationSegments;
+    for (MGLPolygon *polygon in self.interiorPolygons) {
+        auto interiorSegments = polygon.annotationSegments;
+        segments.push_back(interiorSegments.front());
+    }
+    return segments;
 }
 
 - (mbgl::ShapeAnnotation::Properties)shapeAnnotationPropertiesObjectWithDelegate:(id <MGLMultiPointDelegate>)delegate {
diff --git a/platform/darwin/test/MGLFeatureTests.mm b/platform/darwin/test/MGLFeatureTests.mm
index d9334c76af..6cf038d4fb 100644
--- a/platform/darwin/test/MGLFeatureTests.mm
+++ b/platform/darwin/test/MGLFeatureTests.mm
@@ -23,10 +23,16 @@
     
     mapbox::geometry::polygon<double> polygon = {
         {
-            { -77.0325453144239, 38.9131982 },
-            { -122.4135302, 37.7757368 },
-            { 77.6368034, 12.9810816 },
-            { -74.2178961777998, -13.15589555 },
+            { 1, 1 },
+            { 4, 1 },
+            { 4, 4 },
+            { 1, 4 },
+        },
+        {
+            { 2, 2 },
+            { 3, 2 },
+            { 3, 3 },
+            { 2, 3 },
         },
     };
     features.emplace_back(polygon);
@@ -52,6 +58,30 @@
     MGLPolygonFeature *polygonShape = (MGLPolygonFeature *)shapes[2];
     XCTAssertTrue([polygonShape isKindOfClass:[MGLPolygonFeature class]]);
     XCTAssertEqual(polygonShape.pointCount, 4);
+    CLLocationCoordinate2D *polygonCoordinates = polygonShape.coordinates;
+    XCTAssertNotEqual(polygonCoordinates, nil);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:polygonCoordinates[0]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(1, 1)]);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:polygonCoordinates[1]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(1, 4)]);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:polygonCoordinates[2]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(4, 4)]);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:polygonCoordinates[3]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(4, 1)]);
+    NS_ARRAY_OF(MGLPolygon *) *interiorPolygons = polygonShape.interiorPolygons;
+    XCTAssertEqual(interiorPolygons.count, 1);
+    MGLPolygon *interiorPolygon = interiorPolygons.firstObject;
+    XCTAssertEqual(interiorPolygon.pointCount, 4);
+    CLLocationCoordinate2D interiorPolygonCoordinates[4];
+    [interiorPolygon getCoordinates:interiorPolygonCoordinates range:NSMakeRange(0, interiorPolygon.pointCount)];
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:interiorPolygonCoordinates[0]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(2, 2)]);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:interiorPolygonCoordinates[1]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(2, 3)]);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:interiorPolygonCoordinates[2]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(3, 3)]);
+    XCTAssertEqualObjects([NSValue valueWithMGLCoordinate:interiorPolygonCoordinates[3]],
+                          [NSValue valueWithMGLCoordinate:CLLocationCoordinate2DMake(3, 2)]);
 }
 
 - (void)testPropertyConversion {