QGIS polygon centriods - How are they created?

Question

I have been using QGIS to analyses spatial data and I created polygon centroids with the vector geometry tools. Now for a report I have to explain how these centroids were created. I have not been able to find an algorithm or an explanation of how QGIS creates centroids, can anyone help?

Answer 1

For general centroid creation, QGIS QgsGeometry functions wrap respective calls to the underlying GEOS library:

• QgsGeometry * QgsGeometry::centroid() (definition) calls GEOSGetCentroid (definition)

• QgsGeometry * QgsGeometry::pointOnSurface() (definition) calls GEOSPointOnSurface (definition)

The pointOnSurface() function is new for QGIS 2.4 and allows a workaround for when GEOSGetCentroid returns a centroid that lies outside the polygon's surface, e.g. as with a 'C'-shaped geometry. Such a result can make the centroid actually appear on the surface of an adjacent polygon.

Note: GEOSPointOnSurface does not 'weight' the point to the center of the polygon's area.

You can see how the pointOnSurface() function is used to provide such a fix with this commit for symbology.

Answer 2

Centroid computation in Qgis are based on the GEOS library. I can then refer you to the the documentation of GEOS itself (http://geos.osgeo.org/doxygen/classgeos_1_1algorithm_1_1Centroid.html) where you can find the basic principle for polygon centroid computation:

Based on the usual algorithm for calculating the centroid as a weighted sum of the centroids of a decomposition of the area into (possibly overlapping) triangles. The algorithm has been extended to handle holes and multi-polygons. See http://www.faqs.org/faqs/graphics/algorithms-faq/ for further details of the basic approach.