How to efficiently find line-segment intersections between two sets?
-
05-11-2019 - |
문제
So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, at the beginning of every timestep, that no intersections exist within the set of all line segments that constitute the surface, and at every timestep, a fixed number of nodes is altered (if this produces intersections, the simulation resets). Let's call the set of all lines after an alteration N and the lines that have been altered K. I then know that I should only look for intersections within K and between K and {N - K}, because I know there can be no intersections within {N - K}. This is equivalent to wanting to find intersections between K and N.
When I first tackled this problem, I just implemented sweepline, but now I realize that it finds intersections within a set. As far as I can tell, adapting the algorithm to find intersections between segments in a set X and segments in a set Y is quite tricky; I haven't been able to work that out. The only things I thought of is doing brute force (which amounts to |K| * |N|) and just ignoring K and applying sweepline, which is |N|lg|N|. If there's a way to combine the best of both approaches,I'd expect there to be a big difference in the performance of my code. Is there such a way?
올바른 솔루션이 없습니다