Как я могу найти координату центра в MGLMultiPolygonFeature

Question

Я использую iOS Mapbox SDK, и мне нужно найти координату центра в многоугольнике, потому что я хочу добавить маркер в координате центра.Как я могу сделать это в 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

Решение зависит от ваших требований.Если требуется, чтобы центр находился внутри многоугольника, решение, предложенное Полом ван Розендалем, является идеальным.
Однако во многих случаях лучше, если центр также может находиться за пределами многоугольника.Подумайте, например, о многоугольнике, который выглядит как почти замкнутое кольцо.В этом случае может быть более естественным то, что центр находится примерно в центре кольца, а центр вычисляется как центр тяжести многоугольника.
В цитируемом посте вики: эта ссылка обсуждает, как ее вычислить, и показывает ряд реализаций на разных языках.
Я перевел версию Java на Swift и добавил пример:

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

Я думаю, вы можете найти всю необходимую вам информацию здесь: https://blog.mapbox.com/a-new-algorithm-for-finding-a-visual-center-of-a-polygon-7c77e6492fbc

Он связан с модулем javascript (https://github.com/mapbox/polylabel),, но я надеюсь, что вы легко можете переписать его.

Чтобы не просто разделять URL, я скопировал наиболее релевантную информацию из поста в блоге здесь:

Основной принцип - использование четырех деревьев. Основная идея - рекурсивное деление двумерного пространства на четыре.Квадранты. Начните с нескольких больших ячеек, покрывающих многоугольник. Рекурсивно подразделяйте их на четыре меньшие ячейки, исследуя центры ячеек как кандидатов и отбрасывая ячейки, которые не могут содержать решение лучше, чем тот, который мы уже нашли.

Как мы узнаем, можно ли отбросить ячейку? Рассмотрим образец квадратной ячейки над многоугольником:

Если мы знаем расстояние от ячейкиот центра до многоугольника (dist выше), любая точка внутри ячейки не может иметь большее расстояние до многоугольника, чем dist + radius, где radius - это радиус ячейки.что потенциальный максимум ячейки меньше или равен лучшему расстоянию ячейки, которое мы уже обработали (с заданной точностью), мы можем безопасно отбросить ячейку.

Чтобы это предположение работало правильно для любой ячейки независимо от того,их центр находится внутри многоугольника или нет, нам нужно использовать расстояние со знаком до многоугольника - положительное, если точка находится внутри многоугольника, и отрицательное, если оно находится снаружи.