test for isInRange?

[Tim Peters]

[posted & mailed]

[Janko Hauser]
> As it seems, that at the moment all bot's are very creative, I dare to
> ask a question.

Man, you're not kidding!  I had to take the timbot offline, to replace its
"sense of reality" chip.

> What is the known right(tm) algorithmic answer to the problem if a number
> or a range represented by two numbers(start,stop) is in another range?
> Think of a database with geographic locations and you want to to ask
> this database (which need not to be a relational db) if there is data
> in a given range. (Forget for the moment problems with cyclic ranges)
>
> Same for time.
> Is there a known good structure to keep such range information? Should
> I look in the geometry department?

The question isn't exactly clear, but consider looking up a street name in
the index of an atlas.  In this country <wink>, you generally get a list of

    (page number, vertical grid, horizontal grid)

triples.  The "page number" is an artifact of publishing; it's really one
giant grid divided into equal-sized squares.

So you can do that to start:  make up artificial uniformly sized "boxes" for
each of your coordinate axes.  Create a (say you have two coordinates) 2D
sparse matrix mapping each pair of box indices to the list of (e.g.) points
that belong to that box, or ranges that intersect that box, etc.  Then a
little arithmetic on an input suffices to find the only possibly relevant
box indices, and from there the matrix takes you to lists of the only
possibly relevant points (ranges, whatever).

This cuts down search time to the extent that your grid is fine enough so
that the avg # of items per grid area is small.  A more sophisticated
recursive data structure can adapt to local variations in density by, at
each level, mapping a vector of box indices either to a list of final items
of interest or to a finer-grained instance of the same kind of data
structure (but covering only the one grid area it's mapped from).

This can get messy <wink>.  I'm not sure I've seen any implementations of
this kind of thing in Python.  It would be natural in a computational
geometry pkg, or perhaps image processing.

can-never-have-too-many-data-strutures-ly y'rs  - tim