[gdal-dev] OT: OGR and Quadtree and R-tree

[John Reid]

Hi,

Comments inline:

Paul Selormey wrote:

>Hello Frank,
>Thanks so much for yet another great support. I have being playing with
>those
>algorithm but do not really know how best to put them into use. Thanks for
>the enlightment.
>Also, I had thought OpenEV is reading from the file directly and with the
>current
>speed I was satisfied. Being a Python application, it was very difficult to
>tell the
>among of memory being consumed-it only shows the Python runtime memory.
>
>Points are normally all right for memory, but polygon/polyline data could be
>really huge.
>I had a dataset of over 240 MB from a friend the other day, with one of the
>files being
>as much as 100 MB and placing this in memory as my source of worry.
>
If you don't mind me asking, what sort of extents and resolution is this 
data and how well clustered is it (from the bounding box perspective)? 
Do you need the whole lot visible at once?

>I will more carefully read your solutions and insight and see how best to
>implement them.
>I wish the author of GFC is also here to give his insight into the R-tree.
>
Unfortunately L.J. Qian has indicated that he is unable to continue 
development of GFC due to other commitments :-( However he is quite 
happy for some new development to take place. I think there might also 
be some related code in OSSIM.

As far as R-tree goes, there is also some

* C++ code for R*-trees in Predator (ORDBMS - from the webpage "B+
tree and R* tree indexing (with the ability to add new indexes)
over simple and complex expressions." - not sure if this is
implementation of Gist)
* C code in PostGIS/PostgreSQL.

There are some other links as well that I can go digging for if 
interested. What are you interested in doing, visualisation? HTH.

cheers,
John

>
>
>Again, thanks.
>
>Best regards,
>Paul.
>
>----- Original Message -----
>From: "Frank Warmerdam" <warmerdam at p...>
>To: <gdal-dev at yahoogroups.com>
>Sent: Tuesday, August 21, 2001 10:22 PM
>Subject: Re: [gdal-dev] OT: OGR and Quadtree and R-tree
>
>
>>Paul Selormey wrote:
>>
>>>Hello All,
>>>
>>>This is really off-topic, but I could not find a good place to
>>>discuss the OGR and since it is "part" of the GDAL I decided to post
>>>this here.
>>>
>>>Not a professional GIS person, a newbie. I have read about Quadtree
>>>and R-tree and how they make rendering fast.
>>>
>>>1. Which one do you use for Shape file and MID/MIF/TAB and why?
>>>
>>>2. I have seen the implementation of the quadtree in shapelib and the
>>>R-tree in GFC. However, no such algorithm is used in the OGR, why?
>>>
>>>3. I have used OpenEV, which is based on the OGR/GDAL. The rendering
>>>is not all that slow, so why is the need for the quadtree?
>>>
>>>4. To anyone building a OGRLayer object and concerned with the memory
>>>and speed, what is the most practical/best way to use the classes
>>>provided in the OGR?
>>>
>>Paul,
>>
>>1) Shapefiles do not generally have a spatial index. ESRI programs do
>>sometimes generate .sbn/.sbx files which are some sort of spatial index
>>
>but
>
>>they are not documented. The OGR driver for shapefiles does not include
>>any spatial indexing ... it doesn't even use my hacky quadtree stuff in
>>shapelib at this time.
>>
>>2) OGR is generally used for one pass translation rather than high
>>performance random access, so indexing has not been a priority.
>>
>Furthermore
>
>>indexing separately in each driver would complicate the code ... perhaps
>>significantly.
>>
>>3) Note that OpenEV vector rendering loads all the shapes into memory
>>
>making
>
>>the speed of OGR rather irrelevant. Rendering speed of large layers of
>>vectors in OpenEV isn't all that fast, especially if zoomed in on a subset
>>of a large layer because OpenEV always drawns all the vectors through
>>
>OpenGL.
>
>>However; OpenEV does demonstrate the truth that spatial indexing of
>>
>vectors
>
>>is generally only important if you want to deal with vector large vector
>>datasets (larger than can be conveniently held in RAM for instance).
>>
>>4) OGR doesn't really provide any support functions to simplify
>>
>implementing
>
>>a high performance driver; however, it does provide important hooks that a
>>driver can implement to provide better performance to the application. In
>>particular, if applications set a spatial or attribute query a given
>>
>OGRLayer
>
>>implementation can choose to implement it internally in a smart way to
>>
>provide
>
>>good performance. Make sure you override GetExtent() and
>>
>GetFeatureCount()
>
>>so the default implementations (which result in reading the whole dataset
>>once) are not used. Also, if you want to provide high performance, make
>>
>sure
>
>>that random reads are supported.
>>
>>Finally, try to return meaningful results from your TestCapability() call.
>>
>>While OGR formats can be implemented fairly efficiently; if you are
>>super-sensitive to performance, going through OGR is likely not the most
>>efficient mechanism. OGR adds a non-trivial overhead in terms of making
>>and destroying the OGRFeatures. That is why something like MapServer
>>which is very performance sensitive renders directly from a
>>
>hacked/optimized
>
>>shapelib instead of going through a nice general library like OGR. Well,
>>
>it
>
>>does have the option of going through OGR, but it's most optimized option
>>is still the direct from shape method.
>>
>>Best regards,
>>
>>--
>>---------------------------------------+----------------------------------
>>
>----
>
>>I set the clouds in motion - turn up | Frank Warmerdam,
>>
>warmerdam at p...
>
>>light and sound - activate the windows | http://pobox.com/~warmerdam
>>and watch the world go round - Rush | Geospatial Programmer for Rent
>>
>>
>>
>>
>>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>>
>>
>>
>
>
> 
>
>Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 
>
>

-- 
----------------------------------------------------------------------
john reid e-mail jgreid at u...

uproot your questions from their ground and the dangling roots will be
seen. more questions!
-mentat zensufi

apply standard disclaimers as desired...
----------------------------------------------------------------------