In the last days I wrote a first draft following the Guttman paper. While the algorithm is very simple and well explained in the paper, there are two points which makes the implementation not that easy: 1. We want a fully generic RTree (dimension, data type for location, data type for contained data.) And 2. the tree has two different types of nodes, the leaf with data, and the inner nodes.
So I used some type casts and proc arguments with or types (|). The code compiles and I can at least add one entry, delete it or search for it. Currently I do not really care if the code really works -- basically it should but it will have many bugs for sure. I was mostly only interested in how the Nim code would look. I still wonder how we can write it in a simpler and more compact way. Would using concepts help? Or maybe templates instead of procs with OR types? Or object variants or methods? Of course we could simplify the code, if we use only one node type -- each node could contain data and the pointer to next node, but that would waste some memory. Or we could restrict the contained data to reference types, then we could do dirty casts between data and nodepointers. I guess C implementations would do that. Of course later we would convert the RTree into the STAR variant R*Tree with optimized split algorithm and better performance, but that variant is a bit more complicated. One general problem of Rtrees and R*Trees may be their age -- the papers are from 1984 and 1990 and the original authors tuned the algorithm for paged memory. But I am not aware of better algorithms for spatial search of extended objects, i.e. rectangles in 2D.
