Find the intersection of a pair of QuadCurve2Ds

Question

Is there an easy way to approximate the points (if any) where two instances of QuadCurve2D ?

That is, how could I calculate the coordinates of the red dots in this diagram? There is no obvious method for this in QuadCurve2D .

(note: the points are not accurate, because I manually adjusted them for the diagram. Also pay attention to the “missing” fourth point, which does not lie on the segment of the curve, even if it lies on an (infinite) parabola.)

These two segments of the curve were created using the following code:

 QuadCurve2D curve1 = new QuadCurve2D.Double(-2.00, -2.00, +0.75, +4.75, +2.00, -0.75); QuadCurve2D curve2 = new QuadCurve2D.Double(-2.50, -0.75, +5.50, -0.50, +0.50, +1.25); 

Note 2: I would also like to be able to intersect a straight line and a quadratic curve, but I assume that this can be solved by setting one of the control points in a colinear with end points.

Answer 1

Depending on whether you are interested in approximate or accurate solutions (up to double accuracy). For approximate purposes, you can simply parameterize the curves as some function f ( t ), and then perform some interpolation to find values ​​for t that minimize the distance between the curves.

For exact solutions, you will need to find four points at which two parts of the conic intersect. There is a short paragraph about this on wikipedia . The book Perspectives of Projective Geometry has a longer section explaining the details. Of course, there are versions available for different languages; one for Asymptote comes to my mind. The implementation for their general case looks rather intimidating, so maybe they are doing something too complicated.

Once you have all four intersection points, you still have to decide which ones are on the side of the conic section bounded by the end points of your QuadCurve, but this should be easy to compare. Thus, you can perform the following three actions:

• Calculate the matrix of sections of conical sections from end points and control points
• Intersecting conical sections using elements of degeneracy in their bundle
• Determine if these intersections are between endpoints.

If you have a problem with the mathematical details of one of these steps, it’s best to ask for a math stack exchange . Not only do people have more experience in solving mathematical problems, the MathJax functions for typesetting mathematics will make the answers much more readable than you would expect here.

As for your note 2 on the line: it is much simpler because if you express this problem in terms of coordinates, you will only get a quadratic equation instead of an equation of degree 4 for a naive approach to the general problem and another 3rd degree if you solve it as described above. You can write a general aproach in such a way that the intersection of the conic with the line is a step in the solution, so having a way for this can work quite well.

Answer 2

A pragmatic approach will create two Area by adding curves and closing the results. The intersection of these Area should have all the origin intersection points as the endpoints of some segments. So, iterating over the resulting path, ignore any Bézier control points, and for each counter endpoint of the segment, check if it lies on the original curves.

Or look at the implementation of how Area does this, and see if you can adapt it to your needs. If your licensing allows you to enable the GPL2 code.