views:

2726

answers:

7

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

deemer
A: 

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

Dima
A: 

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

Corporal Touchy
+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.
Marcel Levy
+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.
Gregg Lind
+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.

Gregg Lind
+1  A: 
AlejoHausner
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?
Marcel Levy