Documentation Source Text

Check-in [1f473ab6ac]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add a brief note to the R-Tree documentation to encourage applications to round contained-within query boxes outward slightly to account for round-off error in 64-to-32-bit floating point conversions.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 1f473ab6ac1ce7fc27e9fd632fc691ca1bf7cfc0
User & Date: drh 2012-05-29 01:06:15
Context
2012-05-30
00:46
Clarification of what counts as using a database connection for restrictions on SQLITE_THREADSAFE=2. check-in: 84df66d24b user: drh tags: trunk
2012-05-29
01:06
Add a brief note to the R-Tree documentation to encourage applications to round contained-within query boxes outward slightly to account for round-off error in 64-to-32-bit floating point conversions. check-in: 1f473ab6ac user: drh tags: trunk
2012-05-28
17:52
Improvements to shared cache hyperlinking and fixes to the URI parameter documentation. check-in: 918202f13d user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/rtree.in.

207
208
209
210
211
212
213






















214
215
216
217
218
219
220

<p>
But, generally speaking, the more constraints that the R*Tree module
has to work with, and the smaller the bounding box, the faster the
results will come back.
</p>























<h2>4.0 Using R*Trees Effectively</h2>

<p>
The only information that an R*Tree index stores about an object is
its integer ID and its bounding box.  Additional information needs to
be stored in separate tables and related to the R*Tree index using
the primary key.  ^(For the example above, one might create an auxiliary







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242

<p>
But, generally speaking, the more constraints that the R*Tree module
has to work with, and the smaller the bounding box, the faster the
results will come back.
</p>

<h3>3.3 Roundoff Error</h3>

<p>
By default, coordinates are stored in an R*Tree using 32-bit floating
point values.  When a coordinate cannot be exactly represented by a
32-bit floating point number, the lower-bound coordinates are rounded down
and the upper-bound coordinates are rounded up.  Thus, bounding boxes might
be slightly larger than specified, but will never be any smaller.  This
is exactly what is desired for doing the more common "overlapping" queries
where the application wants to find every entry in the R*Tree that overlaps
a query bounding box.  Rounding the entry bounding boxes outward might cause a
few extra entries to appears in an overlapping query if the edge of the
entry bounding box corresponds to an edge of the query bounding box.  But
the overlapping query will never miss a valid table entry.  

<p>However, for a "contained-within" style query, rounding the bounding
boxes outward might cause some entries to be excluded from the result set
if the edge of the entry bounding box corresponds to the edge of the query
bounding box.  To guard against this, applications should expand their
contained-within query boxes slightly (by 0.000012%) by rounding down the
lower coordinates and rounding up the top coordinates, in each dimension.

<h2>4.0 Using R*Trees Effectively</h2>

<p>
The only information that an R*Tree index stores about an object is
its integer ID and its bounding box.  Additional information needs to
be stored in separate tables and related to the R*Tree index using
the primary key.  ^(For the example above, one might create an auxiliary