Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane Question summary: what are the known efficient algorithms to find the intersections of 1-dimensional curves living on a 2-dimensional plane?

Detail: I have a set of 1-dimensional curves on a 2-dimensional plane. Each curve in reality is a set of points connected by straight lines (therefore more like a polygon), and is the numerical solution of a given differential equation. I want to find all the intersection points of the 1-dim curves.

Here are what I tried so far.

Method 1. Use interpolating functions &amp; root finding algorithms.

1.1 For each object C_n, cut it into subobjects C_(n, i) at inflection points of C_n, i.e. at dx/dy = 0 and at dy/dx = 0 when we consider the 2-dim plane as the x-y plane.

1.2 For any two subobjects C_(n, i) and C_(m, j) check if they have a common x- and y-domain. If they have, find interpolating function for each of them, y = f_(n, i)(x) and y = f_(m, j)(x), and find roots of f_(n, i)(x) - f_(m, j)(x) = 0.

Method 2. Use a hash table.

2.1 Consider the 2-dim plane as a hash table, where each element is a square bin of a small size, comparable to the resolution of the 1-dim curves.

2.2 Run along each C_n, and when it hits a bin at (i, j), record the hit in the table with (i, j) as a key and {n} as its element.

2.3 Retrieve keys with more than one element.

A Practical issue with Method 1 is there are many things to consider case-by-case when using interpolation and root-fiding algorithms, especially when there are nearly horizontal/vertical curves and when there are more than one root for a given pair of subobjects.

For Method 2, a big issue is that the physical size of the hash table gets big easily, for example I need about 10GB of RAM to deal with my current research project even at its elementary stage.

I suspect there should be previous studies for similar problems, but my background &amp; research area is theoretical physics and I don't know much about such studies. I tried googling but was not successful so far.

On a side remark, I think that a generalization of this problem, i.e. finding intersections of numerically implemented n-dimensional objects in an m-dimensional space may be quite interesting, and I wonder if there is any previous study about such a problem.

Thank you very much in advance.
http://en.wikipedia.org/wiki/Sweep_line_algorithm

(Or open any standard book on Computational Geometry).

For practical implemented algorithms, see CGAL http://www.cgal.org/

If your main problem is numerical issues, then this can be challenging in practice. A lot of practical work on this problem was done by Dan Halperin in Tel-Aviv University.