计算一个多边形的重心点坐标（准确版）

2019-11-29 13:04:47

主要用途，就是在百度地图上画多边形，然后我们要得到这个多边形的重心。

后来我发现了，百度地图，map对象直接有这个接口。大家可以仔细看下api。

接下来，我们还是要看下这个算法问题。

参考地址 计算一个多边形的重心点坐标



背景介绍与问题分析

在之前的 《如何判断一个多边形是否合法》  一文中有提到，用无人机规划飞行路线前，往往需要框选一个多边形的区域。

而在地图控件上显示这个多边形区域时，往往会遇到这样一个需求：需要把所要测绘的多边形区域移动到地图中心。

实现这个需求的基本思路就是：获取到多边形区域的重心点坐标，然后利用地图控件的 setCenter方法，就可以把地图的显示中心移动到多边形区域重心了。那么问题来了，如何求出一个多边形的重心点坐标呢？

这里所说的重心，也常常叫几何中心

这里首先给出一个公式:

平面多边形 X 可以被剖分为 n个有限的简单图形 X_1,X_2,....X_n，这些简单图形的重心点为 C_1，面积为 A_1，那么这个平面多边形的重心点坐标为 (C_x,C_y)
C_x = \frac{\sum C_{i_x} A_i}{\sum A_i}, C_y = \frac{\sum C_{i_y} A_i}{\sum A_i}

公式参考: 维基百科

一般来说我们可以给多边形进行三角剖分，而 \sum{A_i} 即为多边形的总面积，那么这个公式可以理解为：

多边形重心横坐标 = 多边形剖分的每一个三角形重心的横坐标 * 该三角形的面积之和 / 多边形总面积

多边形重心纵坐标 = 多边形剖分的每一个三角形重心的纵坐标 * 该三角形的面积之和 / 多边形总面积

所以这里就把问题拆分成了三个小问题：

  • 求每个剖分出来的三角形的重心。

  • 求每个剖分出来的三角形的面积。

  • 求多边形的面积。

算法解析

1. 求三角形的重心


三角形重心


三角形的重心：三条中线的交点。其中重心到其中一个顶点的距离是重心到该顶点对边中点的距离的2倍。
即：GC = 2 * GP，也就是说重心坐标在 CP 线段上距离 AB 的中点 P 的 1/3 处。
假设 A,B,C 三点的坐标为：


那么通过简单坐标计算，可以得出其重心坐标为 (x,y)
x = \frac{(x_1+x_2+x_3)}{3} , y = \frac{(y_1+y_2+y_3)}{3}

2. 求三角形面积

计算三角形的面积，我们这里利用 向量积来计算，我们知道平面中的两个向量的叉乘的模等于以这两个向量为边的平行四边形的面积，那么以这个两个向量为边的三角形，则是这个平行四边形的面积的一半。

参考：向量叉积

如上图，已知平面上两点 A:(x_1,y_1),B(x_2,y_2) ，以 A，B和坐标原点 P(0,0) 构成的三角形的面积 S 为：
S=\frac{\vec{PB}\times\vec{PA}}{2} = \frac{x_2y_1 - x_1y_2 }{2}

这里给出运算草稿：


为什么这里我们会以原点作为第三个点构成三角形呢？其实是跟接下来求多边形面积是有关联的。

3. 求多边形的面积

我们在上面给出的求平面多边形重心的公式中有说到，一般我们会把多边形剖分为多个三角形。
那么这个剖分点 P 我们可以设在哪里呢？这里先给出结论：这个剖分点可以设置在多边形的内部，也可以设置到外部。

为什么这个剖分点可以设置到外部呢？我们可以通过简单的三角形情况来推广到多边形的情况。
对于三角形ABC，我们把剖分点设置在其外部 P 的一点上


如果大家还记得 《如何判断一个多边形是否合法》 一文中有讲过向量叉积是有正负之分的，并且根据上面所说的计算三角形面积，那么以 P 为剖分点，通过向量积可以得出这个三角形的面积 A 为：
A = \frac{1}{2}(\vec{PB} \times \vec{PC} + \vec{PC} \times \vec{PA} + \vec{PA} \times \vec{PB})

因为 向量PB 在 向量PA 的顺时针方向，所以 \vec{PA} \times \vec{PB} 的结果是负数的。那么上面的面积计算公式其实就可以理解为：

三角形ABC的面积 = 三角形PBC面积 + 三角形PCA面积 - 三角形PAB面积

假设这四个点的坐标为：P(x_0,y_0), A(x_1,y_1), B(x_2,y_2), C(x_3,y_3)，通过上面的公式进行计算，具体的演算过程我就不给出了，这里直接给出计算结果：
A = x_1y_2-x_2y_1+x_2y_3-x_3y_2+x_3y_1-x_1y_3

我们可以发现，计算结果中没有 x_0,y_0 的项，因为它们在计算过程中给消去了，数学就是这么奇妙！所以我们可以得出一个结论，多边形的面积结果与这个剖分点的位置是无关的。那么为了计算方便，我们当然选择把这个 P 点设置到原点上啦。

那么只要我们知道多边形的每一个顶点，通过原点进行剖分成多个三角形，然后通过向量的叉乘求出每个三角的面积，最后相加，就可以求出多边形的面积了。

示例代码及解析

好了，说到这里，我们已经找到所有满足最开始的计算多边形重心点坐标的所有计算元素了。是时候上代码了，这里构建一个函数calculatePolygonGravityCenter(coordinates: [CLLocationCoordinate2D])，这个函数传入的参数是多边形在地图上的坐标点数组。

