node.children is undefined when adding multiple infinite-length lines about rbush HOT 8 CLOSED

It's a pretty uncommon use case, but I'd like to make RBush support it too. Can you set up the most minimal test case that reproduces the problem so that I can look into fixing it faster?

from rbush.

hey @Pieter-Jan, any updates?

from rbush.

Hey @mourner thanks for taking interest in this issue!

I read some more about R-trees and realised that my problem is very hard to support by an R-tree. I was unable to create a "minimal" situation where this issue started occurring in Rbush but I did notice that jsts' strtree dynamically enlarges the number of children for the "nodes" when I feed the same data (this takes a lot of time). I am not sure what they do next because the performance is still beter than a complete search. This suprises me, because the bounding box of an infinitely long line is infinite as well.

To give you a perspective, I am trying to come up with a way to improve the performance of "snapping to objects" in a drawing tool (like powerpoint, ...) where there are >1000 objects.

from rbush.

@Pieter-Jan nice use case! I think the best way to approach this would be to have 2 separate 1D binary search trees — one for X axis and one for Y axis. Search for the nearest neighbor is trivial in such case, and you would just do 2 o(log N) lookups that would be pretty much instant (even with a million objects) to find the snapping lines.

from rbush.

I think there might be an edge case when a bbox is infinite on only one side of one axis, i.e. { minx: 0, maxx: Infinity, miny: -10, maxy: 10 }.

Granted, it's not what the initial query is about, but might be important to take into account when approaching similar problems.

from rbush.

Hey @mourner Yes that would be great! Unfortunately I realised recently that we should support snap lines in any direction so I am still looking for a better solution :).

from rbush.

@Pieter-Jan maybe you should still try the 1D BSP approach, but have a BSP for every unique angle value. It's unlikely that angles will vary too much on one scene.

from rbush.

I'm sure you can do away with a linear loop though. Doing a 1000 point to line distance calculations per frame is nothing for a modern browser.

from rbush.