How Can I find the center coordinate in a MGLMultiPolygonFeature

Question

I'm using iOS Mapbox SDK and I need to find the center coordinate in a polygon because I want to add a marker in the center coordinate. How can I do this in Swift?

func drawPolygonFeature(shapes: [MGLShape & MGLFeature]) {
    let shapeSource = MGLShapeSource(identifier: "MultiPolygonShapeSource", shapes: shapes, options: nil)

    let lineStyleLayer = MGLLineStyleLayer(identifier: "LineStyleLayer", source: shapeSource)
    lineStyleLayer.lineColor = NSExpression(forConstantValue: UIColor.purple)
    lineStyleLayer.lineOpacity = NSExpression(forConstantValue: 0.5)
    lineStyleLayer.lineWidth = NSExpression(forConstantValue: 4)

    DispatchQueue.main.async(execute: {[weak self] in
        guard let self = self else { return }
        self.mapView.style?.addSource(shapeSource)
        self.mapView.style?.addLayer(lineStyleLayer)

        let multiPolygonFeature = shapes.first as? MGLMultiPolygonFeature
        if let centerCoordinate = multiPolygonFeature?.polygons.first?.coordinate {
            self.mapView.centerCoordinate = centerCoordinate
            // but centerCoordinate var does not contain the center coordinate
        }
    })
}

Answer 1

A solution depends on your requirements. If it is required that the center is within the polygon, the solution provided by Paul van Roosendaal is perfect.
However, in many cases it is better if the center can also be outside of the polygon. Think, e.g. of a polygon that looks like a nearly closed ring. In this case, it may be more natural that the center is roughly in the center of the ring, and the center is computed as the centroid of the polygon.
In the cited wiki post, this reference discusses how to compute it, and shows a number of implementations in different languages.
I have translated the Java version into Swift, and added an example:

func signedPolygonArea(polygon: [CGPoint]) -> CGFloat {
    let nr = polygon.count
    var area: CGFloat = 0
    for i in 0 ..< nr {
        let j = (i + 1) % nr
        area = area + polygon[i].x * polygon[j].y
        area = area - polygon[i].y * polygon[j].x
    }
    area = area/2.0
    return area
}

func polygonCenterOfMass(polygon: [CGPoint]) -> CGPoint {
    let nr = polygon.count
    var centerX: CGFloat = 0
    var centerY: CGFloat = 0
    var area = signedPolygonArea(polygon: polygon)
    for i in 0 ..< nr {
        let j = (i + 1) % nr
        let factor1 = polygon[i].x * polygon[j].y - polygon[j].x * polygon[i].y
        centerX = centerX + (polygon[i].x + polygon[j].x) * factor1
        centerY = centerY + (polygon[i].y + polygon[j].y) * factor1
    }
    area = area * 6.0
    let factor2 = 1.0/area
    centerX = centerX * factor2
    centerY = centerY * factor2
    let center = CGPoint.init(x: centerX, y: centerY)
    return center
}

let point0 = CGPoint.init(x: 1, y: 1)
let point1 = CGPoint.init(x: 2, y: 2)
let point2 = CGPoint.init(x: 4, y: 3)
let point3 = CGPoint.init(x: 4, y: 5)
let point4 = CGPoint.init(x: 3, y: 4)
let point5 = CGPoint.init(x: 2, y: 4)
let point6 = CGPoint.init(x: 1, y: 5)
let point7 = CGPoint.init(x: 3, y: 2)
let polygon = [point0, point1, point2, point3, point4, point5, point6, point7]
let center = polygonCenterOfMass(polygon: polygon)

Answer 2

I think you can find all the info you need here: https://blog.mapbox.com/a-new-algorithm-for-finding-a-visual-center-of-a-polygon-7c77e6492fbc

It links to a javascript module (https://github.com/mapbox/polylabel), but I expect you can easily rewrite it.

For sake of not just sharing a url I copied the most relevant info from the blog post here:

The basic principle is use of quadtrees. The main concept is to recursively subdivide a two-dimensional space into four quadrants. Start with a few large cells covering the polygon. Recursively subdivide them into four smaller cells, probing cell centers as candidates and discarding cells that can’t possibly contain a solution better than the one we already found.

How do we know if a cell can be discarded? Let’s consider a sample square cell over a polygon:

If we know the distance from the cell center to the polygon (dist above), any point inside the cell can’t have a bigger distance to the polygon than dist + radius, where radius is the radius of the cell. If that potential cell maximum is smaller than or equal to the best distance of a cell we already processed (within a given precision), we can safely discard the cell.

For this assumption to work correctly for any cell regardless whether their center is inside the polygon or not, we need to use signed distance to polygon — positive if a point is inside the polygon and negative if it’s outside.