Discussion :

[méphistopheles]

Bonjour.

J'aimerais pouvoir trouver le point d'une surface de révolution le plus proche d'une sphrère qui se trouve à l'interieur de cette surface.

Il me semble (corrigez-moi si je me trompe) que le problème peut se ramener à celui de la proximité d'un point (centre de la sphere) à la courbe.

la question devient donc: comment trouver le point le plus proche d'une sphere sur une courbe.

si vous en avez une idée...

merci

[FrancisSourd]

Oui, à une translation près, tu peux dire que ton point est l'origine. Cela revient donc à chercher le point (x,f(x)) le plus proche de l'origine (en supposant que f décrit la courbe de la surface de révolution).

Donc il faut minimiser x²+f²(x)

Soit on étudie à la main la fonction, soit on utilise une méthode numérique (style Newton pour rechercher les minima locaux de cette fonction.

[méphistopheles]

heu à la main, je vois pas tropcomment faire vu que ma sphere peut se trouver n'importe-où lors de l'execution.

pour la méthode de Newton, j'ai bien trouvé ceci mais je dois dire que je n'ai pas compris ce qu'il appelait Dg(x k)^-1 (d'inverse de la dérivée ? la fonction réciproque ?)

Merci.

[Zavonen]

Il faut couper par un plan passant par l'axe de la surface de révolution et le centre de la sphère. On tombe en dimension 2, on est ramené à trouver, pour un cercle situé dans la concavité d'une courbe, à trouver le point de ce cercle le plus près de la courbe.
On procède ainsi:
On détermine d'abord la projection orthogonale du centre C sur la courbe. On peut pour cela paramétrer la courbe t-->M(t) et chercher le point M pour lequel le vecteur tangent v(t) est orthogonal à CM(t), par exemple en annulant le produit scalaire.
Cela fait, le point cherché est l'intersection de CM avec le cercle.

[méphistopheles]

Il peut exister plusieurs vecteurs normaux passant par le centre du cercle. (c'est même probable qu'il en existe une infinité par exemple si la courbe est periodique.)

donc, comment définir le plus petit sans calculer à chaque fois la distance.

[Zavonen]

C'est vrai, mon truc ne marche que si la projection orthogonale est unique. Il y a beaucoup de contre-exemples:
Sphère centrée sur l'axe d'un paraboloïde de révolution
Sphère centrée sur le cercle médiateur d'un tore, etc...
En toute généralité, je ne sais pas comment faire.

[méphistopheles]

en fait, j'aimerais bien que francis sourd m'explicite un peu la methode de Newtown, ça m'al'air proche de ce qu'il me faut.

[FrancisSourd]

Tu peux regarder la section 4.6 ici
http://cours.ufrmd.dauphine.fr/lebou....opti.chp4.pdf

ou encore les sections 10.0 à 10.3 ici
http://www.nrbook.com/b/bookcpdf.php

Je t'ai parlé de la méthode de Newton mais n'importe quelle algorithme de minimisation unidimensionnelle peut plus ou moins faire l'affaire.

As-tu une équation simple pour décrire ta surface de révolution?

[méphistopheles]

heu j'arrive pas à voir tes liens... (le premier, firefox et adobe plante, et pour le deusième, ce sont les sous sections qui affichent un message d'erreur)

sinon, oui mon équation est simple et je connais la dérrivée. si a,b,c sont des constantes, elle est de la forme rho(Z)=[a/(2+c)]*[(b-Z²)/(b+Z²) -1 -c)] et sa dérrivée est évidement également tres simple.

[FrancisSourd]

Je reprends avec ta fonction rho(Z):

Si le centre de la sphère est (r0,theta0,z0) en coordonnées cylindrique, alors, tu vas minimiser

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

d(z) = (z-z0)² + (rho(z) - r0)²

Vu la tête de rho(z), je dirais qu'il n'y a qu'un minimum (mais je n'ai rien prouvé).

Tu vas donc chercher z* tel que d'(z*) s'annule. La dérivée d' est une fonction rationnelle (quotient de deux polynômes). Le numérateur est un polynôme de degré 5 (sauf errreur) dont les coefficients s'expriment en fonction de a,b,c,z0,r0.

