0
$\begingroup$

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 & 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 & 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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.