16
May
2009
centroid of points on the surface of a sphere
I was sat in the airport after SG, trying to figure out the logistics of the tutor group meeting up. Where would be the most logical place to go?
As I’d been thinking about geeky problems for the preceding week, my brain was fixed into that way of thinking, and started on trying to figure out the centroid of people’s locations on the globe. This one seemed easy until I tried to think it through and realised that there was a big stick in the spokes.
The seam!
Put more generally, assume that you have some points distributed randomly on the surface of a sphere, how do you find find the centroid of them?
Put into a (vaguely) real world example, my friends live all over the world, assuming that we all have amphibious planes as our only means of transport, where is the most convenient place for us all to meet up? (assuming that we also have a thunderbirds style floating island, and air space rights to everywhere etc.)
The obvious answer is that we map it back onto a plane, and then solve it on the plane, but this only works if people are clustered in one place.
As I’m British, I’ve got a British map with UK in the centre. If I lived in Alaska (hi Sarah P), and my friend lives in Vladivostock, (simple case with only 2 points) I can draw a line between us and we should meet at the midpoint of this line. simple.
No, that point is in Norway somewhere, which is clearly wrong as the centroid of our positions is somewhere in the Aleutian isles or in the Bearing straights. So what’s the solution?
I found this PDF outining a solution, but it doesn’t make much sense, and it’s both a bit mathematical, and a bit clunky. Is there an elegant solution out there?
I’ve come up with a few possible solutions, I’d be interested to see what other people think.
solution 1 – pair wise great circle solving
With a given set of points on a sphere, pick 2, draw two complementary arcs through these points with the centre of the sphere as the centre of the circle.
Pick the shorter of the two arcs and draw a point at it’s midpoint.
remove the two initial points from the working set, and replace it with the new one
repeat until the centroid is found.
As I have no other way of testing this method, i can’t be sure if it’s accuarate. Does anyone have any insight?
Here’s some GC script that produces a centroid point.
The only condition is that the points must lie on the surface of the a sphere.
transaction script "make a centroid"
{
Point workingSet = point01; //make the random points be our set of points to test
Point finalPt = new Point("CentroidPt");// get a point ready to give to the world
while (workingSet.Count >= 2) //once we are down to two at the top, one will come out of the bottom
{
int indexEnum = Series(0,workingSet.Count-1,1); //
int indexOne = indexEnum[Random(workingSet.Count)]; //this section makes sure we have picked
indexEnum = RemoveAt(indexEnum,indexOne); //two unique points from the set
int indexTwo = indexEnum[Random(workingSet.Count)]; //
//set a workign plane based on those points
Plane tempPlane = new Plane().ByOriginXYPoints(baseCS, workingSet[indexOne], workingSet[indexTwo]);
//draw two arcs through the points with the centre as the centre of the earth
double theAng = Angle(baseCS,workingSet[indexOne], workingSet[indexTwo]);
Arc tempArc1 = new Arc();
tempArc1.ByCenterRadiusSweepAngle(baseCS, tempPlane, 10, 0, theAng);
Arc tempArc2 = new Arc();
tempArc2.ByCenterRadiusSweepAngle(baseCS, tempPlane, 10, theAng, 360-theAng);
//test to see which arc is shortest
Point childPt = new Point();
if (tempArc1.Length
I can’t see any problems with this except that it’s not going to be very fast, and it relies heavily on geometry libraries. There must be a faster way, although I think this is likely to be the most easily understood solution.
solution 2 - mean vector
I think this will work, but I’m not sure, there are some indications from a GC model that there is something fish about it, and I can think of situations where it might fail.
From the centre of the earth to each person is a vector (x,y,z) which will have a length of 1 if we assume that the earth has a radius of 1.
if we round up all the vectors and average their x,y and z components then we’ll get a vector that has the right direction.
If we then unitise it so that it’s length is 1 again, it’s endpoint will be the meeting place.
solution 3 – manipulation of lat and long
I’m still working on this, but there must be a way to give back both values for the average latitude, but I’m not sure how at the moment. I can make it work fine for 2 points on a circle, but 3 goes wrong.
There will be updates to this post over the next week. hopefully a solution, and definitely lots more diagrams and gct sketches.
if you’ve got anything to pitch in, please comment, if i don’t solve this soon, it may lead to divorce!
probably, is a very good problem for a GA.
find a centroid point to minimize the distance between a set of points.
do you think is possible?
best
c.
I’m not sure about using a GA to solve it. It strikes me as a very trivial problem that a GA would probably take a very long time, and give a response with an unacceptably low accuracy.
The main obstacle to the use of a GA however is working out a good evaluation function, and that is pretty tightly entwined with the main thrust of this problem.
If you can figure out a way to measure the distance from any point on a sphere to any other point on a sphere, along the sphere’s surface, then you’ve probably solved 90% of the problem (I’ll look into this as it might be fruitful!)
However, what might be more useful for a GA would be the second part of this problem.
If we limit ourselves to to the lattice of possible air traffic routes, and put a cost on each edge of how much the ticket would be, then the GA could munch through the possible total costs of getting everyone to the same place at the same time.
The evaluation function would be much simpler, as we would have a graph. I’m not sure if it’d be directed or not as the costs to travel one way might not be the same as the other way.
any thoughts?
Flora Dilys Salim at 21:56 on 23 May
well, apart from distance… there are other factors to be considered… such as shortest path and travel time… maybe try to find the average mid point of multiple traveling salesmen will work?
get everyone’s current position and find the shortest travel route of every person through everyone else’s positions in the sphere, and then calculate the average mid point?
this is a rough hypothesis and i’m not sure if anyone has done it this way
I think that if you made the problem relate to real world infrastructure, then it could be reduced to a graph with weighted edges, then the brute force way of solving it would be to find the shortest (or cheapest, depending on how the edges are weighted) route for all people to each node, and then just pick the one with the lowest total cost. More slowly:
for each nodefor each person
find the shortest path to the node
add that cost to a total for the group
next person
next node
pick cheapest node
Actually doing would be interesting though, you could hang off the airline booking infrastructure, in which case time would become an issue too, then one node might be cheaper for a particular set of dates, and another for another.
To solve it geometrically, I’m pretty sure that it’ll require some slightly more advanced maths than i have at my immediate disposal
I guess the “infrastructure approach” solution is much more feasible and applicable than a pure geometrical solution
It is not as straightforward – and optimising the algorithm might be a challenge too.
The reason one has difficulty in defining the centroid of a set of points on the surface of a sphere is that, unlike the situation in Euclidean space, on the surface of a sphere the concept of centroid is not well defined. In particular it is often not unique.
On the face of it here is a perfectly reasonable definition of the S-centroid. Treat each point as a point in 3 dimensional Euclidean space. Find the 3-centroid in the standard way. Now take the line from the center of the sphere to this point and continue it until it intersects the surface of the sphere. Define this point to be the S-centroid we are looking for. In many cases this will give a reasonable answer, which may not always be entirely what we expect, but is fairly self consistent.
However, consider the case where the set consists of just two points, which happen to be at the poles. Then any point on the equator is a candidate for the S-centroid. Contrarywise, consider a set of points equi-distributed around the equator. Then either pole is a candidate for the S-centroid. Now take the whole surface of the sphere. What is its cewntroid? Why any point is just as good as any other! This is a fairly catastrophic state of affairs.
What characterises these sets of points is that their 3-dimensional centroid is exactly the center of the sphere. Therefore, I cannot join the center of the sphere to the 3-dimensional centroid and project it onto the surface of the sphere to obtain the S-centroid. There is no unique way to do this.
Indeed, any set of points for which the normal 3-centroid is the center of the sphere will not have a unique S-centroid as defined above. This does not mean we cannot seek another definition, but it does focus our attention where it should be, viz. the problem is the concept, not how we should compute the answer.
As Einstein once said regarding travelling at the speed of light. “Ïf the answer doesn’t make sense you are asking the wrong question!”
Thanks for that Antonia, I had considered the non uniqueness problem as I was spinning through the possibilities in my head, but I hadn’t taken it to it’s proper conclusion that it would be a problem that applied to all situations. I suppose that’s the difficulty of trying to do geometry while cooking.
I think that solving it in 3space and then projecting that point onto the surface of the sphere would probably be the most lightweight and robust solution.
Actually given that the sphere is a constant distance from the centre, a projection isn’t necessary, just a vector through the point would do the job!
Yes Ben, by “project” I did indeed mean just extend the vector to the surface of the sphere.
Here is another thought. If we picture the Universe as the surface of a 4-sphere expanding in time (which is probably wrong but is pretty much the picture of a finite but unbounded universe that I grew up with) and the galaxies are uniformly distributed on the surface of this 4-sphere, then (as above) the concept of the “center of mass of the universe” is badly defined. Indeed any point is just as good as any other point as a candidate! I am not sure how this centroid idea relates to the big bang point, but it is certainly food for thought?
Hope I am not too late with the solution here.
This is for the purely geometric solution, not the infrastructure one.
Basically what you want to do is find the average of the latitude and longitude. But because these are periodic variables, you will get the wrong answer if you average them (the average of 10 degrees and 350 degrees will come out at 180 not the 0 degrees you want). So we can use sine to map the angle into a periodic graph using this relationship:
angle = inverse-tan[ (sine angle) / (cosine angle) ]
The steps are:
A. Find the average of sin(angle)
B. Find the average of cosine(angle)
C. The average angle is inverse-tan( A / B)
So if you are at 30 and I am at 350 degrees (average should be 10 degrees) :
A = sin(30) + sin(350) / 2 = 0.163
B = cosine(30) + cosine(350) / 2 = 0.925
C = inv-tan(0.163/0.925) = 10
If you are using a sphere you should be able to calculate the latitude and longitude this way.
re: Ben
Problem with solution 1: If you were doing the same incremental approach on the plane, you would do a weighted sum at each step rather than always average (the point that was the result of averaging two points would have twice as weight as a normal point). If you simply average, it will be too close to the last point that you considered.
However, on the sphere it gets very interesting. If they are close enough to approximate a plane, incremental weighted average works. However, if three points were on the equator, what you propose works (always average) in a weird way.
Problem with solution 2: You have to find it on the surface. Looking up Slerp vs Lerp might help.
Problem with averaging lat – long: no different than the flattened map, lat and long are the 2D coordinates on the flattened map. If you also make top continue at bottom and left continue at right, it becomes a torus. Not a sphere.
I wish there was an easy solution to this. Here’s what you have been looking for:
http://www.math.ucsd.edu/~sbuss/ResearchWeb/spheremean/index.html
Hope this helps.
http://www.geomidpoint.com/calculation.html is what you’re looking for, with good examples and explanations. The basic answer is to convert to polar coordinates, average the points, and then convert back to lat/long.