Doing the deformation
The Surprisingly Geeky Technical Details
We need to intelligently break up the terrain into patches, so that the deformation within each patch is controlled by nearby stations. This is actually the same problem as 3D texture mapping -- the same process the programmers for Doom and Halo use to paint a skin on a wireframe of 2D surface patches.
Finding Patches
The first step is to find the patches defined by the station locations -- then as the stations move around we can find out how each patch should be deformed. I'll go ahead and show you the answer so you can tell what I'm going on about:
To find the patches, we perform the ritual known as "Delaunay Triangulation." Delaunay's idea was something like this:
- For a given point, draw all the likely triangles involving that point.
- For any such triangle, you can draw a circle going through the three corners. (In geometry class you may have learned, and then forgotten like I did, that this is called the 'circumcircle'). This is in some sense the proposed "neighborhood" of that triangle.
- If that circle includes another point in the graph, you can draw a better triangulation involving the extra point.
- Repeat until all of the graph is covered by triangles and all of their neighborhoods are appropriately minimal.
The rest of it is a clever approach so that you can do this efficiently -- read more here.
I used Mathematica to do the triangulation beforehand, which is very expensive. (By expensive, I mean it takes about a second on my badass computer; but you can conservatively multiply that by a few hundred for a naive Actionscript implementation). In the picture of the triangulation above, points are colored arbitrarily -- the order of triangles is important for calculating the triangulation but meaningless for just using it.
I left the triangulation diagram in as one of the images you can deform -- this makes it obviouls how the texture triangles slide around.
Where to send each point
To deform a station to meet a new metric, I do something like this:
- Draw an arrow from the focus to the destination.
- Strectch that arrow, while keeping it pointed in the same direction, until its length matches the desired "distance" (cost, time, travel distance) metric.
- Then scale and slide around everything so that it fits neatly onto the screen. Edge nodes remain anchored.
- For the clarified map I instead use coordinates pulled from a free version of that map.
Apply Deformation to Bitmap
Think of each triangle as three displacement vectors --a pair that span the sides of the triang and a third that slides it into place. You can see a demo of this in action over here. If we undo that sliding/smushing, we can turn any triangle into a right triangle with base vertex on the origin. Transform that unit triangle forward into the corresponding location on the deformed map, and carry the background bitmap through the transforms -- you get a patch of ground that has been deformed consistently by the poins on its corners.
Preprocessing
I scraped all the relevant data from various websites and wrote a (tautologically) grody but workable perl script to turn it into nice clean XML. This I pulled this into Mathematica for prototyping. (I initially used CSV spat out by perl, but finally I bit the bullet and used Mathematica's brobdignagian XML routines). Mathematica is nice for this because it's interactive, crazy fast, and has a ton of functions. For instance, the Delaunay triangulation is one line long.
Programming
The rest of it was implementation in Flex/Actionscript. With a half-dozen modestly-sized source files, I have a pretty and intuitive interface that runs ubiquitously (only requires the Flash 9 plugin), is reasonably performant and most importantly was rapid to develop. The images (which are huge -- 3000x3000 -- don't hork them from me, they're on Wikipedia) are pulled dynamically from the server, to reduce load time.
Another Interesting Thing Geometry Tells Us
In passing: a natural by-product of the triangulation is the Voronoi diagram. This diagram shows the minimal neighborhood about each point. (That is, each point in a given voronoi cell is closer to that cell's central node than to any other graph node.) I don't do this yet, but you cold imagine coloring neighborhoods by time, or average property value, or average distance from a station (with a blur filter for cosmetics). It's also easy to see how having the neighborhood map could be handy in defining a Bitmap Displacement Filter control bitmap.
Voronoi Diagram for the Geographical Station Locations
Voronoi Diagram for the 'Clarified' (Metro wall map-style) Map