線段搜索的最佳數據結構是什麼？

我需要一個數據結構來查找落在一個矩形中的所有分段（在C＃中，即使它不是主要問題）。線段搜索的最佳數據結構是什麼？

例如，段[（0,0），（10,10）]必須位於（5,5）開頭的長方形中，大小爲（1,1）。

我試過kdtree，但是隻有當他的一個點正好在矩形中時才返回段。它沒有看到該部分爲連續線。

我需要什麼樣的數據結構來有效地進行這種搜索？
我搜索，但沒有發現任何東西，即使它看起來很標準！

問題尺寸：6000段，平均20線段是在矩形

排序重複的：

來源

2011-12-19 Cyril Gandon

你爲什麼不寫自己的？它看起來很直截了當。 – 2011-12-19 09:12:01

「落在」你的意思是段相交矩形？ – 2011-12-19 10:39:31

那麼，相交是一種情況，另一種情況是當段真正在矩形中時 – 2011-12-19 15:31:45

對於非點對象（線段不是點對象）R-tree可能比kd-tree更適合。如果你有少量的線段（< 50），將它們存儲在一個向量中並且總是測試它們可能是最快的方法。

來源

2011-12-19 11:48:25

我不知道你的問題的標準算法，但我頭腦中的第一個想法是將矩形表示爲4行，並且如果有許多行段 - 找到所有行段和行的交集（由排序線段和線條，然後「合併」它們的座標）。
所以它是N * log（N）+ M * Log（M），其中N - 線段的數量，M - 平方數。

之後，你可以發現，廣場相交爲（SquareHorizLine1Intersections UNION SquareHorizLine2Intersections）的相交點（SquareVerticalLine1Intersections UNION SquareVerticalLine2Intersections）

重新設置交叉路口和unitions有K * Logk值，其中K爲大小的複雜線段組。如果你使用數據結構「Binomial heap」（也有斐波那契堆，這可能會更有效），甚至可以簡單地記錄（K）。

所以這個算法看起來具有N * log（N）複雜度的kike。我希望這有助於...或者你需要更好？

來源

2011-12-19 11:52:49

您可以嘗試將擴展的線段參數化爲（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))

來源

2011-12-19 15:26:19

線段搜索的最佳數據結構是什麼？

回答

相關問題