ray-quadtree
A 2d implementation of the octree traversal algorithm described in An Efficient Parametric Algorithm for Octree Traversal.
install
npm install --save ray-quadtree
use
var isect = var QuadTree = // create a new quadtree centered at (0,0)var tree = 0 0 // leaves are to 10x10 unit squarestree;tree;tree;tree; // this is called every time the traversal algorithm processes a// quadtree node. Returning `true` marks the traversal complete. { console // returning true here will stop the traversal for this ray return nodeleaf;} var origin = -50 20var direction = 1 0; // this needs to be normalized if console
outputs:
depth: 0, center: (50, 10), bounds: (-30, -70) -> (130, 90)
depth: 1, center: (10, 50), bounds: (-30, 10) -> (50, 90)
depth: 2, center: (-10, 30), bounds: (-30, 10) -> (10, 50)
depth: 3, center: (-20, 20), bounds: (-30, 10) -> (-10, 30)
found occupied cell
take a look at demo.js to see a full example of usage