Search code examples
mathgraphicsdrawcurve

Intersection between two curves

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?

Solution

  • 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