Colinéarité dans marche de Jarvis (ConvexHull)

[_-Slash-_]

Bonjour,

J'étudie, pour mon plaisir, différents algorithmes géométriques. Je viens d'implémenter en C la marche de Jarvis pour le calcul de l'enveloppe convexe et je me pose une question sur mon algorithme.

Pour rappel, voici le pseudo-code (source Wikipedia).

Code :

1
2
3
4
5
6
7
8
9
10
11
12
    jarvis(S)
    pointOnHull = leftmost point in S
    i = 0
    repeat
      P[i] = pointOnHull
      endpoint = S[0]         // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
    until endpoint == P[0]      // wrapped around to first hull point

Pour lapartie suivante :

Code :

(S[j] is on left of line from P[i] to endpoint)

j'utilise une fonction qui permet de retourner le sens de deux droites passant par un même point (Code C):

Code C :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
/* comparaison du sens de p0pCherche par rapport à p0p1 */
static int cherche_Sens_Ligne(Points p0, Points p1, Points pCherche)
{
    int sens =(     (pCherche.x - p0.x)*(p1.y - p0.y) -
                    (pCherche.y - p0.y)*(p1.x - p0.x) );
 
    if(sens > 0)
        return 1;
    else if(sens < 0)
        return -1;
    else
        return 0;
 
}

Si le retour est à -1 il n'y a pas de problème on écarte le point.
Si le retour est 1 alors on le prend en compte.
Par contre dans le pseudocode on ne parle pas du cas où le sens est 0 ; c'est-à-dire que les points sont collinéaires.

Dans un tel cas, je pense faire une comparaison entre les droites formées par les points et prendre le point le plus éloigné du point actuel. L'enveloppe doit au final être la même mais avec un nombre de points moins important.
Qu'en pensez-vous ?

Merci

[jerome_pdv2]

Bonjour,

pour éliminer les points "colinéaires" je procéderais de la sorte :

1 - déterminer tous les points de l'enveloppe (>=0) donc 0 y compris

2 - prendre un point O à l'intérieur de l'enveloppe, et un point sur l'enveloppe déterminant un vecteur u.

Pour tous les autres points M de l'enveloppe déterminer l'angle en u et le vecteur OM.

Réordonner tous les points par angle croissant par exemple
("réordonner" dans le bon sens les points en cas d'exaequo angulaire)

Tu prends un de tes points ordonnés, et ses deux successeurs, tu calcule les angles entre les vecteurs définis depuis le centre (deuxième point) et les deux extremités, si tu trouve 180 alors tu supprime le deuxième point, et tu recommence en partant du premier point, si l'angle est différent le deuxième point devient le premier point etc...

Jusqu'à avoir fait le tour de ton enveloppe convexe.