notion parallax

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!

lists to trees

Gennaro asked me about data structures to contain a tree for his genetic programming in GC (little does he know how clueless I am about data structures), and I recommended a nested list.

It seemed sensible to me, so I set about turning a nested list into a tree diagram, and I have to admit that there were moments that I doubted the plausibility of it, but it turned out OK in the end!

The way to look at it seems to be that you work from the outside in. The outside set of brackets is the root, and then everything inside that is a terminal, with this rule re-applied recursively for each time another list is found.

You can read this diagram either way, as turning a list into a tree, or the other way arround.

GAs are cool apparently

 I’m reviewing the applications for SG at the moment, and there are an awful lot of people wanting to do some sort of optimisation based proposal at the workshop.Whilst I’m very keen for people to peruse this avenue, there seems to be a general level of naivety about how much a GA, or any other algorithmic improvement method can actually do to help in the design process. Hopefully this will subside as the wave of euphoria passes.My current feeling is that optimisation is essentially trivial, and evaluation is where we ought to be directing our efforts. There are kinds of things that could be evaluated and then given that feedback, we could use our really quite advanced problem solving brains to deal with all the little problems that are flagged up by the evaluation routines.That rant over with, I’m quite optimistic about the general state of the SG applications, there is some interesting stuff in there that I hope will get shared with the wider world as soon as possible!