2 ms·
Efficient 3 dimensional position or range queries (line/column/page) is a pretty well studied problem. You don't need to query every point of the space to answe
by hctaw 5y ago
Efficient 3 dimensional position or range queries (line/column/page) is a pretty well studied problem. You don't need to query every point of the space to answer anything.
- jasim 5y agoI could not find clear references with an initial search. Can you expand a bit more about this approach? Thanks.
- ctoth 5y agoI've used a segment tree[0] for a similar problem before. For 3D queries an R-tree may be more appropriate. [0]: https://en.wikipedia.org/wiki/Segment_tree https://en.wikipedia.org/wiki/Segment_tree
- hctaw 5y agoIt's a task more commonly found in computational geometry (3D range query == find all the points in a data set enclosed by a cube). There are numerous data structures that are well suited for various geometric queries like ranges/lookups (interval trees, quadtrees) as well as more text-oriented operations like cut/copy/paste/insert/merge/etc (like ropes). I'm not familiar with the operations required to put a cursor at the right place in a document, but knowing how much research has gone into storing similar data and looking up what you need efficiently the idea of "going through all the text every time" is a big code smell.