Closest approach of line segments

  • Thread starter Lindley
  • Start date
7
0
I have two sets of line segments, A and B. My goal is, for each segment in A, I want to find all segments in B which approach within some threshold distance.

Clearly this can be done in O(n^2) easily enough, but I think it's possible to do better. For instance, if I were working with points instead of lines, I could construct a KD-tree and do the lookup that way in O(n log n).

At first I was thinking perhaps I could construct 2 KD-trees, one for each end point, and do something with that. But it's possible one segment could approach or even intersect another without their endpoints being anywhere nearby, so that won't work. Now I'm trying to think if there's some way to do it with a plane-sweep algorithm.

Any ideas?
 
236
0
There's not a computer science forum here? Wow, no there isn't. That sucks. Algorithms don't really belong to topology or geometry.
 
7
0
As a computational geometry problem, I figured this was close enough.
 

Related Threads for: Closest approach of line segments

  • Posted
Replies
2
Views
2K
Replies
0
Views
2K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
2
Views
6K
  • Posted
Replies
0
Views
1K
Replies
1
Views
3K
Top