<p><a href="http://en.wikipedia.org/wiki/Sweep_line_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Sweep_line_algorithm</a></p>

<p>(Or open any standard book on Computational Geometry).</p>

<p>For practical implemented algorithms, see CGAL <a href="http://www.cgal.org/" rel="nofollow">http://www.cgal.org/</a></p>

<p>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. </p>

CC BY-SA 3.0
2015-03-23T04:41:10.510Z
2015-03-23T04:41:10.510Z
Sariel Har-Peled
<p>Question summary: what are the known efficient algorithms to find the intersections of 1-dimensional curves living on a 2-dimensional plane?</p>

<p>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.</p>

<p>Here are what I tried so far.</p>

<p>Method 1. Use interpolating functions &amp; root finding algorithms.</p>

<p>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.</p>

<p>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.</p>

<p>Method 2. Use a hash table.</p>

<p>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.</p>

<p>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.</p>

<p>2.3 Retrieve keys with more than one element.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>Thank you very much in advance.</p>

<ds.algorithms><computational-geometry>
Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane
Chan Y. Park
# Finding intersections of numerically implemented 1-dimensional curves on a 2-dimensional plane

(Asked by: username_0 on 2015-03-18)

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.

**Tags:** ds.algorithms, computational-geometry


---

## 1 answers

### Answer by username_1 on 2015-03-23. Score: 1 | Accepted answer

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


---

