On Wed, 9 May 2007 21:00:46 +0400 Tomash Brechko <[EMAIL PROTECTED]> wrote:
> On Wed, May 09, 2007 at 14:45:33 +0000, [EMAIL PROTECTED] wrote: > > You need an R-Tree index to do something like this. The > > public-domain version of SQLite only supports B-Tree indices. > > So, no, indices are not going to help you here. > > Alternatively to R-tree index, you may simply partition the space into > NxM cells, with, say, left and bottom border belonging to the cell > itself (while right and upper borders belonging to the right and upper > cells as their left and bottom borders respectively), and enumerate > these cells row-by-row like > > 10|11|12|13|14 > ---+--+--+--+--- > 5| 6| 7| 8| 9 > ---+--+--+--+--- > 0| 1| 2| 3| 4 > > > This way every point belongs to exactly one cell. Then you create > > CREATE TABLE map ( > x INTEGER, > y INTEGER, > name TEXT, > cell_no INTEGER > ); > CREATE INDEX map_cell_no ON map (cell_no); > > When inserting a point, you compute its cell_no (something like > > cell_no(x, y) = y / cell_height * cells_in_row + x / cell_width; > > > ). When doing a region query, you compute a set of cell numbers that > intersect with a query window, accumulate them in a (memory) table > selected_cells, and then do > > SELECT map.* > FROM mem.selected_cells sc CROSS JOIN map ON sc.cell_no = map.cell_no; > > Better yet to compute two sets: those cells that reside completely > within the query window, and those that intersect window border. > Points from the latter cells should be filtered further. > > Reasonable cell dimensions based on typical query window size and > points distribution will give quite reasonable performance. Interesting idea. I'll try to test it. Dimension for my map is 800x800 and number of points 50,000+. -- Biomechanical Artificial Sabotage Humanoid ----------------------------------------------------------------------------- To unsubscribe, send email to [EMAIL PROTECTED] -----------------------------------------------------------------------------
