Archive for the 'spatial' Category

Published by breki on 28 Nov 2009

Kosmos: Preview Of SVG Support

Some time ago I wrote about experimenting with Cairo drawing engine to render maps. The basic idea was to use Cairo to render SVG map files which can then be manually post-processed using some vector graphics editor like Inkscape.

Unfortunately I worked on lot of other stuff after that, so the experiment was put on hold. But a few weeks ago I started working on a new rendering rules engine for Kosmos and I wanted to write some unit tests to try it out – and the experimental map drawing code seemed a good fit.

The rules engine is far from complete, but I can already reveal a few details of its capabilities. First, you specify a set of features, for example a forest, a motorway, a town. In accordance to some common GIS concepts, there are three types of features: point, line and area feature.

Then you specify how each of these features should be rendered. This consists of a directed graph of commands which supports inheritance of rendering properties (something in the direction of MapCSS, but not as liberal).

I won’t bore you with the details (at least until a proper parser for these rendering rules is available), but I think this new system will be much more powerful than the existing “flat” Wiki table-based rules one. Also, I’ve been working on improving support for relations and multipolygons.

Anyway: back to Cairo: I’ve started implementing more detailed drawing logic and I had quite a few problems figuring out how to render text using Cairo. It turns out the API for drawing text in Cairo is pretty poor (it even crashes when trying to render non-ASCII chars), so the authors of Cairo recommend using Pango, a library for high-quality text rendering. Luckily, it has Mono wrappers and it wasn’t too difficult to make it write out texts on the bitmap.

I’ve written few unit tests for some simple OSM map rendering and here are the results (the left map is rendered using GDI+, the right one using Cairo):

map2gdimap2cairo

I’ve used some simple rendering rules:

  • texts come from OSM tags equipped with “name” tag
  • lines come from any non-closed OSM ways
  • orange-filled areas come from any areas (closed OSM ways).

As a special treat, I’ve also created a SVG file from the same map, you can download it from here: http://downloads.igorbrejc.net/osm/misc/map1.svg

Published by breki on 03 Nov 2009

DSL For Rendering Rules

Doodle
Creative Commons License photo credit: The Pack

Yesterday I started thinking about a new rendering rules system for Kosmos. The existing system (using Wiki tables) was OK for a while, but it’s starting to show its old age: there is no rule inheritance, the rules are cumbersome to edit (because of wikitext), the selectors are not very powerful, rules are not reusable etc.

I started by investigating how similar software is doing these things. Mapnik has a more elaborate XML-based ruling system. It’s powerful, but it seems too verbose for what I had in mind – I want the rules to be simple to write and even simpler to read. And I want to stay away from XML: XML is easy to parse but not that friendly to humans. And writing expressions using XML character entities (example: “<Filter>[CARTO] &gt;= 2 and [CARTO] &lt; 5</Filter>”) is really unfriendly and error-prone.

The next thing to look at was MapCSS, a CSS-like language for map stylesheets and is a brainchild of Richard Fairhurst, the author of Potlatch, the excellent web-based OSM editor. I like the idea, but I’m worried how it could be implemented in the context of a database-driven map engine. The databases can be huge and you want to minimize (and optimize) the queries run on them, but MapCSS seems to allow too many combinations to make it usable for generating maps in (almost) real-time, and that’s what Kosmos is about. When working efficiently with the database, the rendering engine wants to collect all the related objects in one go, and then decide how to render them. So, for example, if it wants all highways to be rendered red, it’ll fetch all the highways from the database (with a single query) and then go and paint them all red. MapCSS doesn’t really allow this: you need to process each OSM object on its own and go through the list/tree of MapCSS rules in order to know whether (and how) to render it. Maybe I’m wrong and there is a better way to approach this, I’ll have to discuss this further with Richard and see what he thinks.

So now I’m thinking about defining my own domain-specific language (DSL) which would be used to specify rendering rules. I don’t have any specifics yet, but there are some things worth thinking about:

  • The DSL should not be XML-based: angular brackets are not for humans.
  • Separating definition of features from the definition of styles: features tell you what something represents. A forest, for example, is a feature that corresponds to an area tagged with natural=wood or landuse=forest. How it is rendered depends on the type of the map: on topo maps you would render it in green color. On driving maps maybe you wouldn’t render it at all. So the idea is to have a features definitions that could be stored in one place (one wiki page) and then reused all across the styling rules. Right now this is not possible in Kosmos.
  • Expressions: the selector expressions should be more powerful than just simple logical operators. The same goes for expressions for style attributes.

