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;

[bakero]

Merci pour votre participation, mais mon veritable probleme sest au niveau du choix de la strutture de donnée pour les operations que je devrais effectué.

[souviron34]

que ce soit des points (x,y), des segments (x1,y1,x2,y2), c'est du pareil au même..

En général on prend des points... Parce que quand c'est un segment, l'enèvement d'un point provoque la modification de 2 segments (si ils sont connectés)

Cependant, dans l'énoncé de ton problème, on indique des segments, donc tu prendras des segments.. (en tableau ou en liste chaînée).

En tableau, cela implique des tris.
En liste chaînée, il faut juste vérifier les points de contact et mettre (ou non) les précédents et suivants.

Tu dois donc faire des tableaux de listes chaînées (un ensemble de lignes brsées, éventuellement à un seul segment)


Pour ce qui est du dernier problème, il faut aller voir dans le forum Algorithmes, mais il faut auparavant avoir calculé et stocké les intersections éventuelles : en passant à travers tous les segments, utiliser les fomules de maths pour déterminer si les segments s'intersectent, et si oui calculer l'intersection.. (ici ce sera un point).

[diogene]

Il y a des choses dans ton problème qui ne me sont pas claires :
-

PS: les segments confondus partielements ou totalements sont considérés comme des intersections infini.

je ne sais pas ce que signifie "intersections infinies" et ce que cela implique pour le traitement de ces cas.

-

calculer le numero de contact qui esiste entre les segments(si [AB], [CD] e [EF] sont connectés on dira que ce numero = 3)

Ce nombre doit être considéré comme la caractéristique de quel(s) élément(s) ? des 3 segments [AB], [CD] et [EF] ? Cela signifie-t-il que [AB] intersecte [CD] et [EF] ou que [AB] intersecte [CD], [CD] intersecte [EF] et [EF] intersecte [AB] (donc forme une espèce de chemin fermé) ?

- La question du parcours minimum peut être considéré ultérieurement mais on aurait avantage à en savoir plus car définir une structure des données dépend aussi de ce qu'on veut faire ensuite de ces données. Qu'entends-tu par "les intersections entre segments forment un parcours" ? A quelle(s) condition(s), ces intersections forment-elles un parcours ?

- Sinon, a priori en l'absence de précisions, j'envisagerai d'utiliser des listes chainées avec deux listes principales : une liste des segments et une liste de toutes les intersections entre segments.
1- Les cellules de la liste des segments stockeraient les coordonnées d'un segment et la tête d'une liste des intersections de ce segment avec les autres (en fait une liste de pointeurs vers des cellules de la liste de toutes les intersections entre segments)
2- les cellules de la liste de toutes les intersections entre segments stockeraient les coordonnées d'un point d'intersection et deux pointeurs vers les cellules de la liste des segments correspondant aux deux segments responsables de l'intersection.

[bakero]

A diogene:
Une intersection "infinie" ce sont deux droites paralelleles qui partagent plusieurs points en commun. Ceci n'implique pas grand chose, juste necessaire pour le calcul des segments en contact, vue que deux segments peuvent etre porter par la mème droite et n'avoir aucun point en commun.
Pour le numero de segments en contact, cela signifie que les trois segments peuvent avoir un point en commun, ou qu'il y en a un qui soit en contact avec les deux autres, ou qu'ils soient tous en contact par 3 points ou plusieurs points(cas de segments confondus).
J'avais deja opté a la strutture graphe par des listes adjacences, mais je vois pas vraimment comment effectué des eliminations de segments avec cette strutture de donnée.

[diogene]

Tout cela n'apporte pas de réponses aux questions que je posais.
1-

Une intersection "infinie" ce sont deux droites paralelleles qui partagent plusieurs points en commun. Ceci n'implique pas grand chose, juste necessaire pour le calcul des segments en contact, vue que deux segments peuvent etre porter par la mème droite et n'avoir aucun point en commun.

Il y a alors potentiellement une infinité de points d'intersections. Il faut quand même savoir comment traiter cette situation et cela dépend de l'exploitation que l'on veut faire ultérieurement de cette base de données de segments. Or tu n'as pas explicité ce point de façon claire.

Je vois a priori 2 possibilités qui dépendent du traitement des données à réaliser sur ces segments

a- Il faut considérer qu'on peut avoir un point d'intersection ou une infinité.

Si les deux segments [AB] et [CD], sont portés par la même droite et se chevauchent, on peut coder cette situation par deux points "d'intersections". Symboliquement, (en décalant d'une ligne les deux segments pour la clarté)

       C-----D          
  A---------------B    2 "intersections" entre [AB] et [CD] : C et D

          C-------------D
  A---------------B    2 "intersections" entre [AB] et [CD] : C et B

On pourrait avoir alors 1 ou 2 points d'intersections selon les segments (mais cela ne dit pas ce qu'il faut faire par la suite de cette information).

b- On peut fusionner des segments :

       C-----D
 A---------------B        équivalent  A----------B

          C----------D
 A---------------B        équivalent  A----------D

Dans ce cas, on aura toujours au final 1 seul point d'intersection entre segments effectifs (mais ceci va altérer la manière de coder les segments puisqu'il y a possibilité de suppression d'un segment : dans l'exemple, il faut retrouver [AB] si on supprime [CD] et [CD] si on supprime [AB]).

2-

Pour le numero de segments en contact, cela signifie que les trois segments peuvent avoir un point en commun, ou qu'il y en a un qui soit en contact avec les deux autres, ou qu'ils soient tous en contact par 3 points ou plusieurs points(cas de segments confondus).

