Multi-dimensionality?

[jwscook]

First of all I'd like to say that I love this tool! It's really helped me out a lot. I just wanted to ask if there is any plan for making it a multi-dimensional interval tree? If not, any advice as how I might have a go, and make the contribution to the repo?

Many thanks! James

[TransGirlCodes]

Hi @jwscook Multi-dimensional intervals sounds interesting. I don't know much about them except they can be considered the cartesian product of a set of n intervals., one interval for each co-ordinate axis. I suppose the first question is, does the AbstractInterval interface and method requirements fit for an n-dimensional interval? and would the sorting and indexing that is done with 1-D intervals in IntervalTrees also largely apply to n-dimensional intervals? I think you are more knowledgeable on this, but the first step would be to make a fork, and a PR, outlining what you want to do, and then when some set direction is decided on, start adding commits to the PR branch of your fork.

[sambitdash]

I will also rhyme with @jwscook on this. Programming for several years, I still find debugging B-Trees a formidable task. So this being implemented in a manner it has been, is an laudable effort. Hence, thank you.

You may like to review the package called Rectangle where this concept has been carried out for implementing Quadtree like subdivision of rectangular spaces. It's essentially a simple 2-IntervalTrees. Ordering needed for my application needed X-axis and Y-axis ordering independently ordered. For simplicity, I used only the intersect operations than implementing elaborate 2-D iterators.

These code segments can provide you the concept clearly.

I have also used the similar concept for searching font mapping for PDF parser for UInt8 type data.

Multi-dimensional range maps are used in Lattices in Algebraic Topology in CAD extensively. However, complexity may be substantial and multiple interval trees can address the issues with relative simplicity as has been shown in the Rectangle package.

[sambitdash]

Computational Geometry - Preparata Shamos (1985) - Springer Verlag (Chapter 8) talks about horizontal and vertical adjacency maps which can be represented as IntervalTrees and tlhat is how I conceptually came up with the idea in the Rectangle package. But nearest interval #14 is equally important in multi-dimensional interval trees. You could use any other distance metric like city block, euclidean, Minkowski, Mahalnobias distances as well. Not sure if you would compute min-distance or avg-distance in those cases as each interval cubes will be point sets as well.