Speeding up segment/set of segment intersection

Question

Suppose you have a set of segments in R^2 (call it S). Every segment is contained in a box of dimension WxH (so, the set S has four additional segments, one for each side of the box) and a segment s to be addedd to S. The segment s starts from point A (that will belong to one of the segment in S) and ends at point B. What i want to compute is the point B' such that B'belongs to one of the segment in S and A-B' does not intersect any other segment in S. Is there a wat to compute B' without using a brute-force algorithm (that is, intersecting AB with every other segment in S)?

Answer 1

"Real-time Collision Detection" by Ericson (table of contents) is a great resource for solving problems like this. Chapter 7 spatial partitioning lists a number of methods suitable for solving such problems.

Consider starting with Octrees, KD-Trees or spatial hashing. They are all reasonably easy to implement, and will make the problem go from O(n^2) to (from memory) O(n log n)