Anyway, this all means I have to implement some kind of a parser for the DSL. So I started looking into possible C# libraries/tools for writing parsers: ANTLR, Coco/R, GOLD, Irony.NET, … There is also a good article called Grammars and parsing with C# 2.0. Time to do some refreshing of knowledge lost way back from my university days…

Published by breki on 23 Oct 2009

Kosmos And Spatial Databases, Part 1

Kosmos Label Placement Sample

Last couple of months I’ve been working on database support for Kosmos. This work started as a request to produce bitmaps of the whole UK in the British national grid reference system from the OSM data.

The current version of Kosmos loads all the OSM data into memory. This obviously proves to be a problem for larger areas. Some time ago I worked on optimizing Kosmos memory usage and it proved to be quite successful, but there is still a physical limit of how large an area can be rendered.

The latest UK OSM data takes about 200 MB of zipped XML (2.5 GB unzipped). This is way too much for the existing in-memory system, so I had to find another way to render UK without reading the XML file directly.

After a bit of investigation, the obvious candidate for OSM data storage proved to be PostgreSQL / PostGIS. By “obvious” I mean that there were already some tools which could import OSM data into the PostgreSQL database, namely Osmosis. I was totally new to PostgreSQL, but the actual installation of the database engine was pretty easy.

The next step was importing of OSM data using Osmosis. Although this can be achieved with a few simple steps, there were quite a few “tricks” I had to learn the hard way before the performance of the database was satisfactory enough to produce map renderings in a realistic time:

  • The PostgreSQL database engine uses non-optimal default settings, so you need to do a bit of investigation to set certain things up. One tip: if you have several disks, make sure your data is stored on a disk separate from the system.
  • Osmosis OSM DB import command has a few settings on its own which can have a dramatic effect on the DB query performance. First of all, you need to use the extended OSM DB schema which contains bbox column for ways, otherwise the spatial queries would always have to contain multiple table joins which will terribly slow things down.
  • Kosmos rendering rule engine was designed for instant-access in-memory data source. The way the data was fetched wasn’t really compatible with slow DB sources, so I had to do a lot of refactoring on the engine before the performance was good enough for any serious work.

After a few weeks of work, I finally managed to get some decent results. The rendering code generated UK for approximate zoom levels 7, 8 and 9 in about two hours on my machine, with the level of detail similar to Mapnik’s layer of the OSM main map. This may seem a lot of time, but considering there were about 11 million nodes and 1.5 million ways to process, I’m quite pleased. And there are further improvements still possible in the rendering engine which could reduce this time at least by half.

British National Grid

One of the biggest worries I had was how the rendering engine will behave when rendering using a map projection and reference system different from the “standard” Mercator and WGS-84. This actually proved to be the easiest thing to solve: the rendering engine internally uses the National grid coordinates and the spatial DB queries transform those transparently to WGS-84 (and back). I also needed to implement a new map projection, but this was just a matter of writing a few lines of math code.

Other Improvements

Since the map was supposed to be “professional” looking, there were a few things that needed to be implemented or improved on the existing rendering engine. These features will probably be included in the next generation of Kosmos, which will be released some time next year.

Text Placement

One of the first (and hardest) things needed for a good looking map is to make sure the text labels do not overlap each other. This is called (automatic) label placement. Good algorithms for label placement are quite complex and I didn’t really have time to implement a full-blown algorithm, so I chose to do a simple point-selection: the algorithm removes labels for smaller places (towns) until there are no more overlaps (see the sample map at the beginning of the post). I’ll write more about this feature some other time.

Better Relations Support

Some of the features needed to be rendered are now defined in OSM using relations. One example of this is national parks. So a new algorithm for consolidating relation’s ways into a single polygon was implemented.

Better Sea Filling Support

The coastline processing algorithm is now more resilient: it will ignore poorly connected coastlines and will still render all of those which are properly defined. This improvement is already in use in the new GroundTruth version released a week ago.

What Next?

During the work on PostgreSQL support I learned about SpatiaLite, a spatial extension to sqlite. As you may know, sqlite is a popular self-contained database engine which stores the data into a single file. So I decided to do a bit of playing around with it and see if it can also be used in Kosmos. I was a bit skeptical whether SpatiaLite will be fast enough for map rendering, but I can already say that it managed to achieve some very good results. I’ll write about SpatiaLite in the next blog post.