[DGD] Sparce Matrix

[Ling]

On Wed, 28 Apr 1999, Kevin Carpenter wrote:

> I suspect the most efficient way of doing this is with nested mappings,
> although I'm very open to suggestions.  One problem with this approach
> is resolving the location spanning issue:  e.g.  If I want to place an
> object at location 10:50:5, how do I determine who the closest other
> object is?  If an object existed at, say, 8:48:5, and it was 3:2:1 in
> size, there would be a conflict since that object would logically exist
> in space 8-10:49-50:5-5.  Once I located the object at 8:48:5, querying
> its size and determining an overlap is easy.  The problem then becomes
> one of locating the object in the first place. 
> 
> If I stored my structure as a nested mapping, I could extract the
> indexes each time I need to do a check (fortunetly, this won't happen
> often for the larger mappings), and binary search the results.  However,
> if I need to do that index extract each time, I might be better off just
> doing my own array maintenance and represent the sparce matrix that
> traditional way. 

A possible solution which may interest you is r-trees.  Unfortunately, in
my brief search, I couldn't find a decent explanation of one.  Anyway, try
the following links for source code and some vague explanations.

<URL:http://cimic.rutgers.edu/~jscho/soap/spaper/node14.html>
<URL:http://joinus.comeng.chungnam.ac.kr/~dolphin/db/access/rtree.html>
<URL:http://www.superliminal.com/sources/sources.htm>

In short, an r-tree is a datastructure for querying a spatial database
using nested bounding rectangles.  The messy bit is splitting the tree.

Once you understand the theory, it is pretty simple. :)  (that's prolly
quite a stupid statement to make)

Sorry I can't expand upon this further.  Final year project report really
does vacuum my spare time away... 

  |    Ling Lo
_O_O_  kllo at iee.org



List config page:  http://list.imaginary.com/mailman/listinfo/dgd