From Navit's Wiki
Revision as of 19:45, 27 May 2008 by Cp15 (talk | contribs)
Jump to: navigation, search

Some words about the binary driver, used to convert OSM maps to a format usable for navigation :

The map coordinates of binfile are in meters, measured from equator and null meridian, with a merkator projection. The limit of this world is about 20000 km in earch direction from this null point. This doesn't cover polar regions, but it's ok for now.

So, the world gives a 40000x40000km rectangle. This rectangle is divided into 4 equally-sized sub-rectangles called a,b,c and d...

  • a is top right
  • b top left
  • c bottom right
  • d bottom left

Each of this sub-rectangles is then further subdivided, so a rectlangle "aa" is top left in "a"

This is continued further up to 14 levels (but the number of levels might be variable). So in the end effect you get many tiles which are containing objects which are within this tile... And the tiles are also containing references to tiles which are within them.

Each tile is a member file in a zip file. So to extract an area of this file, you just read the zip file sequentially.

Tile data format

A tile itself is a dynamic data structure. As declared in data/binfile/binfile.c:

struct tile {
  int *start;           /* Memory address of the whole data structure */
  int *end;             /* Memory address of first memory address not belonging to tile
                         * thus tile->end - tile->start represents the size of the tile
                         * in multiples of 4 Bytes */
  int *pos;             /* current position inside the tile */
  int *pos_coord_start; /* pointer to the first element inside the tile that is a
                         * coordinate. That is the first position after the header of a
                         * tile. The header holds 3 entries each 32bit wide integers.
                         * header[0] holds the size of the whole data-structure.
                         * header[1] holds the type of the item
                         * header[2] holds the size of the coordinates in the tile */
  int *pos_coord;       /* current position inside the coordinates region within the tile */
  int *pos_attr_start;  /* pointer to the first attr //TODO explain attr format// data
                         * structure inside the tile's memory region */
  int *pos_attr;        /* current position inside the attr region */
  int *pos_next;        /* link to the next tile */
  int zipfile_num;

The actual item data looks like this (everything is 4 bytes wide and always aligned):

  int: Length of the item (not including this length field) in integers
  int: Type of the item (from item_def.h)
  int: Length of the coordinate data which follows in integers
    int: pairs of coordinates with consisting of 2 integers each
  } 0..n
    int: length of the attribute (not including this length field) in integers
    int: Type of attribute (from attr_def.h)
      int: Attribute data, depending on attribute type
    } 0..n
  } 0..n

How to extract a specific area from this map format

You can calculate the bounding box of the current tile.

Then there are two possibilities:

  • The tile overlaps with the area you are interested in : Then simply copy the whole file data, including its header to the output, and add an entry to the directory which will be written later
  • The tile doesn't overlap : Then don't drop that file, but instead write a file with size 0 and the same name to the output (I will explain later why this is needed), and add an entry to the directory

At some point you will have reached the end of the zip files, then you have to write the zip directory and the "end of directory" marker

This will be very fast (you don't have to look into the zip files, which would mean decompressing and compressing it again) but has some disadvantages:

  • You will have many empty files in it which are not really necessary. This is needed because the reference to sub-tiles are by number, and not by name (would be slow), and so the position of a tile within the zip file is not allowed to change
  • You get some data you didn't want to have : this is because a tile which overlaps with your area of course doesn't contain only data from your wanted area, but from the area where it is located