Intersections in C.a.R.

C.a.R. can now create intersections of various objects. These objects are

• lines, including line segments and rays,
• circles,
• conic sections,
• functions and curves,
• automatic tracks.

On all of these ojects, C.a.R. can also fix points.

This page describes the algorithms used to intersect the objects and to project points to these objects. It also mentions some problems, which might occur, and discusses the efficiency of the algorithms.

Simple Intersections

Clearly, some objects are easier than others. E.g., most of the time it is quite easy to compute the intersections of a line and a circle. C.a.R. uses a stable algorithm for this. Note, that there might be troubles, if the line is tangent to the circle. As you will notice, when you try, C.a.R. can handle this situation in almost all cases, using an internal epsilon, which is added to the circle radius.

However, circles can be reduced to arcs, and lines can be reduced to line segments or rays. In these cases, the program needs to check, if the computed intersection point still is in the restricted sets. Here, the same epsilon is used to include the point in case of doubt. Note, that it is possible to set the intersection point such that it ignores the restrictions.

For lines and circles, it is also quite easy to project a point to the object. An exception point is the midpoint of the circle, which is projected exactly in positive x-direction. For segments and arcs, some care has to be executed. C.a.R. will find the closest point for line segments and rays, and in most cases for arcs.

Difficult Intersections

The most difficult case is the intersection of two parametric curves. Since nothing can be said about the algebraic equations, derivatives are not available, and we need to rely on numerical algorithms without derivatives.

First of all, we need to be able to project points to curves. For parametric curves this is simply done by approximating the curve as a set of line segments. Walking through the line segments, we can project the point to each of them and choose the closest projection. Some line segments can be discarded at once, since its end points are too far away from the point. Thus it is a good idea to remember the previous segment that yielded the closest distance for the next computation.

For lines, circles and conic sections, the projection can be computed directly using their algebraic equations. The most difficult case is the conic section. We have to minimize the distance to the points on the conic section. This is a Lagrange problem. The equations are rather lengthy, but can be handled with Maple. In the end, a fourth order polynomial has to be solved. C.a.R. uses an open source solver for this, which I found in the Internet. This solver implements the well known formulae, and improves the result with one Newton step. It remains to check the four solutions for the point of closest distance.

If we have an algorithm to project to curves, we can use it to intersect two curves. We project to one and then to the other curve. This simple procedure converges in most situations. However, it can be improved considerably, if the projection is locally orthogonal, and the closest projection is such a projection. Since we know the orthogonal direction to each curve, we can compute the tangents, and try to intersect the tangents. This improved algorithm converges very fast. C.a.R. uses it, whenever tracks, parametric curves, or conic sections are involved.

The result is a stable and accurate computation of all these difficult intersections.

Problems

The most important problem is efficiency of the algorithm. Clearly, the projection of a point to a parametric curve described above is not very efficient. However, it is accurate. A better algorithm can be made, which might fail sometimes to a local optimum. Since, we compute all points of the curve anyway, whenever the curve is painted, the problem might not always become obvious. But we need to keep an eye on it.

Tracks look more complicated, but they are not. In fact, C.a.R. simply remembers the points of the track and treat it like a parametric curve as a set of line segments.

Rene Grothmann (Admin) 2007/01/10 15:58

newfeatures/intersections.txt · Last modified: 2007/01/12 11:14 by rene        