On Fri, Jul 13, 2007 at 03:00:46PM -0400, sen1 at math.msu.edu wrote:
> Hello,
> Using the function 'find_root' one can find an intersection of
> two explicit curves
> x -> [x, g(x)]
> x -> [x, h(x)]
>
> in an interval [a,b] such that g - h have different signs at the
> endpoints.
> Does maxima have an analogous routine to find the intersection of two
> parametrized curves
>
> g: t -> [x(t), y(t)], 0 < t < 1
> h: s -> [u(s), v(s)], 0 < s < 1
>
> where it is known that such an intersection exists?
>
> Note: the parameters are different, so any intersection requires the
> solution of a pair of equations If not, does anyone know a good
> reference for such a routine.
I assume you're looking for numerical results because you mention
find_root. So you're looking for (s,t) such that
[x(t),y(t)]=[u(s),v(s)] and t and s are within some known rectangle of
the s,t plane. Could you perhaps rephrase this as a minimization
process and use lbfgs?
minimize ([x(t),y(t)] - [u(s),v(s)])^2 with a starting condition for t
and s near your guess?? I know this doesn't have guaranteed
convergence, and it's based on a modified newton's method, but perhaps
it is more stable or better than the method that you were using?
Another possibility is to construct a low order polynomial
approximation of the minimization above, perhaps by randomly selecting
points within your rectangle, then fitting the least squares
polynomial surface through those points, then find the minimum of
this, and iterate.
The third thing to try is to spline interpolate the two curves, solve
for intersections of the spline interpolant, and then reinterpolate
over a smaller interval until you can zero in on the true solution.
Unlike in 1 dimension, it seems that it's hard to guarantee
convergence of any "bisection" type method. In 1 Dim you look for
alternative signs on the endpoints of the interval, and use continuity
to deduce that a root exists in the interior of the interval. In 2
Dim, do we have a similar way to conclude that an intersection exists
on the interior of a rectangle?
> One special case of interest to me is the one in which the curves have
> a non-degenerate crossing; i.e., have linearly independent tangent
> vectors at the crossing.
I am pretty sure that maxima has nothing built in for this specific
problem. I know you've discussed this before on the list. Everything I
know about curve intersection comes from the computer graphics field
where the curves tend to be bezier splines, and the methods are
iterative and low-accuracy. Also the curves rarely oscillate
erratically etc.
I'm fairly interested in what you come up with. Perhaps if you post an
example problem I'll be motivated to write some code.
--
Daniel Lakeland
dlakelan at street-artists.org
http://www.street-artists.org/~dlakelan