Spatial Index for Lines

Question

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

(Now I ride a bicycle along all the lines, and, rather, it's too slow).

Javascript has several kd trees and other spatial indexes, but they all store points, not strings.

I really only need to request the x axis; this would be enough with a 1D range tree.

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

Once created, the index will not be added.

Answer 1

In two dimensions, where you have good control over the total spatial extent (i.e., know min and max, and they will not increase), grid approaches such as simple grids or quadrants are incredibly good. In particular, if you know your query radius (box size for players), a grid of exactly this size should work very well.

Many games also used the so-called BSP tree, a binary space partition tree. But for good performance, this AFAIK tree is usually pre-computed when building the level, and then just loaded with the map.