[Mathématiques] Intersection d'un segment et d'un cercle

[Myrina]

Mes souvenirs en mathématiques sont relativement vieux et j'aurai besoin d'aide pour savoir comment déterminer si un segment [AB] coupe un cercle d'origine O et de rayon r dans le plan (donc en 2D, pas 3D).

Dans la pratique, il s'agit de détecter, parmi les flottes partant d'un point A pour aller à un point B, celles qui seraient, à un moment ou un autre, à portée d'un radar situé au point O.

Si le point A ou le point B est dans le cercle (OA<r ou OB<r), la flotte est forcément détectée; mais dans le cas ou aucun des deux n'est dans le cercle, il est quand même possible que des points du segment soient dans le cercle.

La cerise sur le gâteau serait de pouvoir récupérer les flottes détectées par une seule requête SQL: les points A et B de chaque flotte sont stockés en base de données.

[Maks]

Théoriquement c'est lorsqu'un point du segment [AB] est un point du disque de centre O et de rayon R. Car si tu parles d'un système de radar, c'est plus un disque non ?

Tu pourrais prendre en compte en plus de A et B, le point M au milieu du segment ? Ce qui recouvrirait peut être tous les cas ? (à voir)

[Shidame]

Ce topic pourra peut être t'aider :

http://www.developpez.net/forums/d274664...nt-cercle/

[Enyrian]

Hey!

Je te propose mon idée qui est je pense pas très compliquée, ni en calculs, ni à mettre en place:

1) Considérer ton segment comme un morceau de droite:

Il faut récupérer son équation de la forme ax+by+c=0, on va plutôt utiliser y=ax+b.
Si xA <> xB, a=(yA-yB)/(xA-xB) et b = yA-a*xA
Si xA=xB, l'équation est x=xA=xB

(où A(xA,yA) et B(xB,yB) sont les points du segment)

2) Récupérer les radars qui coupent cette droite:

Là une "astuce": il s'agit simplement des cercles dont le centre est à une distance à la droite AB inférieure inférieure à son propre rayon...
On calcule la distance d pour tous tes radars, de centre O(xO,yO) et de rayon R:
si xA<>xB, d=abs(yO-a*xO-b)/sqrt(1+a²)
si xA=xB, d= abs(xO-xA)

Puis tu gardes ceux qui vérifient d<=R

3) Vérifier que ces radars coupent dans la partie [AB] de la droite:

Edit: cette partie est fausse, voir plus bas

Ne garde que les radars qui entrent en collision avec le disque de diamètre AB. Pour cela tu calcules le rayon (un seul calcul):

rAB = sqrt((xB-xA)²+(yB-yA)²)/2

De centre W=((xA+xB)/2 , (yA+yB)/2) qui je note après W(xW,yW)

Pour chaque radar de centre O(xO,yO) de rayon R, la condition s'écrit:

WO <= rAB + R

i.e. sqrt((xW-xO)²+(yW-yO)²) <= rAB + R


Je sais pas si c'est clair, mais ça m'a l'air correct x)

[Ter Rowan]

erf je ne sais plus imaginer ces solutions, ça me désole

mais la démarche de Enyrian me parait pas mal

[Myrina]

Merci pour les réponses, voici ce que j'en conclus:
Pour avoir un système simple à mettre en oeuvre, je vois qu'il faut que je fasse le 1) lors de l'établissement du déplacement pour stocker 3 informations supplémentaires (a, b et si la droite est horizontale)
Ainsi le 2) ne semble pas trop complexe à faire en SQL.
Le 3) (que je n'ai pas trop compris pour l'instant) sera fait en programmation pour affiner le résultat de chacune des occurrences renvoyées par le SELECT.

---

erf je ne sais plus imaginer ces solutions, ça me désole

moi aussi iffle:
faut juste que l'on accepte que l'on vieillit un peu plus chaque jour.

[Enyrian]

Pas étonnant, la clause 3) marche pas tout le temps... =P
Le raisonnement est pas bon, je vais y méditer!

---

Bon, j'ai trouvé quelque chose qui évite de passer par les formules d'équations de cercles.

3) Vérification:

Soit P le projeté de O centre du radar sur la droite (AB).
Soit E et E' les points-intersection droite-radar.



On a : WP² = WO² - d² et PE² = R² - d²

La condition devient: WP - rAB - PE <= 0.

Ca me semble OK.

J'ai pas précisé, mais on obtient WP² avec:

WP²= (xO-xW)² + (yO-yW)² - d² puis sqrt

[Myrina]

Voilà, j'ai appliqué sans souci les points 1) et 2)

par contre, j'ai eu du souci pour comprendre et mettre en oeuvre le 3) proposé.
Mais par une autre approche, j'ai réussi à m'en sortir:
- si le point A ou le point B est dans le disque alors le segment est forcement présent dans le radar
- sinon, si la projection P du centre O du radar est dans le segment [AB] donc les points A et B se sont part et d'autre du cercle donc une partie du segment [AB] est présent dans le radar.

$longueurAB=sqrt(($Bx-$Ax)*($Bx-$Ax)+($By-$Ay)*($By-$Ay));

$distOAB=(($Ox-$Ax)*($Bx-$Ax)+($Oy-$Ay)*($By-$Ay))/($longueurAB*$longueurAB);

				

$longueurOA=sqrt(($Ox-$Ax)*($Ox-$Ax)+($Oy-$Ay)*($Oy-$Ay));

$longueurOB=sqrt(($Ox-$Bx)*($Ox-$Bx)+($Oy-$By)*($Oy-$By));



if ($longueurOA<=$r||$longueurOB<=$r||($distOAB<=1&&$distOAB>=0)) {

	$color='red';

} else {

	$color='orange';

}

http://myrina.free-h.net/testradar.svg

Donc, en rouge, les flottes visibles par le radar. Les autres ne sont pas visibles; celles en orange sont celles dont la droite coupe le cercle du radar.

Merci pour l'aide

[keke]

1° >>> si le point A ou le point B est dans le disque alors le segment est forcement présent dans le radar
2° >>> sinon, si la projection P du centre O du radar est dans le segment [AB] donc les points A et B se sont part et d'autre du cercle donc une partie du segment [AB] est présent dans le radar

2° n'est pas suffisant.
Il faut <b>aussi</b> que la longueur du segment [PO] soit inférieur à R. Et dans ce cas, le point 1° est inutile.

Pour s'en convaincre.
Un segment A(0,0) et B (2,0)
Un cercle de centre O(1,8) de rayon 5
La projection P se trouve en (1,0), dans le segment [AB]
mais dans ce cas, la distance [PO] fait 8 ce qui est supérieur au rayon de 5.

kéké

[Myrina]

Sauf que dans ce cas là, je ne vérifie pas la condition du 2) énoncé par Enyrian:

PO<=r