data-structures - 对于线段数据库，查找与矩形相交的所有线段

Question

给定大量线段，如何有效地找到与矩形相交的所有线段？一个典型的应用程序是 GIS 数据库，用于查找当前视野范围内的所有道路。对于点，这可以通过将点存储在 KD 树中来有效地完成，但是线段的相应数据结构是什么？

如果算法考虑到线宽，这是一个奖励，但零宽度算法是完全可以的。

Answer 1

您可以使用分段树，例如CGAL中存在的： dD Range 和 Segment Trees。该数据结构可用于所有维度，包括维度 2。

Answer 2

Consider the rectangle as a set of 4 line segments. you now have a set of n+4 line segments. apply a sweep line algorithm on the line segments. only perform intersections if the two line segments are from different sets. I.e one segment,is frm rectangle,and the other is from the database. Also, you may start the sweep line process from the first vertex of rectangle and end when all rectangle lines are completely processed.

you may also search on spatial hashing and line rasterization (for filling space cells with line data) . This may be even faster.

Answer 3

另一种可能的数据结构是R-tree。特别是优先级 R-tree将为您提供有保证的运行时间上限，但启发式变体在实践中可能更快。