c# - 找到一个点所属的最短线段

Question

我有一个 List<>一维段，每个段由 struct 表示包含开始和结束( x1 , x2 )。段可以重叠。该列表按开始排序 ( x1 )。

如何有效地找到包含特定点的最短线段 x ？

目前，我使用 list.BinarySearch找到 x 的第一段>= x1 , 这是有效率的。然后我继续通过列表一次一个片段，直到 x < x1 , 找到最短的段 x1 <= x < x2 ，效率不高。

如何改进该算法以获得更快的速度？我觉得可以，但我被卡住了。

这个问题不是 Shortest distance between a point and a line segment 的重复问题.

Answer 1

如果您允许 O(n log n) 预处理时间，您可以构建一个数据结构，在 O(log n) 时间内为您提供任何查询点的答案。对区间的所有端点进行排序(跟踪它们对应的区间)，并从左到右处理端点。还维护一个按间隔长度排序的间隔自平衡二叉搜索树。每次遇到左端点，就把区间加入树中，每次遇到右端点，就把区间从树中移除。此外，对于您遇到的每个端点，记录包含端点和前一个端点之间的子间隔的最短间隔(树中最左边的节点)。 (如果没有区间，记录“无”)所以最后你将得到一个 2n - 1 个子区间的数组，它知道是否有一个区间覆盖子区间，如果有，最短的区间是多少.然后给定一个点，您可以对结构进行二分搜索以找到包含该点的子区间，并报告是否存在包含该点的区间，如果有，最短区间是多少。