line sweep algorithm for detecting intersections, a la Bentley Ottmann

[Jon]

Greetings,

I need a fast(er) method for detecting all intersections of a line with itself. The line is defined by x,y coordinates that change in time and eventually intersect. This is a numerical model of a river centerline over long time scales, if that helps with the picture. Here's a video of a simulation: http://www.youtube.com/watch?v=VR0SFmz6JRc

Each time step I have to check for intersections. I am currently using intersections.m from the File Exchange by Douglas Schwartz: see http://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections , but it operates on O(n^2) time. I know there are algorithms like the Bentley-Ottmann that operate on O(n*log(n)) time, but I haven't found any implementations in Matlab. I've spent hours now trying to create MEX files from C implementations, but I can't find all the necessary libraries for the algorithms I've found online. I've also tried a java implementation but again, the libraries weren't complete or available.

Obviously I'm avoiding coding this in Matlab myself for a couple reasons. I don't think Matlab is well-suited for sweep-line algorithms (but I'm still trying to wrap my head around them), so I'm wondering if programming in Matlab script will be that much faster. I suppose it depends on n, but also the way its coded could make a huge difference.

I recently increased n from ~1000 to ~4000, and the model runtime has gone from ~4 hours to ~4 days, hence my desire to implement a faster intersection method. The code calls intersections.m three times per time step, so a faster algorithm would be wonderful. intersections.m was the second-longest time hog according to the profiler (much of the time is spent on repmat).

Any suggestions, hints, or help?

Thanks.

[Bruno Luong]

This is slow because it is MATLAB:
http://www.mathworks.com/matlabcentral/fileexchange/27673-2d-polygon-edges-intersection/content/polygonstuff/poly2poly.m

You might convert it to MEX.

Bruno

[Alan_Weiss]

I wonder if it might be worthwhile to lay a grid down on the space, and
first look for line segments that are in each grid element, and then
look for intersections only among those line segments that are in each
grid element. If you have N segments in total and G grid elements, then
instead of having to compare N^2 segment-segment intersections, you
might need only something of order (N/G)^2 comparisons, so it might be
faster overall (I don't know how much time the initial segment-to-grid
sorting will take, but I think it is O(N)).

Alan Weiss
MATLAB mathematical toolbox documentation

[Jon]

Alan_Weiss <awe...@mathworks.com> wrote in message <l4dnmb$qv5$1...@newscl01ah.mathworks.com>...

Hm, interesting thought Alan. I think I've seen that mentioned before. You're right that the initial sort is O(N). Do you think there's any way that I can exploit the geometry of the problem to make the most efficient boxes? I do know that the probability of one line segment intersecting another becomes quite tiny after some downstream distance L, so perhaps I could simply look for intersections in x(node:node+L). That seems to be along the lines of the grid method, but maybe simpler. Thanks for your input.

[Jon]

"Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <l4d53a$bkr$1...@newscl01ah.mathworks.com>...

Have you looked at intersections.m? It appears fundamentally different than poly2poly, as it solves a linear system of equations of the line segments. I think I tried poly2poly a long time ago and it was substantially slower, but I could be mistaken.

Unfortunately I don't know any other programming languages very well--this is why I am stuck trying to copy someone else's C/Java implementations.

[Jon]

"Jon" wrote in message <l4bkf3$d35$1...@newscl01ah.mathworks.com>...

In case this thread is of interest to anyone, I ended up using the rangesearch function in the Statistics and Machine Learning toolbox. It builds a kd-tree for optimal nearest-neighbor searching.