1

Looking for information on methods or algorithms used to calculate point centroids from polygons across software.

ArcGIS uses a "gravity model" but can someone point me to the math or a paper on the method? This is the best info I can see for Arc but it is not detailed enough.

QGIS uses ???

WhiteBox uses ???

R uses ??

GDAL / OGR uses ??

Grass uses ??

I am not looking for code unless it helps define the algorithm or method utilized. Really looking for citable literature.

For example, for flow direction ArcGIS uses the D8 algorithm and this is based on

Greenlee, D. D. 1987. "Raster and Vector Processing for Scanned Linework." Photogrammetric Engineering and Remote Sensing 53 (10): 1383–1387.

Jenson, S. K., and J. O. Domingue. 1988. "Extracting Topographic Structure from Digital Elevation Data for Geographic Information System Analysis." Photogrammetric Engineering and Remote Sensing 54 (11): 1593–1600.

Looking for similar for centroids. I can use the n vertices method myself in code but want to find out what others use.

  • Note that centroids and label points are different animals. Most of the listed applications are open source, so you could just look at the code. For the black box applications you could use a set of 8-12 well-designed test cases to intuit both the primary and fall-back labeling algorithms. I was even able to intuit 80% of the methodologies of human subjects in some grad research I did in the mid-90s (including the kid who just dropped the label over the closest line to get the extra credit offered by the prof with as little effort as possible). – Vince Sep 27 '14 at 11:42
  • I know I can look at the code but that does not tell you their definitive source. I did some reverse engineering but the same problem as above. Huber did this as well in Arc 3 but you cannot cite from a reverse engineer. – If you do not know- just GIS Sep 27 '14 at 14:55
  • GRASS GIS comes with its own method, see grass.osgeo.org/programming7/… The original algorithm was designed in the '80th and continuously updated. – markusN Sep 29 '14 at 19:42
2

A wiki article Centroid describes a few methods, including this one, which is probably the one used by most GIS tools:

Centroid of polygon

The centroid of a non-self-intersecting closed polygon, defined by n vertices (x0,y0), (x1,y1), ..., (xn−1,yn−1), is the point (Cx, Cy), where

enter image description here enter image description here

and where A is the polygon's signed area,

enter image description here

In these formulas, the vertices are assumed to be numbered in order of their occurrence along the polygon's perimeter, and the vertex (xn, yn) is assumed to be the same as (x0, y0). Note that if the points are numbered in clockwise order the area A, computed as above, will have a negative sign; but the centroid coordinates will be correct even in this case.

It credits Bourke, Paul (July 1997). "Calculating the area and centroid of a polygon".

However, the method has been published long before Bourke. For example, it is presented, in the form of Fortran code, in Baxter, Richard (1976), Computer and Statistical Techniques for Planners. London: Methuen. There, Baxter refers to a 1972 article by Stinton that describes an improvement on the above centroid, one that lies inside the polygon. (The simple centroid, above, can yield a point outside a complex polygon.)

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.