[OSM-dev] Simplified street-network

[marcus.wolschon at googlemail.com]

Hello everyone,

did anyone else ever work on simplifying the polylines for
low zoom -rendering or similar purposes?
Any algorithms, websites or books that may help me?

While importing a map into Traveling Salesman I am currently
generating 3 additional filtered maps.
1. These maps contain only the most important highway-types (trivial)
2a. Any 2 Ways sharing a common node but having the same name or ref
    are joined (works fine, helps with step 3)
2b. Any 2 ways that are parallel all the time, very close together
    and have the same name or ref are joined (this does NOT work yet)
2c. Ignore 2a and 2b if there is a relation with type=street or
type=combined_way
    and combine its elements with rule 2a and 2b instead of looking at the
name/ref.
3. The resulting polylines are simplified with 2 rules:
3a. Any node who's removal causes a course-error of less then X is removed
    (this eleminates unimportant nodes in long curves and straight lines)
3b. Any node that is less then Y in distance from the last node is removed.

These steps are executed in an online-algorithm (and need to be executed
that
way) = one new way-entity at a time. So at all times I have the full and
simplified
map as it looked after the last step and 1 new way-entity.

My problem lies with adding the new rule 2b here.
Having this would make the map render much faster (less ways to render)
and even look nicer (because these 2 usually overlap in rendering).

I can already determine if 2 ways A and B are parallel for all the length
of one
of them and sort the nodes of B into the other way A.
However usual motorways are made up of segments and I'm having quite a hard
time comming up with a rule to still make rule 2b work for the next segment
that attached to B as the end/start -node of B may not be an inner node in
A
and no longer the first or last node.

Requirements:
* The user may import a map of any size with already having a map of any
size.
* Any means "way more data then there will ever be main-memory".
Thus I cannot first collect all ways, grouped them by street and then
simplify.
* map-import must be fast. This is something the user is supposed to do
every
  now and then. For small imported maps he is supposed to do this before or
  while driving (get the latest map-updates for the part of the world
between
  start and target = never route using a map that is half a year old).
* the map is stored in osmbin-format. There is no way I can force an
end-user to
  install a postgis or mysql-gis on his nettop/laptop/carpc/smartphone just
to
  have a navigator while the commercial ones work on off-the-shelf
cellphones.
* no native code (sorry, can't use your super-cool graph-library
cross-platform)


Marcus