On Thu, Dec 27, 2007 at 03:29:47PM +0000, Jon Burgess wrote: > On 27/12/2007, Gabriel Ebner <[EMAIL PROTECTED]> wrote: > > On Thu, Dec 27, 2007 at 02:06:48AM +0000, Jon Burgess wrote: > > > > By using QuadTiles, you only have to look at 120,000 nodes (10,000 > > > > nodes each for the QuadTile and all of its parents) to determine what to > > > > map. Of course, you could use this in conjunction with spatial > > > > indexing to make things even faster. > > > > > > We do not directly deal with this level of detail in Mapnik. The > > > PostgreSQL Postgis extensions deal with efficiently performing spatial > > > queries on the data in the tables. It uses an radix-index scheme which > > > I believe is a more generalised form of quad-tiling. > > > > AFAIK postgis uses R-trees for indexing, i.e. no sort of tiling whatsoever. > > I was thinking that the prefix / trie structure of the r-tree is quite > similar to the quad tiling scheme. The further you go down the tree > the smaller spatial area is covered by the objects deeper in the tree.
The big difference between an R-tree and a radix tree is that the nodes of an R-tree can and do overlap, while those of a radix tree don't. This makes it easier to store large objects since you don't have to insert them into multiple nodes if they happen to cross the edge of a tile, but only into a single node, whose bbox you can adjust. Gabriel. _______________________________________________ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
