10

I would like to know how exactly QGIS Geometry tools -> polygon centroid is calculating the point coordinates. For example does it divide the boarder of the polygon into small points, take two pairs of two points (length and width) with maximum distance and take the crossing of these two lines as the centroid?

13

If QGIS is computing the centroid with GEOS which is a JTS port then the algorithm is this http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/algorithm/CentroidArea.html. About the theory there is a link in the javadoc into http://www.faqs.org/faqs/graphics/algorithms-faq/, see section 2.02: How can the centroid of a polygon be computed?.

The centroid (a.k.a. the center of mass, or center of gravity) of a polygon can be computed as the weighted sum of the centroids of a partition of the polygon into triangles. The centroid of a triangle is simply the average of its three vertices, i.e., it has coordinates (x1 + x2 + x3)/3 and (y1 + y2 + y3)/3. This suggests first triangulating the polygon, then forming a sum of the centroids of each triangle, weighted by the area of each triangle, the whole sum normalized by the total polygon area. This indeed works, but there is a simpler method: the triangulation need not be a partition, but rather can use positively and negatively oriented triangles (with positive and negative areas), as is used when computing the area of a polygon. This leads to a very simple algorithm for computing the centroid, based on a sum of triangle centroids weighted with their signed area. The triangles can be taken to be those formed by any fixed point, e.g., the vertex v0 of the polygon, and the two endpoints of consecutive edges of the polygon: (v1,v2), (v2,v3), etc. The area of a triangle with vertices a, b, c is half of this expression: (b[X] - a[X]) * (c[Y] - a[Y]) - (c[X] - a[X]) * (b[Y] - a[Y]);

Code available at ftp://cs.smith.edu/pub/code/centroid.c (3K).
Reference: [Gems IV] pp.3-6; also includes code.

It seems to me that the method is accurate. If you want to check how the coordinate values are used and if there can be rounding errors etc. you can have a look at the source code of JTS or GEOS.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.