Two Bezier Paths Intersection Point

I have two paths on two separate layers/views that intersect at only one point. I need to find the point of intersection. I've searched and can't seem to find how this is possibe.


The light grey vertical line intersection point with the blue line graph. Both paths are UIBezierPaths. Is there a method to get a array of insection points? Which in my case would return one result?


Replies

(Inline images don't appear in forum posts. If you want us to see your image, you'll have to link to it in an external location, which may put your post in moderation.)


Finding bezier intersections isn't easy. It requires solving a higher order polynomial and/or approximating via subvdivision. I tried searching the web for "intersection of bezier curves", and there were plenty of possibilities worth following up.


If you want a specific reference, I would suggest this book:


books.google.com/books?id=fvA7zLEFWZgC&dq=bibliogroup:%22Graphics+gems+series%22&hl=en&sa=X&ved=0ahUKEwj3kcGNgLfWAhVO5mMKHVCLCQ0Q6AEIRjAH


which seems to have this companion source code repository:


github.com/erich666/GraphicsGems


(There may be more recent solutions available.)

Reinforcing Quincey conclusion, I found this interesting artcile (to understand why it is difficult, unfortunately not to provide a solution):


h ttp://www.truetex.com/bezint.htm


You can read that :

Locating all the intersections between two Bezier curves is a difficult general problem, because of the variety of degenerate cases.

Consider just the "simple" case, where two Bezier curves intersect at singular point(s). The problem is to find the singular minima (or zeroes) of an N-dimensional non-linear distance function given two N-dimensional Bezier curves. This is the sort of problem about which Press et al. state, "There are no good, general methods for solving systems of more than one nonlinear equation. ... there never will be any good, general methods." [1] We will illustrate with some two-dimensional examples.


So don't exhaust yourself by trying to find a generic solution. The best you can is to handle simple cases, such as intersecting a bezier path with a line. It's easier, but remains tricky

h ttps://www.particleincell.com/2013/cubic-line-intersection/


You simplify even more with a vertical line (which I understand is your case):

h ttps://stackoverflow.com/questions/35650946/line-and-curve-intersection-in-python-using-bezier-curve-and-vertical-line


EDITED. Hope that could help as well.

I thought of an approximate solution:

if you compute, let's say 1000 points corresponding to curviline absciss (t) for each curve

Then search in the 2 arrays of 1000 points which are close enough (define the threshold so that it is less than 1 pixel)

You would get a list (array) of near-miss, which is an approximate result of what you are looking for.

This to build the arrays:

h ttps://stackoverflow.com/questions/14174252/how-to-find-out-y-coordinate-of-specific-point-in-bezier-curve-in-canvas

This library does exactly what you want: https://github.com/adamwulf/ClippingBezier