Yesterday, Amy was asking if there was a library for drawing curved lines between two points on a map. She wants to use this for her travel posts, which say for example "Tokyo to Boston". We noticed that Facebook draws curved lines when they show a planned trip. Martijn was able to figure out how to reproduce this on Facebook consistently. You have to start by creating a "checkin" post, then add a "traveling to" activity to it. Notice that the line from Portland to Seattle is curved rather than straight, although it doesn't strictly follow a Great Circle line either.
I liked this idea, and realized that my own travel posts would benefit from images as well, so I set to work adding this to the library that I use to generate the maps for my posts. Before, my posts just look like this. Wouldn't this look better with a map?
My static maps are generated using Atlas, a service I wrote for handling all the geo stuff on my website. The static map generation is actually a surprisingly simple chunk of code, which assembles all the necessary map tiles and then draws points and lines on top of them using PHP GD and ImageMagick.
The first step was to figure out how to draw curved lines. There was more to it than I originally anticipated. I knew roughly the shape of the curve I wanted, and after researching a bit, determined that a Quadratic Bézier Curve would give me the shape that I want.
A Quadratic Bézier Curve differs from a standard one in that only one control point (P1 in the image above) is used instead of two. Luckily, the PHP ImageMagick library has a function to draw that curve. If I use a control point at the midpoint of the start and end of each leg, I'll get a nice symmetric curve. I can vary the height of the curve by using a control point farther away from the line connecting the two points. Here's approximately what I'm going for, where A and B are the start and end points of the line segment, and P is the control point.
Given A and B, I can find the mid-point M easily. Half the distance is d, so I know one side of the triangle, and I choose the angle alpha. It's been a long time since I've had to use any trig, so my memory of all this is rusty, but I did remember that it should be possible to find point P given one angle and one side of a right triangle. It took a while to dig up all the identities and formulas for this. Ultimately this stackexchange answer explained things well enough for me to reverse engineer a generic formula out of it.
This means I can now vary the angle alpha to adjust how steep to make the curve. This translates into the following ImageMagick PHP code.
$draw->pathStart();
$draw->pathMoveToAbsolute($A['x'],$A['y']);
$draw->pathCurveToQuadraticBezierAbsolute(
$P['x'], $P['y'],
$B['x'], $B['y']
);
$draw->pathFinish();
We start at point A, then move through point P to land at B. With an angle of 25 degrees, this gives a pretty great looking curve!
Once I started running this code for other trips from various points on the globe, I immediately ran into some interesting issues. It turns out these curves look best when the horizontal curves go upwards and the vertical curves go to the right, and when there are multiple hops, the lines must not overlap. Here are some images from my library with curves I'm relatively happy with.
It took quite a bit of trial and error to determine the rules for making these render properly. The main trick is this: If the line is wider than it is tall, then draw the line from left to right. If the line is taller than it is wide, then draw from top to bottom. ("Draw from left to right" means choosing the leftmost point as point A in the equation above.)
This rule ends up with pretty good results in most cases, as you can see above. However there are still a couple of cases I'm not 100% happy with, although I can't quite come up with a rule to fix them so I'm going to leave them as is for now.
I'm reasonably happy with the results regardless that I'm going to leave it alone for now. If you have any thoughts on fixing it, you're welcome to submit a pull request to Atlas!
If you want to use this yourself, you're welcome to run the Atlas API on your own server, or just copy the code and use it as a library! To generate these curves, pass a parameter bezier=25 into the request when you are generating a line between two points.
Now my itinerary posts look a lot better!
