Intersection between two curves

Question

I need to obtain the intersection of two curves. The problem I'm facing can be stated in the following way:

Given two curves C1 and C2, defined by N1 and N2 points connected by straight lines, obtain all the intersections of C1 with C2. Both curves don't intersect themselves.

I tried several approaches, but none seems to work so far. Any guess?

Answer 1

The easiest way is to test all pairs of segments, one from each curve. If that is too slow, try a strip tree. The paper below can be found at the author's web site.

Ballard, D. H. (1981), Strip trees: a hierarchical representation for curves, Communications of the ACM, v.24 n.5,310-321

Answer 2

Since your curves are comprised of line segments, I would suggest using a spatial tree (e.g. a quadtree) to only check segments that are in proximity to each other. This will reduce the complexity of your algorithm from O(N1 N2) to O(N log N) (where N = N1 + N2), assuming that the number of very close intersections is small.

Other than that, you can find intersections in this way.