1

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.

Ghost
  • 1,777
  • 6
  • 31
  • 44
  • 1
    If you know each line will always have exactly two points, you should consider using a `std::pair` instead of a `std::list`; a `std::pair`'s a much simpler object, so there's less overhead associated with it, both in time and space. – Xavier Holt Jan 19 '13 at 15:07

1 Answers1

2

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.

Community
  • 1
  • 1
borrible
  • 17,120
  • 7
  • 53
  • 75