Discussion :

[bakero]

salut!
je dois faire un projet en c sur l'implementation des segments de droites.
Pratiquement mon programme devrait:
- Creer un segment prenant ces coordonnées entier en entrer(x1,y1,x2,y2)
- Controllé s' il esiste une intersection avec les autres segments deja presents.
PS: les segments confondus partielements ou totalements sont considérés comme des intersections infini.
-supprimer un segment
-visualiser les segments
-calculer le numero de contact qui esiste entre les segments(si [AB], [CD] e [EF] sont connectés on dira que ce numero = 3)

-determiner le parcour minime(c'est a dire que les intersections entre les segments forment un parcour, et il faudrait calculer le parcour minimum)

Je pensais a une implementation des grafes par les listes adjacences, mais j'ai lu quelque part que la suppression est impossible avec cette methode et je sais plus quelle structure utiliser. Help please!

[souviron34]

une liste chaînée..

[bakero]

et pour les coder les intersections comment je le fais avec les listes?

[souviron34]

calculer des intersections de segments c'est des maths..

cela n'a rien à voir avec la manière dont on stocke ou gère les points ou les segments en programmation..

[brachior]

calculer des intersections de segments c'est des maths..

cela n'a rien à voir avec la manière dont on stocke ou gère les points ou les segments en programmation...

Oui et non,
La manière de stocker des éléments peut jouer sur les maths très fortement,
Il y a des structures plus ou moins adaptées aux traitements des données.

Sinon pour ton problème,
J'hésite entre deux structures,
Une liste chainée est pratique pour la quasi totalité de tes traitements
(suppression, calcul d'intersection, ...)
Mais ton dernier traitement,
Je ne sais pas vraiment comment tu dois le faire,
Si tu dois parcourir les intersections comme étant un chemin eulérien ou autre, ...
Donc là c'est possible qu'un graphe soit plus pratique.

Après, étant en C,
Il y a toujours moyen de simuler des graphes avec des listes ou des tableaux.

[olivieram]

Bonsoir,
une idée comme ça. Voici un petit exemple:

Code :

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
#include <stdio.h>
#include <stdlib.h>
/*
 * L'idee est de pouvoir calculer les intersections
 * de la facon la plus simple possible
 * je pense a une matrice
 * L'intersection existe lorsque 4 extremites forment un rectangle
 * Il y a un rectangle de differentes orientations
 * Le plus rapide c'est le calcul de la matrice
 * et sa representation
 * La matrice pour 1 segment:
 *    x1 x2 
 *  y1
 *  y2
 *  La matrice pour 2 segments:
 *     x11 x12 x21 x22
 *  y11 x  
 *  y12     x
 *  y21        x
 *  y22            x
 *  Si on trie les x et les y
 *
 *     x11 x21 x12 x22
 *  y22             x  
 *  y12        x
 *  y21     x
 *  y11 x
 *  Une fois tries l'ordre determine s'il y a intersection ou non
 *  Le chemin le plus court est obtenu en suivant les croix
 */
 
typedef struct _point {
	int x;
	int y;
} point;
 
typedef struct _segment {
	point extremite[2];
} segment;
 
typedef struct _sgmList {
	segment *ptr;
	int nbElements;
	int count;
} sgmList;
 
typedef struct _groupX {
	int x;
	segment *s; /* segment relatif */
} groupX;
 
typedef struct _groupY {
	int y;
	segment *s; /* segment relatif */
} groupY;
 
typedef struct _matHorizX {
	groupX gx[]; /* tableau des x */
	int count;
	int nbElements;
} matriceHorizontale;
 
typedef struct _matVertY {
	groupY gy[];
	int count;
	int nbElements;
} matriceVerticale;
 
typedef struct _matrice {
	matriceHorizontale h;
	matriceVerticale v;
	int* checked[];
} matrice;
 
typedef struct _archi {
	matrice mat;
} archi;