func calculatePolygonGravityCenter(coordinates: [CLLocationCoordinate2D]) -> CLLocationCoordinate2D {
    var area = 0.0 // 多边形面积
    var gravityLat = 0.0 // 重心点 latitude
    var gravityLng = 0.0 // 重心点 longitude
    for (index, coordinate) in coordinates.enumerated() {
        // 1
        let lat = coordinate.latitude        let lng = coordinate.longitude        let nextLat = coordinates[(index + 1) % coordinates.count].latitude        let nextLng = coordinates[(index + 1) % coordinates.count].longitude        // 2
        let tempArea = (nextLat * lng - nextLng * lat) / 2.0
        // 3
        area += tempArea        // 4
        gravityLat += tempArea * (lat + nextLat) / 3
        gravityLng += tempArea * (lng + nextLng) / 3
    }
    // 5
    gravityLat = gravityLat / area
    gravityLng = gravityLng / area    
    return CLLocationCoordinate2D(latitude: gravityLat, longitude: gravityLng)}

对应上面代码的注释：

  1. 拿到多边形上连续两个点的坐标，我们可以把 latitude 看做横坐标，longitude 是纵坐标。

  2. 利用向量叉乘计算这两个点与原点组成的三角形的面积。

  3. 所有面积之和得出多边形的面积，就是求公式 C_x = \frac{\sum C_{i_x} A_i}{\sum A_i} 中的 \sum A_i。

  4. (lat + nextLat) / 3 是以这两个点和原点组成的三角形的重心横坐标，这样的累加gravityLat += tempArea * (lat + nextLat) / 3 其实是求公式 C_x = \frac{\sum C_{i_x} A_i}{\sum A_i} 中的 \sum C_{i_x} A_i 的值。

  5. 到这一步就简单了，直接套用公式 C_x = \frac{\sum C_{i_x} A_i}{\sum A_i}。

参考资料

  1. 维基百科-Centroid

  2. 维基百科-叉积

  3. cnblogs-用向量积（叉积）计算三角形的面积和多边形面积

  4. 知乎-两个向量的叉乘为什么是面积

  5. 中国知网-任意多边形匀面重心的计算方法



  • 精彩推荐

  • 2018-08-16 16:10:43

    Laravel 跨域解决方案

    我们在用 laravel 进行开发的时候，特别是前后端完全分离的时候，由于前端项目运行在自己机器的指定端口(也可能是其他人的机器) ， 例如 localhost:8000 , 而 laravel 程序又运行在另一个端口，这样就跨域了，而由于浏览器的同源策略，跨域请求是非法的。其实这个问题很好解决，只需要添加一个中间件就可以了。

  • 2018-08-18 20:30:12

    laravel5.5 路由分割成不同文件

    routes.php/api.php文件用来放置laravel路由，当项目越来越大，相应的路由文件也会越来越多。如果能够将不同功能的路由分割到不同的文件，那么对以后的维护将很有帮助。

  • 2018-08-20 15:26:19

    关于OnTouch 和OnClick同时调用冲突的解决方案

    大家在搞轮播图的时候会碰到这样的情况，点击进入webview界面，长按轮播图停止轮播，手松开图又开始轮播，这里就涉及到了OnTouch 和OnClick同时调用。两者是有冲突的。这里简单介绍，给大家提供思路。

  • 2018-08-20 15:29:11

    揭开RecyclerView的神秘面纱(二)：处理RecyclerView的点击事件

    主要讲述了RecyclerView的基本使用方法，不同的布局管理器而造成的多样化展示方式，展示了数据之后，一般都会与用户进行交互，因此我们需要处理用户的点击事件。在ListView和GridView提供了onItemClickListener这个监听器，然而我们查找RecyclerView的API却没有类似的监听器，因此我们需要自己手动处理它的点击事件。 以下提供两种方法来实现处理RecyclerView点击事件的功能，以下代码均基于上一篇文章的代码做出修改。

  • 2018-08-20 22:58:46

    onInterceptTouchEvent和onTouchEvent调用关系详解 ...

    老实说，这两个小东东实在是太麻烦了，很不好懂，我自己那api文档都头晕，在网上找到很多资料，才知道是怎么回事，这里总结一下，记住这个原则就会很清楚了：

  • 2018-08-23 15:32:18

    map对象拷贝问题

    最后面是使用序列化的方式，发现，更改引用类型的数据的时候，mapNew对象并没有发生变化，所以产生了深拷贝。 上述的工具类，可以实现对象的深拷贝，不仅限于HashMap，前提是实现了Serlizeable接口。

  • 2018-08-24 11:33:17

    总结和分析几种判断 RecyclerView 到达底部的方法

    SwipeRefreshLayout 写一个 RecyclerView 的上下拉 ,里面有一个判断 RecyclerView 是否到达底部的方法 isBottom。我的同事用了这个上下拉之后发现有些小 bug，没考虑周全，譬如各个子项高度不统一的时候，然后我找到原因是因为这个判断上下拉的问题。所以，我就去网上查到几种判断 RecyclerView 到达底部的方法，发现各有千秋。以下的分析都以上一篇文章的 SwipeRecyclerView 为例

  • 2018-08-26 00:18:04

    RecyclerView 图片错位空白的问题

    1.图片错位的原因是因为图片异步记载返回去展示出的问题。图片空白，是item刷新，请求图片时间上的问题。 2。viewHolder.setIsRecyclable(false); 就没有tag，不设置 就有tag，但是有没有没啥区别 设置tag，

  • 2018-08-28 10:00:24

    laravel使用队列的简单步骤

    最近需要导入大量的excel文件，数量达到十万之多。 而我又不想修改服务器的超时时间，因为这样可能影响服务器的堵塞。 而php又没有很好的异步。 后来发现了令laravel最为骄傲的部分，队列。具体文档参考下方链接。