Slab decomposition data structure for 2D vertical ray queries
Given a collection of line segments, constructs a slab decomposition for the purpose of point location queries. This implementation uses a functional red-black tree to store the slabs, requires O(n log(n)) space and answers vertical ray queries in O(log(n)) time.
var makeSlab = require"slab-decomposition"var slabs = makeSlab0 0 10 101010 20 05 5 20 0forvar i=-10; i<10; ++iconsole.logslabscastUpi -1
npm install slab-decomposition
Constructs a slab decomposition from the segments
segmentsis a collection of line segments which only overlap at their end points
Returns A slab decomposition data structure
Casts a vertical ray from
point going upward along
[0,1]. Returns the index of the first segment hit.
pointis the base point of the ray
Returns The index of the first segment hit by point, otherwise -1 if no segment intersects the ray.
(c) 2014 Mikola Lysenko. MIT License