From: rusin@moriarty.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis Subject: Re: Roots with rotation Date: 2 Dec 1996 19:36:53 GMT In article <32A03BAE.7E46@cenplus.com>, Fred Siegeltuch wrote: >Given: >Two real continuous functions: f(x) and g(x), a rotation of g(x)about >the origin, and a bounding rectangle {(Xl, Yl), (Xh, Yh)}. > >Find: >The all intersections of f and rotated g within the bounding rectangle. > >I need this problem solved (approximately) for a piece of educational >software I am trying to write. Any suggestions appreciated. I hope the educational software helps teach the difference between a function and its graph. I assume you are rotating the latter. The graph of g is the set of points of the form { (x,y): y=g(x) }. If you rotate a point (x,y) counterclockwise through an angle of theta, you end at the point (x cos(theta) - y sin(theta), x sin(theta)+y cos(theta) ); equivalently, the coordinates of the original point may be recovered from the coordinates of the new point, (x',y') as x= x' cos(theta) + y' sin(theta) y= -x' sin(theta) + y' cos(theta). so that a point (x', y') is in the rotated graph iff the (x,y) so described is in the original graph, that is, iff -x' sin(theta) + y' cos(theta) = g( x' cos(theta) + y' sin(theta) ). This point is in the intersection of (the rotated graph of g) and (the graph of f) iff it satisfies both the above condition and the condition y' = f(x'). In particular, you can find the y-coordinates of such points easily from the x-coordinates, and those x-coordinates are the solutions of -x sin(theta) + f(x) cos(theta) = g( x cos(theta) + f(x) sin(theta) ). Now, your ability to solve such an equation depends on the type of functions f and g are. If both are polynomial, then the above is a polynomial equation (of degree equal to deg(f)*deg(g) ), and so has at most a finite number of solutions; the graphs meet only finitely many times, for any fixed theta. Other functions likely to be of interest in elementary educational software will also lead to only finitely many intersections within a compact set, although of course a function like f(x)=sin(1/x) will allow for infinitely many functions near the origin. You can adapt the discussion above to curves defined implicitly (rotated curves occur frequently in the context of conic sections, for example). Then the intersection of (the solution set of f(x,y)=0) and (the rotation of the solution set to g(x,y)=0) may be computed by solving two equations in two unknowns, which is perhaps best accomplished via Newton's method (viewing F=(f,g) as a single function F: R^2 -> R^2), although if e.g. F is a polynomial map of low degree one may use resultants to reduce this to a one-variable problem. It would be embarassing to release educational software which did not screen its allowed input to prohibit a user from trying functions for which the algorithms encoded within do not work well. Rotating the graph of y=x^100 by theta=0.01 and asking for its intersection with y=x^99 will require careful treatment. dave ============================================================================== [So I wrote some notes to myself but never sent them... -- djr] ============================================================================== (Sigh) Why do I do this? Query: where does the graph of y=x^99 cross that of y=x^100 if the latter is rotated through an angle of theta? Relevant equation is seen to be: either x=0 or 98 99 98 100 f(x): = c x - x (s x + c) - s = 0 where s=sin(theta), c=cos(theta). Clearly one solution is at x=0. Are there others? (i.e., roots of f? After all, it's only a 9899-degree polynomial...) Since this is an odd-degree polynomial with negative lead coeff and negative value at 0 [assuming 0 < theta < pi here], there's at least one negative root x. For example, when theta=0.01, there's one at -0.947627044545. Others still? Well, let's look at slope. Deriv of f is x^97*following: 98 100 99 98 99 (der) 98 c - 99 x (s x + c) - 9800 x (s x + c) s This in turn has a derivative equal to 100 2 98 2 4 2 - 99 c (t Y + 1) (980001 Y t + 19602 t Y + 1) where t=tan(theta) and Y=x^98/tan(theta). Solving for t^2Y in the quadratic shows no real roots, so this 2nd deriv is negative for all real Y (no matter what theta), i.e., the 1st deriv factor "der" is decreasing for all x. Thus the only critical points of f occur at x=0 and at the one value of x making (der)=0. Rewriting der as 99 - x (s X + c) (9899 s X + 99 c) + 98 c with X=x^98 shows that the critical point occurs where x= c 98 ----------------------------- 99 (s X + c) (9899 s X + 99 c) Since the function f may be written 100 c X - X x (s X + c) - s, when this condition holds f equals 2 2 c (9801 X t + X - 9899 t X - 99 t) ------------------------------------ 9899 t X + 99 So we can see that f has only the one (negative) root or three according as this relative maximum value of f is positive or not. (For some t it is, for others it isn't). The borderline cases would be those for which this extreme value of f is exactly zero. If this happens, we can solve for X to get 2 2 4 1/2 - 1 + 9899 t +- (1 + 3861398 t + 97990201 t ) 1/19602 ------------------------------------------------- t Comparing to the condition relating x and X shows x must be 166442626947036914196392708547441272754174391385070720783418386394246498487848\ 144489532867529310267931330402683286369274634556991752057008774985379841708812\ 921998679540467222357937444992535070018680969095217346220353265330397418711625\ 461039462920736899162011747125187489437575855756435085186703913184717559452671\ 494033145104448613835321011109264966478953167255668416545268488793737652476590\ 669432783679150171789366044832033929166848 / 99 2 2 4 1/2 99 / c (19601 + 9899 t + (1 + 3861398 t + 97990201 t ) ) / 2 2 4 1/2 (1930699 + 97990201 t + 9899 (1 + 3861398 t + 97990201 t ) ) At the same time, its 98th power should equal the above X. This gives an equation to solve for t. I get a root near theta=.00127, giving t=.0012700007, x=0.9730323 and X=.068623. It appears pictorially that this is the only root: increase theta, and the "bend" in x^100 is too high to touch x^99; decrease it, and the "bend" sinks lower, forcing the point of intersection towards x=1 (when theta=0) and beyond (as theta decreases).