Algorithm for schematizing (metro) maps

Question

This is a long shot, but I thought I might try before starting the dirty work.

I've got a project to build an application which will, for a defined input stations (vertices) and lines (edges), that is, a real map of some public transportation, schematize a given map into a metro map. I've done some research on the problem and it's an NP-complete problem equivalent to the 3-SAT problem. I also have some theoretic ideas on how to generate such a map, but they aren't detailed enough.

What I'm looking for is any other existing solution of this problem, some sort of pseudo-code, some real code in (almost) any other programming language etc, anything that would reduce the time I need to spend working on the algorithm itself, which will in return give me more time to work on other aspects of the application.

If anyone has ever seen anything that can help me, I'd appreciate it very much.

Answer 1

This is just some suggestion with handwaving - take with a pinch of salt.

My notion of a "metro" map is one where lines tend to one of the eight cardinal directions and stations are regularly spaced.

I'm assuming you're trying to convert a set of real coordinates into "metro" coordinates.

I would start with your main route (e.g., a city loop), then incrementally add other routes in order of importance.

For each route you want to find the nearest approximation that uses the fewest number of straight lines travelling in the eight cardinal directions. You might do this by starting with the bounding box for the real coordinates, splitting that into a grid, then finding a "metro" route from grid square to grid square, then successively refining that route to reduce the number of bends without distorting the map too much and without introducing crossings with other routes if at all possible.

Having done that, scale each line so that consecutive stations are the same distance apart on the "metro" view.

My guess is you'll still want to support manual tweaking of the result.

Good luck!

Answer 2

If you google for "metro map layout problem" and "metro map line crossing" you'll find a lot of references, since it has been researched very actively in the past 10 years.

The problem seems no trivial at all, and translating the "artistic" features to mathematical constraints is seemingly one of the most difficult tasks.

Anyway here are a three publications that I found interesting to start with (among many, many others):

Metro Map Layout Using Multicriteria Optimization

Line Crossing Minimization on Metro Maps

The Metro Map Layout Problem

HTH!

Answer 3

Research that's similar to your topic: http://graphics.stanford.edu/papers/routemaps/