-1

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?

7
  • This seems more like a math problem than a programming problem, and would therefore be off topic. if it is a programming problem, please tell us what language and post any code you have.
    – ewok
    Dec 6, 2011 at 17:36
  • Also, if this is homework, please tag it as such.
    – ewok
    Dec 6, 2011 at 17:36
  • @ewok algorithm questions are supported here, there are numerous examples of questions more mathematical than this. Dec 6, 2011 at 17:40
  • @ewok: As a Physics Student I could be tempted to say programming is just math... this is an numerical algorithm, so it can be considered a programming question. It is not homework, but to avoid more comments about it, I added the tag. Dec 6, 2011 at 17:44
  • 1
    Also, I would say that programming is a subset of math, rather than being the same as math. if this is related to an algorithm that needs to be implemented in code, then it is fine, but if it is simply "what is the mathematical way to solve this problem", then I think it belongs on math.stackexchange.com. Otherwise, why are there 2 different sites?
    – ewok
    Dec 6, 2011 at 17:48

2 Answers 2

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

0
0

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.

1
  • Quadtree is a good tip; lines can intercept on anyplace, and here we are dealing with segments. Dec 6, 2011 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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