What is the best way to calculate a 3D center (or nD)?

Question

As part of a project at work, I have to calculate the center of gravity of a set of points in three-dimensional space. Right now I'm doing it in a way that seems simple but naive - by averaging 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 remember that there is a way to get a more accurate centroid, but I have not found a simple algorithm for this. Anyone have any ideas or suggestions? I use Python for this, but I can adapt examples from other languages.

Answer 1

No, this is the only formula for the center of gravity of a set of points. See Wikipedia: http://en.wikipedia.org/wiki/Centroid

Answer 2

You vaguely mention "a way to get a more accurate centroid." Perhaps you are talking about a centroid that is not affected by emissions. For example, the average income in the USA is probably very high because a small number of wealthy people very much distort the average; they are "emissions". For this reason, statistics use the median . One way to get the median is to sort the values, and then select the value halfway down the list.

You may be looking for something similar, but for 2D or 3D points. The problem is in 2D and above, you cannot sort. There is no natural order. However, there are ways to get rid of emissions.

One way is to find a convex hull . The convex hull has all points on the “outside” of the set of points. If you do this and throw away points located on the body, you will throw away emissions, and the remaining points will give a more “representative” center of gravity. You can even repeat this process several times, and the result is the same as onion peeling. In fact, this is called "convex flaking of the hull."

Answer 3

In contrast to the general refrain, there are various ways to determine (and calculate) the center of a point cloud. You have already proposed the first and most common solution, and I do not claim that something is wrong with this:

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

The “problem” is that it will “distort” your center point depending on the distribution of your points. If, for example, you assume that all of your points are in a cubic box or some other geometric shape, but most of them fall in the upper half, your center point will also shift in that direction.

Alternatively, you can use the mathematical mean (average of the extrema) in each dimension to avoid this:

middle = middle(x), middle(y), middle(z)

You can use this when you care about the number of points, but more about the global bounding box, because all this is the center of the bounding box around your points.

Finally, you can also use median (the element in the middle) in each dimension:

median = median(x), median(y), median(z)

Now this will do the opposite of middle and actually help you ignore outliers in the point cloud and find the center point based on the distribution of your points.

A more and more reliable way to find a “good” center point may be to ignore the upper and lower 10% in each dimension, and then calculate average or median . As you can see, you can define the center point in different ways. Below I will show you examples of two 2D point clouds based on these suggestions.

The blue dot is the middle (middle) center of gravity. The median is shown in green. The middle is shown in red. In the second image, you will see exactly what I said before: the green dot is “closer” to the densest part of the point cloud, and the red dot is even further away from it, taking into account the extreme edges of the point cloud.

Answer 4

you can use summation of the accuracy of magnification - summation of Kahan - is that what you had in mind?

Answer 5

Potentially more efficient: if you calculate it several times, you can speed it up a bit by storing two constant variables

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

then changing N and amounts when points are created or destroyed. This changes things from O (N) to O (1) for computation, due to more work every time a point is created, moved or destroyed.

Answer 6

"More accurate centroid." I believe that the centroid is determined as you calculated it, so there can be no “more accurate center of gravity”.

Answer 7

Yes, this is the correct formula.

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

Answer 8

Did you understand. What you are calculating is a centroid or middle vector.