Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

2D-Cubic splines are given in parametric form (X(t), Y(t) and X(s), Y(s)). Every segment has it's own X and Y expression. And I want to find all intersection points. Some segments are intersecting some aren't.

At first I solved this problem using "line intersections method". Which has the simple idea of splitting a chosen pair of spline segments into 50-100 small subsegments and then intersection point was found by calculating both curves points vector and comparing the values of X(p),X(s) and Y(p) with Y(s).

It worked but it was not the solution I was looking for because it had two major flaws. First, it's slow even with "overlapping test" before comparison loop and the second problem was it could skip intersection point if it's too close to the previous one.

Is there a way to: 1) find if an intersection point is in the given parameter ranges (tmin, tmax) and (smin,smax) of two splines. 2) find an exact values of s and p at the intersection point.

I would like using analytic method if it exists. However the second part can be done iteratively but we have to know how many points are to find.

I understand that this is not a kind of question that has a short answer. I would appreciate it if you could provide the books titles (and author names) or other links and references to read about the good solution of this problem (2D cubic curves intersection).

share|improve this question
    
Even if there were an analytic method, the formulae are likely to be unwieldy for a general point configuration. If you can convert to $B$-spline format, IIRC there are special methods for finding the intersection of two such curves; see this for instance. –  J. M. Sep 29 '11 at 1:24
    
Thank you for this link, JM. It will probably be helpful in the future because I'd like to improve my program. But for now I'm going to try finding the better solution of the splines problem (better than my first attempt) for a couple of days. –  danny_23 Sep 29 '11 at 3:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.