CODEWITHSUNDEEP
c++algorithmsearchstlintersection
Ghost
Ghost

Reputation: 1835

How to check if a segment is intersecting any line?

I have a std::list of lines. Each lines is a list of 2 CPointobjects, marking the start and end point of a line

std::list<std::list<CPoint>> edges;

I then have another line (a list of 2 CPoints), which I want to test for intersection with any of the lines of the main list. How can I do this? possibly an intersection test within a loop for iteration.

Upvotes: 1

Views: 1023

Answers (1)

borrible
borrible

Reputation: 17376

A basic approach would be, as you suggest, to iterate through all your lines and then applying a line intersection algorithm. Asymptotically this may be the best; after all your new line might well intersect all of the other lines.

In many line intersection algorithms we apply a bounding box test first. Very roughly, making sure that the rectangles containing the two lines being compared overlap. If they do not overlap the lines cannot intersect, although if they do a more comprehensive test would need to be applied.

The bounding box test is seing if the x-interval of the two boxes overlaps and the y-interval of the two boxes overlaps. There are data structures that are specifically designed for efficient interval intersection checks. Take a look at information on interval trees. Such a structure would mean, in many cases, that you would be performing your bounding box test on fewer lines; the data structure discarding some lines (via their intervals) before the test needs applying.

Upvotes: 2

Related Questions