4 ms·

The Isochrones [0] mentioned in the article include basically all the necessary information. I guess a capable GPU-shader programmer could easily render the dis

by qznc 9y ago

The Isochrones [0] mentioned in the article include basically all the necessary information. I guess a capable GPU-shader programmer could easily render the distortion in real time. (Hint Hint Hacker News for a cool weekend project) [0] https://www.mapbox.com/bites/00156/#10/51.6840/-0.1480 https://www.mapbox.com/bites/00156/#10/51.6840/-0.1480

nemetroid 9y ago
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?
- qznc 9y ago
  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?
- TFortunato 9y ago
  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!
  - ballenarosada 9y ago
    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.
    - TFortunato 9y ago
      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 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!
toomuchtodo 9y ago
> (Hint Hint Hacker News for a cool weekend project) I would love an HN/GoFundMe or Patreon mashup, where people could take on cool hacks in a thread that readers are willing to support. I have zero free time at this point in my life, but would be willing to throw some money at folks who do have free time and skills.
- ximeng 9y ago
  If you are serious you could include some contact details in your profile and a statement for the kind of projects you're interested in funding.
microcolonel 9y ago
That looks pretty good! It seems like the transformation could be done reasonably quickly, maybe with a two-component texture (not sure how efficient texture sampling in vertex shaders is), in the vertex shader(s) in that Mapbox GL instance right after the basic projection. I might give this a go. It might get a bit weird around the edges though, gotta make sure to have a margin of additional geometry.
- nhaehnle 9y ago
  > not sure how efficient texture sampling in vertex shaders is On a modern GPU, it's basically just as efficient as in pixel shaders, with two caveats: 1. If you want mip-mapping, you have to do LOD calculations yourself, which is likely a bit slower. (Not an issue in what you have in mind.) 2. There are questions around the locality of your memory accesses. As long as you lay out your vertices more or less along a space-filling curve (which is a good idea for grids anyway, due to vertex reuse) you should be mostly fine. Obviously the details will vary depending on the exact architecture.

by qznc 9y ago

nemetroid 9y ago

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?

qznc 9y ago
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?
TFortunato 9y ago
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!
- ballenarosada 9y ago
  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.
  - TFortunato 9y ago
    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 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!

toomuchtodo 9y ago

> (Hint Hint Hacker News for a cool weekend project) I would love an HN/GoFundMe or Patreon mashup, where people could take on cool hacks in a thread that readers are willing to support. I have zero free time at this point in my life, but would be willing to throw some money at folks who do have free time and skills.

ximeng 9y ago
If you are serious you could include some contact details in your profile and a statement for the kind of projects you're interested in funding.

microcolonel 9y ago

That looks pretty good! It seems like the transformation could be done reasonably quickly, maybe with a two-component texture (not sure how efficient texture sampling in vertex shaders is), in the vertex shader(s) in that Mapbox GL instance right after the basic projection. I might give this a go. It might get a bit weird around the edges though, gotta make sure to have a margin of additional geometry.

nhaehnle 9y ago
> not sure how efficient texture sampling in vertex shaders is On a modern GPU, it's basically just as efficient as in pixel shaders, with two caveats: 1. If you want mip-mapping, you have to do LOD calculations yourself, which is likely a bit slower. (Not an issue in what you have in mind.) 2. There are questions around the locality of your memory accesses. As long as you lay out your vertices more or less along a space-filling curve (which is a good idea for grids anyway, due to vertex reuse) you should be mostly fine. Obviously the details will vary depending on the exact architecture.