Fonction d'intersection segment de droite et cercle

Version imprimable

22/06/2008, 00h23
mr-ti

Fonction d'intersection segment de droite et cercle

Bonjour,

J'ai pas mal cherche mais je ne trouve pas...

Je dispose de du centre et du rayon du cercle, des points a et b du segment.
Mon problème est de trouver un code (en c) le plus efficace pour savoir si il y a une intersection entre le cercle et le segment.
Cette fonction doit retourner vrai si il y a intersection ou si le segment est dans le cercle.

Voilà, merci d'avance...
22/06/2008, 07h32
unmanos

Le probleme c'est plutot de connaitre la distance minimale entre un point (le centre de ton cercle) et une droite. Si celle ci est inferieur au rayon du cercle, alors il y a intersection.

http://mathworld.wolfram.com/Point-L...mensional.html

http://local.wasp.uwa.edu.au/~pbourk...try/pointline/

Voilà ce que j'ai trouvé comme solution donc si quelqu'un trouve un moyen d'optimiser ce code, je suis preneur.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
typedef double real_t;
typedef struct point_t{
    real_t x,y;
}point_t;
typedef unsigned char bool_t;
 
bool_t intersect_segment_cercle(point_t *pt1, point_t *pt2, point_t *center, real_t ray){
    real_t x,y;
 
    // Le point pt1 appartient-il au cercle ?
    x = pt1->x - center->x;
    y = pt1->y - center->y;
    if(sqrt(y*y+(-x)*(-x)) <= ray)
        return 1;
 
    // Le point pt2 appartient-il au cercle ?
    x = pt2->x - center->x;
    y = pt2->y - center->y;
    if(sqrt(y*y+(-x)*(-x)) <= ray)
        return 1;
 
    // Calcul de la distance minimum entre le centre du cercle et la droite
    x = pt2->x - pt1->x;
    y = pt2->y - pt1->y;
    real_t d = fabs(y*center->x + (-x)*center->y + (x * pt1->y - y * pt1->x)) / sqrt(y*y+(-x)*(-x));
 
    // Y a-t-il intersection entre le cercle et la droite passant par les points pt1 et pt2 ?
    // Si oui, on teste si les abscisse points pt1 pt2 sont de chaque côté de l'abscisse du centre 
    // ou si les ordonnées points pt1 pt2 sont de chaque côté de l'ordonnée du centre
    if(d <= ray 
       && ((pt1->x < center->x && center->x < pt2->x)
            || (pt1->y < center->y && center->y < pt2->y)
            || (pt1->x > center->x && center->x > pt2->x)
            || (pt1->y > center->y && center->y > pt2->y)))
        return 1;
    else
        return 0;
}

22/06/2008, 16h06
souviron34

voir forum Algorithmes -> Maths