# Finding the virtual center of a cloud of points.

Given:

1. (latitude, longitude) points $P_1, P_2,\ldots, P_n$.
2. Presumably, all the points should form a dense cloud. However, noise is possible.

Needed:

• The virtual center of the points.

For instance, 99% of the points may lie within a circle with 1km radius, except for 1% scattered outside that circle at a distance larger than 1km from any point inside the circle. Then this 1% is noise.

Unfortunately, I do not know how to define the noise properly. But the virtual center I am looking for should be close enough to most of the points. If most of the points are close to it, then I do not mind that some be far away.

If it is not too hard, I would like to be able to recognize more than one dense cloud amongst the points. In which case, each cloud could be reduced to its virtual center and thus I will have to find the new virtual super center of the virtual center cloud. That super center is the final result.

I am not a mathematician, so my descriptions are vague. But I am pretty sure that this is a well known problem and it probably has a trivial solution.

Thanks.

P.S.

This question is similar to Detect Abnormal Points in Point Cloud, however, my space is two dimensional, which probably does not matter. Still.

EDIT

The points are indeed on the surface of a sphere, a spheroid actually, Earth more precisely. However, the distance between them is not large enough to take the Earth curveture into account, so it may be safely assume that the surface is flat and longitude is X and latitude is Y.

-
What you could do is find the center of "mass" of the points (assigning them all equal mass, 1 for instance). Then, you look at what are the points that are most distant from that center. And you throw those points out. Everything will depend though on what you understand by "distant". I think a sensible choice would be assuming a multivariate normal distribution of the points and throw out those that are more than $n\sigma$ away from the center ($n$ being 4 for instance). Then recompute the center of mass after you've thrown out those points. – Raskolnikov Sep 14 '12 at 14:42
Could you arrange your reply as an answer? I know wiki helps, still if you could elaborate a bit on multivariate normal distribution that would be great. – mark Sep 14 '12 at 15:26
I don't think my answer really addresses all your issues. It doesn't address the issue of how to distinguish different clouds in the data. – Raskolnikov Sep 14 '12 at 15:46
Yep, it is a problem. – mark Sep 14 '12 at 15:54
Does the LAT/LON indication means that the point are of the surface of a sphere? And the resulting point should also be of the same surface? – enzotib Sep 15 '12 at 5:33

## 2 Answers

Just take the mean. The average of the x coordinates of the points will be the x coordinate of the center, and the average of the y coordinates of the points will be the y coordinate of the center.

-
And then throw out the wild outliers to make that center even more accurate. – Mateen Ulhaq Sep 15 '12 at 4:11
Do you suggest to do it iteratively? Like compute the mean, then throw all that are beyond some threshold, then recompute the mean and continue until there is nothing to throw? – mark Sep 15 '12 at 11:07
But will it work in case of two clouds? In this case the mean should be somewhere in the middle between the two clouds. The problem is that if the threshold is too low, then I might throw away both of the clouds entirely. – mark Sep 15 '12 at 11:08

You should look into clustering algorithms. The easiest one that comes to mind is k-means. Depending on the number of clusters you "seed" you'll get the clusters and their centers. If you do not know the number of clusters (as usually the case), try with different seed numbers and use a metric to decide what number fits best.

-