Are there any Spatial Data Structures suited for VL?

Guys, It’s a huge topic that I tried to discover by myself with a lot of attempts. I didn’t succeed in C# for some reason. Some of implementations obviously contains bugs, some of them works with fancy and not suitable for VL datastructures, some of them doesn’t works for no reason. VL tries to hit me for recursion and other attempts to “do the right”. Actually, I’m not too mature to do that kind of thing.

There are a lot of algorithms that may and sometimes should be implemented with spatial data structures and optimizations with them. For example, I think drawing nodes in VL may be corresponding with this type of tasks — adding to graph, “intersecting” this graph with render region, exclude evaluation outside the “render view”, and why not to add more “renders” in that case? Physics? Cellular automatas? Huge parallel calculations with OpenCV? Even compute shaders. A lot of serious computational algorithms need optimization like that, not only custom generative image processing.

R-tree, Quadtree, Octtree, k-d trees. I’ve had an experience with Rust and I was really surprised how much of beautiful implementations are in Rust and how easy to use them. I’m even tried to write wrappers, but it’s all looks and feels ugly. Actually, I had couple hybrid tools Rust/VL because of that.

It would be interesting to hear your opinion. Are there any solutions that I’m not aware of?

1 Like

Screenshots from last year’s podcast. Sorry, in Russian, but you can rewind to the end to see the performance

at 1:35:42
It only works slow because of poor drawing optimization without instancing, but you can get the idea.
Next in the video there are examples with good optimization.

2 Likes

Simple implementation of QuadTree
Maybe it will be enough for my purposes

QTA_custom.vl (105.9 KB)

6 Likes

I’ve never heard of R-trees before, might be interesting to investigate. Actually did this a little while ago to optimize collisions. There are 4000 points captured in nearly 8000 boundaries. The search runs very smoothly with instancing. I have an example for QuadTrees too.

I followed this implemention of QuadTrees by Daniel Shiffman adn then added a dimension, but I changed somethings to use VL features instead of javascript and even in a visual programming language the intuition about it aint so clear.

I think there needs to be a bit of a strategy when it comes to programming recursive objects, because you don’t really see the result until its ‘finished’ or nearly so.

I’ll post the patch later but a couple notes

  1. Once the points to search for in the tree are built, the search process is very fast, but the tree rebuilds slowly if I have a lot of points to change.
  2. The patch is pretty janky, so I’ll clean it up a bit but it still confuses even me, so I’ll make some notes that may not be helpful.

KTreeCapture

3 Likes

There is a quote about R-Star:

R-trees can efficiently find answers to queries like “Find the nearest point of a polygon”, “Find all police stations within a rectangle” or “Find the 10 nearest restaurants, sorted by their distances”. Compared to a naive implementation for these scenarios that runs in O(n) for n inserted elements, r-trees reduce this time to O(log(n)) .

However, creating an r-tree is time consuming and runs in O(n * log(n)) . Thus, r-trees are suited best if many queries and only few insertions are made. Also, rstar supports bulk loading, which cuts down the constant factors when creating an r-tree significantly compared to sequential insertions.

R-trees are also dynamic , thus, points can be inserted and removed even if the tree has been created before.

A couple examples:

Open QuadTreeSkia or OcTreeStride. They both use the Ktree patch that has the main code. Maybe it could be made a little more generic, and maybe laid out a bit better but ask here for any pointers.

The Quad tree example is more explicit about the gains you can make: There is a switch to see how the optimized search outperforms the normal search There are 40000 points which is going to run a bit slow that run okay on my desktop, but you could halve that and still get the idea.
KTrees.zip (93.7 KB)

2 Likes
7 Likes

Hey, I am currently looking into Barnes-Hut as a possible solution to speedup a force directed graph and came across your Octree. I switched it from using Box to AlignedBox and it seems to be 3-4 times faster under some conditions at least when building the tree. Search has also some performance gains (because there is no need to convert to AlignedBox I guess). Just FYI.

BoxVsBox

KTrees-0.2.7z (49.7 KB)

3 Likes

This topic was automatically closed 365 days after the last reply. New replies are no longer allowed.