What is the best datastructure for line segments searching?

Question

I need a datastructure to find all segments falling in a rectangle (in C#, even if it is not the main problem).

For exemple, the segment [(0,0) , (10,10)] must be in the rectangle begining at (5,5) with the size (1,1).

I tried kdtree, but it returns only segment when one of his point is exactly in the rectangle. It doesn't see the segment as a continous line.

What sort of datastructure do I need to do this search efficiently?
I search but didn't find anything for this case, even if it seems very standard!

Problem Dimension : 6000 segments, average 20 line segment are in the rectangle

Sort of duplicate :

Why don't you write your own? It looks straight forward to me. — Azhar Khorasany, Dec 19 '11 at 09:12
by "falling in" do you mean the segment intersects the rectangle? — Martin DeMello, Dec 19 '11 at 10:39
Well, intersect is one case, the other is when the segment is entierly in the rectangle — Cyril Gandon, Dec 19 '11 at 15:31

score 1 · Answer 1 · answered Dec 19 '11 at 11:48

1

For non-point objects (line segment is not a point object) R-tree may be better suited than kd-tree. If you have a small number of line segments (<50), storing them in a vector and always test all of them may be the fastest way.

answered Dec 19 '11 at 11:48

Juraj Blaho

13,301
7
50
96

score 0 · Answer 2 · edited Dec 19 '11 at 13:28

I don't know a standard algorithm for your problem, but the first idea that came to my mind is to represent rectangles as 4 lines and if you have many line segments - find intersections of all line segments and lines (by sorting line segments and lines and then "merging" their coordinates).
So It is N*log(N)+M*Log(M), where N - number of line segments, M - number of squares.

After that you can find line segments that intersects the square as (SquareHorizLine1Intersections UNION SquareHorizLine2Intersections) INTERSECT (SquareVerticalLine1Intersections UNION SquareVerticalLine2Intersections)

Again set intersections and unitions have a complexity of K*LogK, where K is the size of set. Or even simply log(K) if you use data structure "Binomial heap" (there is also Fibonacci heap, that could be even more efficient).

So this algorithm looks kike having N*log(N) complexity. I hope that helps... Or you need better?

Craig Gidney · Answer 3 · 2011-12-19T15:39:14.560

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))

What is the best datastructure for line segments searching?

3 Answers3