skywind mailing lists wrote: > I hoped that somebody already tried to implement a nearest neighbor > algorithm.
Typically, objects are not axis-aligned rectangles, and the R-tree is just an index based on the bounding boxes. Computing the (nearest) distance would require the actual geometries. > Is the format of the shadow tables somewhere documented or do I have > to analyze the source code? rtree.c says: ** Database Format of R-Tree Tables ** -------------------------------- ** ** The data structure for a single virtual r-tree table is stored in three ** native SQLite tables declared as follows. In each case, the '%' character ** in the table name is replaced with the user-supplied name of the r-tree ** table. ** ** CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB) ** CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER) ** CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER) ** ** The data for each node of the r-tree structure is stored in the %_node ** table. For each node that is not the root node of the r-tree, there is ** an entry in the %_parent table associating the node with its parent. ** And for each row of data in the table, there is an entry in the %_rowid ** table that maps from the entries rowid to the id of the node that it ** is stored on. ** ** The root node of an r-tree always exists, even if the r-tree table is ** empty. The nodeno of the root node is always 1. All other nodes in the ** table must be the same size as the root node. The content of each node ** is formatted as follows: ** ** 1. If the node is the root node (node 1), then the first 2 bytes ** of the node contain the tree depth as a big-endian integer. ** For non-root nodes, the first 2 bytes are left unused. ** ** 2. The next 2 bytes contain the number of entries currently ** stored in the node. ** ** 3. The remainder of the node contains the node entries. Each entry ** consists of a single 8-byte integer followed by an even number ** of 4-byte coordinates. For leaf nodes the integer is the rowid ** of a record. For internal nodes it is the node number of a ** child page. For a simple search algorithm, see <http://stackoverflow.com/q/25241406>. Regards, Clemens _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