Est-ce que cela signifie que c'est une caractéristique de chaque segment indiquant le nombre de segments avec lesquels il a au moins 1 point d'intersection ?

3-

J'avais deja opté a la strutture graphe par des listes adjacences, mais je vois pas vraimment comment effectué des eliminations de segments avec cette strutture de donnée.

Il y a deux choses : (1) représenter l'ensemble des segments et pouvoir manipuler cette collection (ajouter, enlever des segments à la collection) puis (2) exploiter cet ensemble de données en déduisant éventuellement de cette collection une autre représentation des données plus adéquate au traitement à faire. Les deux représentations ne sont pas forcément identiques car les traitements à réaliser sont différents.

4- Tu n'as pas non plus répondu à la dernière question posée

[bakero]

1-En effet il esiste une infinité de points d'intersection, mais aucun segment ne disparait ou n'est absorbé. Meme si un segment appartient entirement a un autre on dira qu'ils sont en connection et la suppression de l'un n'affecte en aucun cas l'autre. Pour ce que on devrait en faire pour ce type d'intersection, il serait necessaire je pense au calcul du chemin minim et aussi lors du comptage des segments en connection.

2-Non il ne s'agit pas d'une caracteristique de chaque segment, mais de tout les segments. En fait a chaque point d'intersection entre deux ou plusieur segments, on verifie si il esiste un segment parmi ki n'a pas encore été compté et on incremente le compteur. Deux segments confondus forment une intersection donc on incremente.
Sur la piece jointe on a trois segments qui sont en contact par un point donc n = 3.


3-Pour le parcour minimum, je m'escuse j'ai mal formulé ma question plus haut. Il s'agit du parcour minim entre deux extremité de deux segments differents. Sur la fig 2 de la piece jointe on aura:

parcour minim (A,B) = A-A', B-B', C-C': lenght = 3
parcour minim(A,F) = null:lenght = 0
si les segments sont confondus: lenght = 1

c'est vrai que j'ai pas été tres clair dans les debuts et je m'en escuse, mais j'ai vraiment besoin d'un coup d main pour resourdre ce projet, suis pas tres doué en programmation

[diogene]

Si je comprend,
- sur le point 2 :
ce compteur est donc une caractéristique d'une intersection et indique le nombre de segments en intersection en ce point.
- sur le point 3 :
d'après la méthode de calcul de la distance, seule compte l'existence d'une intersection entre segments mais la position de cette intersection sur les segments n'intervient pas.

[bakero]

Oui exactement, tout les points d'intersections devront etre analisés et triés ceux qui n'auront pas encore été comptés.
Egalement vrai pour le point 3, la position sur le segment ne compte pas, mais il faudrait considerer le minimum d'intersection possible pour arriver a l'autre segment, vu qu'il pourait y en avoir d'autres chemins qui y mene.

[diogene]

Sur le point 2 :
Sur le moment, je ne vois pas l'intérêt de ce compteur pour la suite du problème. Comme on se moque de la position d'une intersection sur un segment, il est sans importance de savoir que deux intersections d'un segment avec deux autres segments soient confondues en un seul point ou soient deux points différents.

[bakero]

En fait c'est l'implementation de ce cas de figure qui cause probleme, je vois pas comment ce serait possible

[diogene]

Il faut bien que l'on comprenne le but du programme avant de pouvoir fournir des conseils pertinents. Alors, essaye d'être clair, sinon on perd du temps.

En fait c'est l'implementation de ce cas de figure qui cause probleme, je vois pas comment ce serait possible

Je ne comprend pas du tout cette réponse ni le rapport avec ma remarque.
En clair, à quoi doit servir ce fameux compteur ?

[bakero]

Desolé, je parlais de l'implementation de l'intersection segments et precisement dans le cas de deux segments pararelles portés par la meme droite et n'eyant pas de point en commun. J'ai vu des implementations pour des lignes de droites, mais encore rien pour les segments qui fonctionnent bien.
Pour le compteur, il devra etre restituer en output c'est tout, le pragramme prendra en entrée une liste de segment et rendra en output ce compteur. Donc il ne servira surement pas pour la suite du programme.

[diogene]

Décidément, cette histoire de compteur n'est pas claire du tout. Apparemment, ce n'est pas ton idée personnelle que de mettre ce compteur, mais quelque chose qu'on te demande de faire. Et visiblement, tu n'as pas bien compris ce que c'était sinon tu pourrais l'expliquer. Précédemment tu étais d'accord pour dire que c'était une propriété d'une intersection et maintenant c'est une propriété d'un ensemble de segments. Ce n'est pas la même chose. En plus, tu dis qu'il ne sert à rien, mais pourquoi le demander alors que sa présence peut modifier la structure des données à utiliser.

Je te conseille avant d'aller plus loin de te renseigner auprès de ceux qui te demandent cette réalisation pour bien comprendre ce qu'il y a à faire avant de commencer. C'est indispensable, car si le problème est mal posé, on va vers le mur.

[bakero]

J'ai parfaitement compris le probleme et peut etre que je m'esplique mal.
On demande le nombre de segments qui sont en intersection dans l'ensemble des segments, donc ne sera pas compté un segment qui n'est en conctact avec aucun autre segment.
dans la fig 2: on voit bien que tout les segments ont un ou plusieurs intersections a part [FF'] qui est isolé, dont n = 5 ([AA'],[BB'],[CC'],[DD'],[EE'] )dans ce cas ci. Je pense que chaque segment aura comme proprietée le nombre ou la liste de segment avec lequel il est en conctact.
Si on pouvait deja m'aidé a implementer l'intersection entre deux segments, j'en serais vraiment ravi . int existe_intersection(segment s1, segment s2){}
merci