What's the best way to calculate a 3D (or n-D) centroid?

Question

As part of a project at work I have to calculate the centroid of a set of points in 3D space. Right now I'm doing it in a way that seems simple but naive -- by taking the average of each set of points, as in:

centroid = average(x), average(y), average(z)

where x, y and z are arrays of floating-point numbers. I seem to recall that there is a way to get a more accurate centroid, but I haven't found a simple algorithm for doing so. Anyone have any ideas or suggestions? I'm using Python for this, but I can adapt examples from other languages.

Answer 1

Nope, that is the only formula for the centroid of a collection of points. See Wikipedia: http://en.wikipedia.org/wiki/Centroid

Answer 2

You got it. What you are calculating is the centroid, or the mean vector.

Answer 3

A "more accurate centroid" I believe centroid is defined the way you calculated it hence there can be no "more accurate centroid".

Answer 4

you can use increase accuracy summation - Kahan summation - was that what you had in mind?

Answer 5

Yes that is the correct formula.

If you have a large number of points you can exploit the symmetry of the problem (be it cylindrical, spherical, mirror). Otherwise, you can borrow from statistics and average a random number of the points and just have a bit of error.

Answer 6

Potentially more efficient: if you're calculating this multiple times, you can speed this up quite a bit by keeping two standing variables

N  # number of points
sums = dict(x=0,y=0,z=0)  # sums of the locations for each point

then changing N and sums whenever points are created or destroyed. This changes things from O(N) to O(1) for calculations at the cost of more work every time a point is created, moves, or is destroyed.