当前位置：文江博客话题详情

线段搜索的最佳数据结构是什么？

发布于 2024-12-22 03:27:03 字数 533 浏览 4 评论 0原文

我需要一个数据结构来查找落在矩形中的所有线段（在 C# 中，即使这不是主要问题）。

例如，线段 [(0,0) , (10,10)] 必须位于从 (5,5) 开始、大小为 (1,1) 的矩形中。

我尝试了 kdtree，但当他的一个点恰好在矩形中时，它只返回段。它不会将该段视为一条连续的线。

我需要什么样的数据结构才能有效地进行此搜索？
我搜索但没有找到任何适合这种情况的东西，即使它看起来很标准！

问题维度：6000条线段，平均20条线段在矩形内

重复排序：

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

爱要勇敢去追 2024-12-29 03:27:03

对于非点对象（线段不是点对象）R-tree 可能是比 kd-tree 更适合。如果您有少量线段（<50），将它们存储在向量中并始终测试所有线段可能是最快的方法。

回复收藏 0 原文

面犯桃花 2024-12-29 03:27:03

我不知道解决你的问题的标准算法，但我想到的第一个想法是将矩形表示为 4 条线，如果你有很多线段 - 找到所有线段和线的交点（通过对线段和线进行排序）线，然后“合并”它们的坐标）。
所以它是 N*log(N)+M*Log(M)，其中 N - 线段数，M - 方块数。

之后，您可以找到与正方形相交的线段，如下所示 (SquareHorizLine1Intersections UNION SquareHorizLine2Intersections) INTERSECT (SquareVerticalLine1Intersections UNION SquareVerticalLine2Intersections)

同样，集合交集和并集的复杂度为 K*LogK，其中 K 是集合的大小。或者，如果您使用数据结构“二项式堆”，甚至可以简单地记录（K）（还有斐波那契堆，这可能会更有效）。

所以这个算法看起来有 N*log(N) 复杂度。我希望这有帮助......或者你需要更好的？

回复收藏 0 原文

傻比既视感 2024-12-29 03:27:03

您可以尝试将延长的线段参数化为（y 轴截距、斜率）或类似参数。与给定线段相交的延长线的空间在（y 轴截距、斜率）空间中形成一个形状，您可以像这些线是点一样对其进行查询。（将垂直线作为特殊情况处理。）

取与任何矩形边界线段相交的线的并集，然后过滤掉未延伸时实际上不穿过矩形的线段。

// we will intersect against three of the rect's borders (the 4th's results are redundant)
borders = {(TopLeft, TopRight), (TopRight, BottomRight), (BottomRight, BottomLeft)}
// each border forms a shape in (y, slope) space defined by two intersecting half spaces
// we query the line space using something standard like kd-trees
lines1 = Union(borders.ForEach(LineSpace.Inside(ShapeOfSegmentInIntersectSpace(?border))))
// now filter out lines that don't cross the rect when extended
// since we already know they intersect when extended, the check is pretty simple
lines2 = lines1.Where(?line.BoundingRect.Intersects(rect))

You could try parametrizing the extended line segments as (y-intercept, slope) or similar. The space of extended lines intersecting a given line segment forms a shape in (y-intercept, slope) space that you can query against as if the lines were points. (Handle vertical lines as a special case.)

Take the union of the lines intersecting any of the rect's bordering line segments and then filter out segments that don't actually cross the rect when they aren't extended.

// we will intersect against three of the rect's borders (the 4th's results are redundant)
borders = {(TopLeft, TopRight), (TopRight, BottomRight), (BottomRight, BottomLeft)}
// each border forms a shape in (y, slope) space defined by two intersecting half spaces
// we query the line space using something standard like kd-trees
lines1 = Union(borders.ForEach(LineSpace.Inside(ShapeOfSegmentInIntersectSpace(?border))))
// now filter out lines that don't cross the rect when extended
// since we already know they intersect when extended, the check is pretty simple
lines2 = lines1.Where(?line.BoundingRect.Intersects(rect))

回复收藏 0 原文

~没有更多了~