Discussion :

[chadliii]

Bonjour,
J'ai un segment (je connais les coordnnées de ses 2 points limites) et un cercle (je connais son rayon et les coordonnées de son centre). Mathématiquement, je peux avoir le spoints d'intersection (s'ils existent) mais j'ai pas trouvé comment transformer la méthode mathématique en algorithme.
Merci d'avance pour votre aide

[Ivory69]

Salut,
Mathématiquement c'est koi tes tests ?

[chadliii]

l'equation d'un droie est sous la frome y=ax+b.
on connait 2 points qui vérifient cette équation donc on peut trouver a et b. Juste faut faire attention aux intervalles puisque c'est un segment.
L'equation d'un cercle est: (x-xc)²+(y-yc)²=R² avec R:Rayon et le centre (xc,yc).
Pour trouver l'intersection, il suffit de substituer y dans la 2eme equation.
Vous avez une idée comment faire ça algorithmiquement?
Merci

[Kangourou]

salut,

une solution est de raisonner geometriquement.
- soient D la droite supportant le segment, et C le cercle
- construire P, la perpendiculaire à D passant par le centre de C
- calculer les coordonnees de I, le point d'intersection de P avec D. Ce point est situe entre les deux intersections de la droite avec le cercle, si elles existent.
- calculer la distance du point I au centre du cercle. Si la distance est duperieure au rayon, pas d'intersection. Sinon, par Pythagore, on deduit la distance 'r' entre I et chaque point d'intersection.
- les coordonnees des points d'intersection sont obtenues en ajoutant au point I un vecteur de norme 'r' et d'angle +/- l'angle de la droite

Pour les calculs sur droite, je te conseille la representation parametrique:
x(t) = x0 + t*dx
y(t) = y0 + t*dy
Ca te permet d'avoir la 'position' d'un point sur une droite. Si pour un segment, tu prends x0 et y0 egaux aux coordonnees du premier point, et dx et dy egaux a la difference des coordonnees des extremites, les points du segment correspondent a 0 <= t <= 1.

A+

[Ivory69]

Ben en fait tu te ramène à une équation du second degré en x donc t'as juste un test à faire sur le signe de delta.
L'équation si je me suis pas trompé est:

(1+a)x² + 2(a(b-yc)-xc)x + (xc² + (b-yc)²-R²) = 0

tu poses
A=(1+a)
B=2(a(b-yc)-xc)
C=(xc² + (b-yc)²-R²)

tu calcules ton delta et tu conclue
si négatif pas d'intersection
si positif deux intersection
si nul un point d'intersection

[Ivory69]

NB: fodrai vérifier si ça marche sur des exemples mais je pense que ça doit pas être très loin de ça

[pseudocode]

+1 avec Kangourou.

Equation parametrique de la droite:
x = x0 + t*dx avec dx=x1-x0
y = y0 + t*dy avec dy=y1-y0

Equation du cercle:
(x-xc)^2 + (y-yc)^2 = R^2

substitution:
(t*dx+Ox)^2 + (t*dy+Oy)^2 = R^2 avec Ox=x0-xc et Oy=y0-yc

ce qui nous donne l'équation du second degré:

A*t^2 + B*t + C = 0

avec
A=dx^2+dy^2
B=2*(dx.Ox+dy.Iy)
C=-Ox^2-Oy^2-R^2

On résoud, et on garde les valeurs de t entre 0 et 1

[chadliii]

Bonjour,
Merci pour vos réponses.
D'abord j'ai pas compris comment vous arrivez à trouver l'équation paramétrique du segment:
x = x0 + t*dx avec dx=x1-x0
y = y0 + t*dy avec dy=y1-y0
où 0 <= t <= 1
??

Pour la substitution dans l'équation du cercle, c'est bon sauf que je trouve
C= Ox^2+Oy^2-R^2 et pas C=-Ox^2-Oy^2-R^2 (comme pseudocode).
Pour B=2*(dx.Ox+dy.Oy) (il y avait une faute de frappe de pseudocode)
a+

[pseudocode]

Pour la substitution dans l'équation du cercle, c'est bon sauf que je trouve
C= Ox^2+Oy^2-R^2 et pas C=-Ox^2-Oy^2-R^2 (comme pseudocode).
Pour B=2*(dx.Ox+dy.Oy) (il y avait une faute de frappe de pseudocode)
a+

Oui tu raison sur les 2 remarques. Je devrais pas taper d'algo quand j'ai la grippe .

Bonjour,
Merci pour vos réponses.
D'abord j'ai pas compris comment vous arrivez à trouver l'équation paramétrique du segment:
x = x0 + t*dx avec dx=x1-x0
y = y0 + t*dy avec dy=y1-y0

En fait, tu te déplaces sur la droite portant le segment.
- Lorsque t=0, tu es en position (x0,y0), c-a-d la 1ere extremite du segment
- Lorsque t=1, tu es en position (x1,y1), c-a-d la 2nde extremite du segment
- Entre les 2 tu te déplaces linéairement, donc tu es sur la droite qui passe par les 2 extremités.

Il faut juste que tu te limites au valeur de t entre 0 et 1, sinon tu te retrouves sur la droite mais avant ou apres les extermités.

[chadliii]

Merci pseudocode.
Merci aussi à Ivory69 et Kangourou.

[defluc]

Bonjour,

Je réactive un sujet ancien parce que je ne comprends pas la syntaxe

Code :

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

B=2*(dx.Ox+dy.Oy)

et plus particulièrement le point («.») qui y figure.

[Zavonen]

Je traiterais le problème analytiquement dans un repère centré sur le centre du cercle et pour lequel le second vecteur de base est orthogonal à la droite.
Dans ce cas le cercle est: x^2+y^2=R^2
la droite y=k
Donc selon les valeurs de k 0 1 ou 2 points d'intersection.
Quand il y a intersection (2 points éventuellement confondus) le problème est ramené à l'intersection de deux segments sur une même droite horizontale. Il n'y a donc plus qu'une comparaison d'abscisses à faire.

[JediMaster]

Bonjour,
Je redéterre ce topic parce que la solution de Zavonen me parait très bonne mais je n'arrive pas a la la traduire de manière algorithmique.
Je comprends bien que dans x²+y²=R² (x,y) est l'ensemble des points de constituant le cercle C
Que la droite d : y = k parce que y = ax + k mais x = 0 puisque on travail dans le repère rouge sur le dessin.
Mais après je suis bloqué je ne trouve pas comment faire mon équation qui doit être, je pense, du second degré puisque je peux avoir deux solutions.

Mon problème est aussi que je travaille dans le repère vert pour les coordonnées

Quelqu'un pourrais m'aidez svp ?

[Invité]

Bonjour,
Je crois qu'il faut distinguer 2 problèmes différents.
1 le calcul lui-même des intersections. A ce stade la difficulté qui me parait principale est la précision du résultat.
2- la condition d'intersection.
J'ai une fonction qui fait cela, en C, mais elle fait tout de même 170 lignes.
Mais pas de problème pour vous la donner.
Je l'ai écrite il y a une bonne dizaine d'années, mais je pense que je pourrai répondre à toutes les questions.

[JediMaster]

Merci pour votre réponse. En fait ce qui m’intéresse n'est pas les coordonées des intersections mais seulement si il y a intersection ou pas.
On m'a aidé a trouver la solution et je la poste ici si sa peux aider
le seul problème étant en fait de trouver le la distance entre le centre du cercle et la droite d.
représenter sur le dessin par le segment partant du centre au point k

donc avec d : y = ax+ b
et K(xk,yk)
on obtient :

distance = ( |axk - yk + b| ) / racine²(1+a²)

après on test la distance avec le rayon
si distance < rayon alors il y a une intersection

[BBric]

Un petit déterrage, pour ajouter mon grain de sel. ^^
La technique qui a fonctionnée pour moi est celle d'Ivory69 au début, on substitue ax+b à y dans (x-xc)²+(y-yc)²=R², ce qui donne (1+a²)x² + (-2*xc + 2*a*(b-yc))*x + xc² + (b-yc)² - R² = 0, après il reste à calculer le discriminant et à conclure. La petite subtilité est pour les droites horizontales et verticales (et accessoirement les points confondus) qui demandent un traitement différent, dans tous les cas il faut également filtrer les résultats extérieurs au segment.