Il faut donc calculer les zéros de ce polynôme. Comme c'est du 5e degré, on ne peut pas le faire à la main.

Je te renvoie à la page de wikipédia sur le sujet pour avoir un algorithme qui permet d'évaluer numériquement les zéros du polynôme. (J'ai l'impression que tu as un problème avec ton adobe reader car les liens que je t'avais donné marchent bien chez moi et c'est du pdf. Mais wikipedia redit à peu près la même chose).

Une fois que tu as le zéro z* du polynôme, le point le plus proche est (rho(z*),theta0,z*) en coordonnées cylindriques.

[méphistopheles]

en effet, il y as un terme en Zz0 qui empèche de faire un changement du genre X=Z²...

Par contre, il y as un problème qui me titille: s'il y as plusieurs valeurs minimales égales, j'aurais besoin de toutes les avoir... ce qui pose un certain nombre de problèmes...

Dans le methode de newton: la fonction sur laquelle on doit chercher un zero doit être la dérivée de la distance non ? (qui elle est de degré 4 si je ne mabuse (mais je m'abuse probablement, ça parait trop simple)(par contre si c'étais vrai ce serais super bien que la methode de ferrari soit un peut longue à mon goût)) la question est donc: ou se placer "automatiquement' pour être sur d'attraper un(des) zeros ? il faut ensuite verifier pour chacuns des zeros si oui ou non ils sont égaux (il me semble que pour ma fonction, on ne peut descendre en dessous de deux minimaux égaux)...

merci

[FrancisSourd]

en effet, il y as un terme en Zz0 qui empèche de faire un changement du genre X=Z²...

Effectivement. C'est aussi mon constat.

Dans le methode de newton: la fonction sur laquelle on doit chercher un zero doit être la dérivée de la distance non ? (qui elle est de degré 4 si je ne mabuse (mais je m'abuse probablement, ça parait trop simple)(par contre si c'étais vrai ce serais super bien que la methode de ferrari soit un peut longue à mon goût))

Oui c'est bien la dérivée (d' dans mon dernier mail). Il me semble que le numérateur est de degré 5 plutôt que 4 (ce qui ne change pas grand chose). Une fois que tu as trouvé un zéro z*, tu divises le polynôme par (z-z*) et tu cherches pareillement un nouveau zéro (et ainsi de suite jusqu'à ce que tu les as tous trouvé.

[QUOTE]
la question est donc: ou se placer "automatiquement' pour être sur d'attraper un(des) zeros ?[QUOTE]

Je pense qu'en partant de z=z0 et en appliquant l'algo de recherche de zéros, tu converge rapidement vers z*.

il faut ensuite verifier pour chacuns des zeros si oui ou non ils sont égaux (il me semble que pour ma fonction, on ne peut descendre en dessous de deux minimaux égaux)...

Oui, c'est cela.

[méphistopheles]

le problème est que la fonction ne converge que vers le zéro de la pente monotone: si j'ai plusieurs zéro, il faut que je me place ailleurs... et alors, ou donc se placer

(ce qui ne change pas grand chose)

Si! si elle est de degré 4, je peut connaître tous les zéros de la fonction sur un intervalle donné de manière formelle (par le méthode de ferarri).

[FrancisSourd]

le problème est que la fonction ne converge que vers le zéro de la pente monotone: si j'ai plusieurs zéro, il faut que je me place ailleurs... et alors, ou donc se placer.

Je ne comprends pas trop ce problème. Je t'avais parler de diviser ton polynome par Z-Z* où Z* est le premier zéro trouvé. Tu as alors un nouveau polynome de degré moindre dont tu cherches les zéros (qui sont également des zéros de ton premier polynôme).

Si cela n'est pas cela le problème, mieux vaut poser la question dans une nouvelle discussion car j'ai l'impression que cette discussion-ci n'est plus suivie par grand monde!

[méphistopheles]

en fait, je vient de comprendre... désolé

bon, vu que le nombre de zeros est limité, ça devrais aller, car le C++ n'est pas doué pour le calcul formel.