spatial index for lines

Question

I have lots of line segments (that represent various surfaces such as walls, ceilings and floors). I want to efficiently determine which lines are within the player's bounding box.

(Right now I'm cycling through all lines, and whilst correct, it is proving much too slow).

There are several kd-tree and other spatial indices in Javascript but they all store points rather than lines.

I actually only need to query by the x axis; it would suffice with a 1D range tree of some sort.

How can you efficiently store and retrieve shapes such as lines?

Once built, the index would not be added to.

Answer 1

In just 2 dimensions, where you have good control over the total spatial extend (i.e. know min and max, and these won't increase), grid based approaches such as plain grids or quadtrees work incredibly well. In particular, if you know your query radius (the players box size), a grid of exactly this size should work really well.

Many games also used what is called a BSP tree, a binary space partitioning tree. But for good performance, this tree is AFAIK usually precomputed when the level is built, and then just loaded with the map.