2726

7
+2  Q:

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

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.

+4  A:

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

A:

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

A:

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

+2  A:

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

No, I'm not looking to get a more accurate sum before averaging, if that's what you mean. I was just wondering if I was calculating the centroid correctly. Thanks, though -- I hadn't even heard of this.
+1  A:

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.

Specifically, the mean of a random subset of points is an unbiased estimator of the mean of the whole group.
+1  A:

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.

+1  A:
So if I understand this correctly, if the centroid is like the mean of a linear set, does convex hull peeling get you the point analogous to the median?