A method of generating a database for a navigation device, said method comprising: retrieving data defining a three-dimensional terrain; generating, based on said retrieved data, a first data structure using a tiling which includes a plurality of tiles (23-26; 31-34), wherein an entry is respectively generated in said first data structure for each tile (23-26; 31-34) of said tiling, wherein generating said entry respectively includes: comparing a portion of said three-dimensional terrain contained in said tile (23-26; 31-34) to at least one pre-defined tile pattern included in a second data structure, and selecting, based on a result of said comparing, one of data defining said portion of said three-dimensional terrain or an identifier for a pre-defined tile pattern included in said second data structure for storing in said entry; and storing said first data structure and said second data structure in said database, wherein coordinates of vertices of a surface mesh defining said three-dimensional terrain are retrieved from said data defining said three-dimensional terrain or are generated based on said data defining said three-dimensional terrain, each one of said vertices respectively having a pair of lateral coordinates and a height coordinate, and wherein, for each tile (23-26; 31-34) of said tiling, said entry (14, 16, 17) is respectively generated to include an identifier for a pre-defined tile pattern included in said second data structure if relative lateral coordinates of all vertices located on said tile (23-26; 31-34) correspond to lateral coordinates of vertices in said pre-defined tile pattern. retrieving data defining a three-dimensional terrain; generating, based on said retrieved data, a first data structure using a tiling which includes a plurality of tiles (23-26; 31-34), wherein an entry is respectively generated in said first data structure for each tile (23-26; 31-34) of said tiling, wherein generating said entry respectively includes: comparing a portion of said three-dimensional terrain contained in said tile (23-26; 31-34) to at least one pre-defined tile pattern included in a second data structure, and selecting, based on a result of said comparing, one of data defining said portion of said three-dimensional terrain or an identifier for a pre-defined tile pattern included in said second data structure for storing in said entry; and storing said first data structure and said second data structure in said database, comparing a portion of said three-dimensional terrain contained in said tile (23-26; 31-34) to at least one pre-defined tile pattern included in a second data structure, and selecting, based on a result of said comparing, one of data defining said portion of said three-dimensional terrain or an identifier for a pre-defined tile pattern included in said second data structure for storing in said entry; and storing said first data structure and said second data structure in said database, wherein coordinates of vertices of a surface mesh defining said three-dimensional terrain are retrieved from said data defining said three-dimensional terrain or are generated based on said data defining said three-dimensional terrain, each one of said vertices respectively having a pair of lateral coordinates and a height coordinate, and wherein, for each tile (23-26; 31-34) of said tiling, said entry (14, 16, 17) is respectively generated to include an identifier for a pre-defined tile pattern included in said second data structure if relative lateral coordinates of all vertices located on said tile (23-26; 31-34) correspond to lateral coordinates of vertices in said pre-defined tile pattern.