Discussion :

[alexis0788]

Bonjour, dans le cadre d'un projet informatique de programmation en C nous devons afficher dans une console la convexité d'un polygone.
Pour cela il est d'abord nécessaire de determiner si le polygone est croisé ou non...
Pour cela nous avons écris une fonction qui permet de determiner si deux cotés se coupent (cette fonction prend en paramètre 4 points).

Code :

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

1
2
 
point *intersection(point *un,point *deux,point *trois,point *quatre);

Nous avons défini un type point comme cela:

Code :

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

1
2
3
4
5
6
 
typedef struct POINT {char *nom;
                      float abscisse;
                      float ordonnee;
                      struct POINT *pred;
                      struct POINT *succ;} point;

Voici le prototype de la fonction que nous comptons ecrire:

Code :

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

1
2
 
bool croise(point *p)

Nous avons donc un problème pour parcourir la liste de point de telle manière à pouvoir déterminer une eventuelle intersection entre tous les côtés probables...
ps:nous n'avons pas besoin de récupérer les coordonnées de l'intersection mais juste de retourner un booléen.

D'avance nous vous remercions pour vos commentaires.

[souviron34]

Va voir du côté du forum Algorithmes..

Question déjà posée...

Pleins de méthodes existent,mais c'est des maths, pas du C en tant que tel...

Autre chose : je ne comprend pas très bien..

• Si c'est déterminer l'enveloppe convexe , un algo du type Marche de Graham marche très bien.
• Si c'est déterminer si le polygone est croisé, cela n'a pas grand chose à voir avec la convexité, et là l'algo est simple : prendre un segment, vérifier qu'il ne coupe pas les autres.. Itérer..

[barbsbou]

C'est peut-etre mon incapacite a reflechir mais je ne comprends pas trop ton probleme

grace a ta structure point tu peux par courir tous les points de ton polygones, donc tous les cotes.
et avec

Code :

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

1
2
3
4
5
6
7
8
9
 
initial = /*je choisi un point de depart*/
for() /*je parcours tous les points de mon polygone*/
{
    for()/*je parcours tous les points a partir d'ou je suis jusqu'a mon point initial*/
    {
      /*et la je test si mes deux segments sont croise grace a ta fonction*/
     }
}

ca doit marcher...non??

[ToTo13]

Bonjour,

C'est peut-etre mon incapacite a reflechir mais je ne comprends pas trop ton probleme

je pense que ce qu'il appelle point du polygone, sont en fait les sommets. Est ce bien cela ?

- Si tu travailles dans un espace discret, une solution simple est de faire tracer les points à l'aide d'un Bresenham, puis de regarder s'il y a intersection (deux segments qui passent au même endroit).
- Sinon, tu peux prends deux cotés C1 et C2, tu calcules les équations des droites passant par les cotés, puis l'intersection de ces deux droites. Si le point est dans le segments des cotés, c'est que les cotés se coupent.

[alexis0788]

Bonjour et merci de vos réponses j'ai du m'absenter pour un voyage à l'étranger... en fait ce que j'appelle polygone c'est une liste de sommet définies.
Je manipule donc une liste de points(de sommets).
J'ai réalisé une fonction qui prend en arguments 4 points(ou sommets) et qui determine s'il y a intersection entre deux droites.
J'ai procédé comme cela:

Code :

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

1
2
 
point *intersection(point *un,point *deux,point *trois,point *quatre)

Cette fonction determine s'il y a intersection entre la droite formée par les point 'un' et 'deux' et la droite formée par les points 'trois' et quatre'.
S'il il n'y a pas intersection je renvoie NULL sinon je renvoie le point d'intersection.

Mon PROBLEME est maintenant de savoir comment déterminer si cette intersection est bien comprise à l'intérieur du polygone.
Car pour l'instant il y a forcément intersection...

Merci

[Zavonen]

L'enveloppe convexe est l'ensemble des barycentres des sommets affectés de coefficients tous de même signe. Il suffit donc, ayant le point d'intersection, de calculer ses coordonnées barycentriques. C'est ni plus ni moins la résolution d'un système linéaire.

[pseudocode]

J'ai réalisé une fonction qui prend en arguments 4 points(ou sommets) et qui determine s'il y a intersection entre deux droites.

Tu peux directement calculer l'intersection de 2 SEGMENTS au lieu de l'intersection des 2 droites de support:

Soit 2 segments [AB] et [CD].

Si ils ont un point d'intersection "I", alors on a:

I = A + r*(B-A) = C + s*(D-C)

avec 0 < r,s < 1

En 2D, les coordonnées de I sont:
I.x = A.x + r*(B.x-A.x) = C.x + s*(D.x-C.x)
I.y = A.y + r*(B.y-A.y) = C.y + s*(D.y-C.y)

Ce qui nous permet de résoudre r et s :
r = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y) / (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x)
s = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y) / (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x)

Donc pour savoir si [AB] et [CD] une intersection, il faut regarder si 0 < r,s < 1.

Code java :

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

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
 
/** 
 * test if two segments [AB] and [CD] intersect.
 * 
 * @param A,B first segment
 * @param C,D second segment
 * @return true if the 2 segments intersect.
 */
private boolean intersectionSegmentSegment(Point A, Point B, Point C, Point D) {
 
	int r_num = (A.y-C.y)*(D.x-C.x)-(A.x-C.x)*(D.y-C.y);
	int r_den = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);
 
	if (r_den==0) return false;     // no intersection 
	double r = (double)r_num/r_den;
	if (r<=0 || r>=1) return false; // intersection outside segment [AB]
 
	int s_num = (A.y-C.y)*(B.x-A.x)-(A.x-C.x)*(B.y-A.y);
	int s_den = (B.x-A.x)*(D.y-C.y)-(B.y-A.y)*(D.x-C.x);
 
	if (s_den==0) return false;     // no intersection 
	double s = (double)s_num/s_den;
	if (s<=0 || s>=1) return false; // intersection outside segment [CD]
 
	return true;
}

[alexis0788]

Merci beaucoup pour le code en java mais il y a certains point que je ne comprends pas:
que signifie 0<r,s<1?
Et que sont les variables r_num, r_den, s_num et s_den?
Merci.