How making an ISS clock turns into researching an optimization problem involving spherical Voronoi diagrams…

A few years ago, I got seriously interested in amateur radio and satellites. I would often haul out a small Yagi antenna and my trusty Kenwood TH-D7A and try to talk to other hams by bouncing signals off the various satellites which acted as amateur radio repeaters. During that time, I wrote a Python version of G3RUH’s Plan-13 algorithm for predicting satellite locations. Eventually, I converted that code to C++ and made an Arduino/Gameduino version that I called “Angst”.

But there were a number of problems with it as a general project. Most notably, it utilized some special hardware which made it more expensive than I would like, and it required an external display. I suppose I could have found a small composite display, but one serious issue remained: there was no simple way to update the orbital elements that are used to predict the satellite locations. The ISS is particularly problematic, since it is in low earth orbit and frequently fires its engines to boost it to a higher orbit, which is not something that can be accounted for statically.

But in the years since I did that project, the ESP8266 has taken the world by storm. Not only is it cheap (I got some WeMos D1 Mini clones for less than $5 shipped from China) but it is faster (an 80Mhz 32 bit processor) and most importantly includes WiFi.

For the last couple of days, I’ve been tinkering my old Plan-13 code together with some new code written especially for the ESP8266 to create a “clock” that will automatically tell me the position of the ISS and details about the next pass. The nice thing is that since the ESP8266 has WiFi, it can update itself automatically. Right now, I have code running that contacts, finds the latest orbital elements, predicts the next three passes, and then enters a loop where it shows the current position of the ISS every five seconds. Right now, it just echoes that information out on the serial line, but eventually I’ll get a tiny TFT or LED display to display the live information:

But just seeing the latitude and longitude of the “sub satellite” point didn’t really help me know where the satellite was in its orbit. Sure, I could (and probably will) make a little graphical display for the gadget sooner or later, but I thought it might be nice if I could have it tell me when it was passing close to certain major cities. To give this a try, I found a list of world cities and their coordinates and population, and selected the top fifty cities of the world and within the United States (make one hundred cities total) and then when I do a prediction, quickly compute the distance and bearing to each of the cities and display the closest one. And that works, and doesn’t take too much time. You can see in the run above that the closest city was Honolulu.

But, I noticed a problem.

If you imagine that the earth is a sphere, and imagine that the each city is a point on the surface which you can think of as a seed. If you collect all points on the sphere that are closest (in the great circle) sense to that point than any other seed, you end up with the globe being divided up into a number of regions, each bounded by arcs of a great circle. If you took the same computer and math classes as me, you can recognize this as a “spherical voronoi diagram”. You can read about them here where I swiped the illustration from. Here is the Voronoi diagram of the earth with seeds at each of the World Airports:

You’ll notice something: the regions are widely varying in size. If I had loaded my ISS code with these locations, it would spend a lot of time talking about how it is thousands of miles from some remote airport in the middle of the Pacific, but when it was flying over the United States, it would rapidly shift from region to region. Indeed, because population centers are often close, it might be fairly rare for it to be closest to New York City, even though it is perhaps an obvious landmark, more obvious than the smaller ones that surround it. It might also be the case that if you have two population centers which are fairly close to one another, that approaching from one side would be masked by the other city.

Ideally, we’d like a collection of cities which:

  • are well known
  • divide the globe into a number of Voronoi regions which are nearly the same size
  • and where shape of the Voronoi regions are not too lopsided, so the cities are near the center of a roughly circular region

I haven’t figured out how to do this yet, but I’m betting that I am going to use some kind of genetic algorithm/simulated annealing approach. Stay tuned.

Musing about a 2 dimensional delta robot…

First of all, if anyone is still swinging by this blog, yes, I’m still alive. While I haven’t exactly been prolific in my leisure activities, they haven’t stopped entirely. I worked on some simple embedded development for the 1K code challenge, which you can see on my page, and which hopefully I’ll write up here. I’ve got some additional projects in mind, so perhaps with a little extra effort on my part I’ll be getting back to more regular entries.

One of the things that has been kicking around in my head is to “make something that moves.” In particular, I’ve long been interested in gadgets like plotters, 3d printers, laser cutters and CNC machines. A few months ago on a whim, I ordered a CNC shield and Arduino so that I could begin to think about maybe creating a project which drives some steppers around to trace some pattern. I doubt that I possess the skills or know-how to do a good job of making a real CNC machine, but I kind of liked the idea of making a plotter. I started to work on the basic mechanical design of a simple 2D gantry. But frankly, I began to balk at the idea. You need two different sets of parallel ways, which seemed large and cumbersome, and each axis is different.

At the Maker Faire I had observed some simpler setups which generally go under the name of “Drawbots”. You can see an excellent write-up here on the “Death To Sharpie” page. I liked the idea a lot: it uses two steppers and the setups for each are symmetric. Each one winds and unwinds a chain, and the pen is suspended at the intersection of the two chains. In this incarnation, the pen doesn’t even have a separate control: it is simply drug around the poster board, leaving a trail wherever it goes. Pretty cool! I must admit though, I thought his software setup (laptop + Raspberry Pi + Arduino?) was a little complicated, and I’d probably enjoy working on the control software anyway.

But I was discussing this with my constant lunchtime companion Tom, discussing catenary curves and the like, and he basically said “why don’t you just use solid arms, making a 2D analog of the 3D delta robots you see in 3D printers?”

An awesome idea! One of the cool things about constructing a delta robot is that it consists of three essentially identical pillars. Yes, the three pillars all move slightly differently, but that is really a software issue, not a hardware one. A few moments of thought and I realized that you could make a pretty spiffy 2D version, and the math would actually be pretty easy.

So, in between tasks, I worked out the necessary quadratic equations, and created this gif that will demonstrate how the motion works.

The work space is the unit-size gray square at the bottom. It is bracketed by two rails, each of length two. Each has a carriage which runs along its side, and pins one end of a fixed arm (again, of unit length) which are held together in the center by a pin, which is where the pen will be. As you drive the red and green carriages back and forth, the intersection moves back and forth. It isn’t hard to see that the pen can reach any location in the unit square at the bottom.

It isn’t quite as compact as the typical drawbot, but I can’t help but think there are some serious mechanical advantages to setting up a bot this way. It should not be very hard to create an interpreter that could run on the Arduino that would take a small subset of G code and some basic scaling and rate information, and drive a pair of steppers to create this kind of a robot. I’ve never written code exactly like this before. It should be fun.

Stay tuned.