2

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

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

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

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

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

重复排序：

4

3 回答 3

1

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

于 2011-12-19T11:48:25.110 回答
0

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

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

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

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

于 2011-12-19T11:52:49.707 回答
0

您可以尝试将扩展线段参数化为 (y-intercept, slope) 或类似的。与给定线段相交的延长线空间在（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))
于 2011-12-19T15:26:19.213 回答