1From green@superliminal.com Fri Jul 19 02:55:40 2002 2Return-Path: <green@superliminal.com> 3Received: from camelot.itc.it (camelot [195.223.171.5]) 4 by orchestra.itc.it (8.11.6/8.11.6) with ESMTP id g6J0uQa24233 5 for <blazek@itc.it>; Fri, 19 Jul 2002 02:56:26 +0200 6Received: from jareth.dreamhost.com (jareth.dreamhost.com [66.33.198.201]) 7 by camelot.itc.it (8.11.3/8.11.3) with ESMTP id g6J0uOn13308 8 for <blazek@itc.it>; Fri, 19 Jul 2002 02:56:25 +0200 (MET DST) 9Received: from superliminal.com (adsl-63-201-35-131.dsl.snfc21.pacbell.net [63.201.35.131]) 10 by jareth.dreamhost.com (Postfix) with ESMTP 11 id 39D616B5EA; Thu, 18 Jul 2002 17:56:22 -0700 (PDT) 12Message-ID: <3D37638C.7AEB82AE@superliminal.com> 13Date: Thu, 18 Jul 2002 17:55:40 -0700 14From: green@superliminal.com 15Reply-To: green@superliminal.com 16Organization: Superliminal Software 17X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U) 18X-Accept-Language: en 19MIME-Version: 1.0 20To: Radim Blazek <blazek@itc.it> 21Cc: antonin.guttman@informix.com 22Subject: Re: R-Tree for GRASS 23References: <02071810432200.13881@janacek> 24Content-Type: text/plain; 25 charset=us-ascii 26Content-Transfer-Encoding: 7bit 27Status: RO 28X-Status: O 29 30hello radim, 31 32i'm glad that you're finding my r-tree implementation useful. it should be noted 33that i am not the original author. i got my original implementation directly from 34toni gutman who i believe co-invented the technique with michael stonebrakier. 35that implementation was the same one they'd originally written when testing and 36benchmarking the technique. he was not proud of the original code and felt that 37while it worked, it would have been better reimplemented from scratch. instead, i 38upgraded and polished their code. another user discovered a flaw in the technique 39and suggested a solution using bounding spheres which i then implemented. for 40example, imagine you have the following three rectangles: 41 0,0 to 1,0 42 0,2 to 1,3 43 1000000,0 to 1000001,0 44if you want to partition them into two boxes, the original algorithm based only on 45box volumes would have put the first rectangle in one box and the last two in 46another. clearly a bad choice for most applications. the bounding sphere metric 47would instead place the first two rectangles in one box and the third in another. 48much better. it was definitely interesting to extend this to use n-dimensional 49spheres, but it does generalize nicely. 50 51your changes to NUMDIMS, and float to double are normal parameters you're expected 52to customize. your changes to handle compiler warnings and printf are more 53interesting to me. you didn't include your modified files, so i'd appreciate them 54which i may use to update the archive. if you can, please make careful note of 55your non-cosmetic fixes and improvements. i can't promise to update the archive 56but it will at least be useful to have. more likely i'd convert the whole thing 57into a nicely objectified java package but there's a good chance i'll never get 58around to doing that. 59 60regarding split_l.c vs. split_q.c: these involve a choice you can make between 61speed and box optimization. you should use the quadratic version ('q') if it's 62fast enough for your needs, and use the less expensive linear method if not. note 63that in both cases various branches of the resulting rectangle trees may overlap. 64there's another version of the technique called "R+ Trees" which guarantees no 65overlaps, but i don't have an implementation of that version. i believe it's even 66slower than either r-tree splitting method, so you should probably also take all 67of that into account. 68 69i did a quick search and found a citing of toni's work here: 70http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/g/Guttman:Antonin.html 71for your grass header files, you should list toni's name as author, though i'd 72appreciate mention of my updates to his code and technique. 73you'll find the abstract of the paper here: 74http://www.informatik.uni-trier.de/~ley/db/conf/sigmod/Guttman84.html 75and a home page for toni here: 76http://es.ucsc.edu/~tonig/ 77note that you'll also find links to his original paper and implementation there. 78i'm cc'ing him in case there's anything he'd like to add or correct; and also so 79that if he likes, he can update his implementation with my updated sources. it's 80been a very long time since i've talked with him so i hope that address is still 81current. 82 83finally, i have a question for you about grass: i've developed a technique based 84on r-trees that allows interactive navigation of enormous polygonal 3d data sets. 85it's been a solution in search of a problem. i know that some gis application 86require such data sets and i'd love to communicate with any that you know of who 87might need such a technique. it only works in static environments that are crowded 88enough such that regardless of how the user navigates, only a very small fraction 89of the entire data set are ever visible at once. it's obviously a very specialized 90technique but it scales with the log of the number of polygons and may therefore 91be very useful for applications with huge and ever-growing data sets. 92 93-daniel 94 95Radim Blazek wrote: 96 97> Ciao, 98> 99> I want to use R-Tree http://www.superliminal.com/sources/RTree.zip 100> as spatial index for GRASS (GPL GIS) http://grass.itc.it/index.html 101> 102> I tested just for line intersection function but want to use as general 103> index for vectors. Library will be part of GRASS project, but may be 104> extracted and compiled independently (Makefile.alone). 105> 106> I have done just few cosmetic changes so far (described in README.grass): 107> - files converted to unix line ends 108> - added file 'README.grass' 109> - added Makefile 110> - few modifications to get rid of compiler warnings, but warnings like: 111> index.c:277: warning: `tmp_nptr' might be used uninitialized in this f. 112> were left because need deeper revision if may cause problems, insetad of 113> blindly init to 0/NULL 114> - '//' comments -> '/* */' 115> - printf() - > fprintf(stdout,) 116> - NUMDIMS set to 3 117> - test.c 2D -> 3D 118> - type RectReal: float -> double 119> 120> OK? (I hope so because you write: You're completely free to use them for any 121> purpose whatsoever.) 122> 123> If you don't mind I would like to ask you if you recall 124> how split_l.c and split_q.c differ and which should be used? 125> 126> Can I add headers to your files for GRASS?: 127> /**************************************************************************** 128> * MODULE: R-Tree library 129> * 130> * AUTHOR(S): Daniel Green (dgreen@superliminal.com) 131> * 132> * PURPOSE: Multidimensional index 133> * 134> * COPYRIGHT: (C) 2001 by the GRASS Development Team 135> * 136> * This program is free software under the GNU General Public 137> * License (>=v2). Read the file COPYING that comes with GRASS 138> * for details. 139> *****************************************************************************/ 140> 141> Thanks 142> 143> Radim 144 145 146