Wednesday, July 20, 2011

Calculating the Centroids: Correction

This is due to David and what he does is really very clever. There seemed to be an anomalous behavior in just taking the mean (+ some additional details) for the coordinate of the parent node.

Let me first describe what the problem is and how Dave's solution comes to the rescue.

So suppose you have 3 points A, B, C on the equator with longitudes -80, -170 & 160 respectively. If you take their simple mean that comes out to be -30.
Take the point diametrically opposite this point on the globe, that comes out to be 150. Now 150 and -30 are two potential candidates for being chosen as the mean. We choose 150 because the sum of its distances to A, B and C along the equator is minimum.
Notice that neither of 150 and -30 are between the child nodes on the map. This is weird and in fact this is wrong.

So here is what Dave does. Take the three points and find the points which have the maximum separation between them. This maximum separation is always less than 180 for otherwise we could have reached from the other side of the globe.

Finding this pair of maximally separated points is computationally expensive via the naive method of pairwise comparison. O(n^2)

In our example the pair of maximally separated points are -80 and 160, the distance between them being 130.
Now transform the axis such that -80 is the new origin. The transformed coordinates become 0, 90 and 120. These are obtained by adding to 0 the distances to the respective points A, B and C

Once this is done calculate the mean. The mean is 70. Transforming back you get -150.
This is between the child nodes.

Take another example, rather a difficult one. (-20, -180, 30). Now let's apply this new method on it.
Take the maximally separated nodes. -20 and -180. Now transform -20 -> 0, -180 -> 160 and 30 -> -50.
Take the mean.
110/3 = 36.66
Transforming back we get, -56.66.

Indeed the required angle.


In planar geometry this point would be the centroid of the polygon formed by the child nodes. I believe though it is only my intuition that this is also the centroid of the spherical polygon formed on the surface of the earth by the tip nodes.

No comments:

Post a Comment