javascript - 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

在二维空间中，您可以很好地控制总空间扩展（即知道最小值和最大值，并且这些不会增加），基于网格的方法（例如普通网格或四叉树）工作得非常好。特别是，如果您知道您的查询半径（玩家框大小），那么恰好这个大小的网格应该可以很好地工作。

许多游戏还使用了所谓的 BSP 树，即二元空间划分树。但为了获得良好的性能，AFAIK 通常在构建关卡时预先计算这棵树，然后只加载地图。