Hacker News Reader

Comment by nemetroid | Hacker News Reader

The problem isn't in getting the data for the transformation but to figure out which transformation to use. It's not possible to do in the general case, imagine e.g. an infinitely quick circle line. Where do you put the part of the map that's inside the circle?

View on HN

I think as far as figuring out the transformation to use on the a generic map I would:

0) ignore stuff like "infinitely quick" since that isn't realistic for what we are doing :-)

1) For the map I am displaying, pick a handful of points of interest to hse as controls, as well as my current location.

2) Use existing data we already have for stuff like direction routing to get travel times between all the pairs in our points of interest.

3) Draw a weighted graph, where each vertex is one of our points of interest and each edge is weighted by travel time. The initial position of each point should be it's geographic position, but we can then use an existing graph layout algorithm that uses an energy-based method (e.g. pretend the edges are springs) to deform the graph. This way each point will end up with its distance being proportional to travel time.

4) Using initial points as our input control points, and their location in the graph as output cobtrol points, use any number of image warping algorithms put there to calculate our warp / morph / deformation field.

5) Apply to initial map image.

I don't know how well it would work in practice but seems like a reasonable first stab at it! :-)

EDIT: Apologies for typo, fat fingers on mobile!

There's no reason your distance graph should correspond to any continuous mapping of the plane. Two distances constrain a third point to one of two spots. Add a third distance and unless you get lucky, there will be no valid corresponding point in the codomain.

That is absolutely true, and I fully admit that there isn't going to be a perfect way to do this unless you are very lucky. I'm only curious if you could use a method like this to make maps like shown above at http://www.spiekermann-wegener.com/mod/time/time_e.htm where it's approximately correct in a somewhat useful way.

My gut says it's probably more realistic to do this for large scale maps (say between major cities, 100s of miles, where distance is pretty proportional to travel time). Once you get down to the city / street level, yeah it probably gets real dicey with high variation in travel speeds depending on the particular road and how routes are laid out, and you just aren't going to get pretty triangles fitting together nicely :-P.

In any case its a fun problem to think about!

Good point.

An infinitely quick circle would reduce to a point. Morphing a 2D map in 3D, I would imagine the inside of the circle like a balloon with the circle as the opening. Reducing that to 2D seems impossible without breaking it somehow.

I guess the problem is worth at least a paper, if not a dissertation. Maybe there is some esoteric math paper in topology which already solved that? Or has proven it impossible?

Reply on news.ycombinator.com