Discussion :

[Worm00]

Bon je vais tacher d' être le plus clair possible, voila ma situation :
- J'ai des point (je connais les coordonnées) avec chacun un numéro
- Des lignes (je connais les deux point qui la compose) avec chacune un numéro

Et moi je dois retrouver les différentes faces (une face est définie par les lignes qui la compsent) qui composent ma forme (un exemple sera bienvenu je pense)


X : Numéro de ligne
X : Numéro de point


Donc ici mes face sont (6,5,7,9,3,13,11,12) et (10,11,13,8) et enfin (8,3,4,2,1)

PS : Je dois le faire en python mais c'est surtout la démarche algorithmique qui me pose probleme ici... Alors si vous vous ennuyez : "A vos cerveau !!! Aidez moi s'il vous plait !"

[Davidbrcz]

Ca ressemble beaucoup aux solutions apportées dans ce sujet:
http://www.developpez.net/forums/d57...ion-polygones/

[pseudocode]

Tu peux aussi énumérer tous les circuits du graphe, et conserver ceux qui n'ont pas de segments à l'intérieur.

C'est plus long que l'union-find mais tu n'a pas besoin de passer par une représentation "bitmap" de ton dessin.

[Worm00]

Tu peux aussi énumérer tous les circuits du graphe, et conserver ceux qui n'ont pas de segments à l'intérieur.

C'est exactement mon objectif mais comment y parvenir c'est ça mon soucis... Et je ne VEUX pas passer par une image je n'ai que des coordonées dans un tableau ...

[pseudocode]

C'est exactement mon objectif mais comment y parvenir c'est ça mon soucis...

Déjà tu peux simplifier ton graphe. Seuls les points d'intersections nous interessent : ce seront les sommets du graphe. Les chemins entre les sommets (= les segments) seront les arcs du graphe.

Pour énumérer les cycles, tu a plusieurs moyens. Le plus simple c'est de faire une exploration exhaustive des chemins. L'exploration peut se faire assez simplement avec la matrice d'adjacence (algo DFS + backtracking).

Une fois que tu as les cycles, tu peux construire le polygone qui représente la face. Il reste à tester si un autre segment est à l'intérieur. Pour cela, il faut tester si un point du segment (par ex. le milieu) est dans le polygone (sujet déjà traité a fond dans ce forum).

[Worm00]

Mes Points sont déjà tous point d'intersection puisque j'ai affaire uniquement a des formes géométriques.
Ok je vais essayer de voir ça. Le truc c'est que je connais rien en backtracking...

PS : Je ne comprend pas pourquoi il faut combiner backtrack et DFS ... Peut tu m'éclairer ?

[Worm00]

AAAAh je crois avoir saisi ! Dit moi si j'ai tort s'il te plait...
Bon en fait j'avais déjà commencer a codé un truc et je viens de me rendre compte que c'était un DFS que j'inventai là sans le savoir... Donc je me retrouve avec un liste de point, c'est là qu'intervient le backtrack non ? en gros je dois tester si le point précédent est bien voisin sinon retourner en arrière jusqu'à en trouver un non ? Du coup je me retrouverai avec une liste du circuit si je ne m'abuse.

PS : D'abord tester si le suivant est voisin sinon cela signifie que j'ai fait un tour.

[pseudocode]

Mes Points sont déjà tous point d'intersection puisque j'ai affaire uniquement a des formes géométriques.

Je voulais dire uniquement les points qui sont une bifurcation (rencontre de au moins 3 segments). Les autres n'interviennent pas dans la détermination des circuits.

Code :

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

1
2
3
4
5
6
7
+-------+
|       |
0---1   |
|   |   |
2---3---4
|       |
+-------+

PS : Je ne comprend pas pourquoi il faut combiner backtrack et DFS ... Peut tu m'éclairer ?
AAAAh je crois avoir saisi ! Dit moi si j'ai tort s'il te plait...

Voila, tu as compris le truc... Tu dois construire tous les chemins possibles dans ton graphe et stocker ceux qui forment un circuit, c'est-à-dire ceux qui reviennent au point de départ.

Comme tu veux déterminer des surfaces, il faut prendre les circuits de longueur au moins 3. Et comme tu veux des surfaces simples (non croisées), il faut prendre les circuits qui sont composés de points différents. Donc les circuits ne peuvent avoir plus de N points (N = nombre de sommets du graphe)

Tout cela permet de construire l'algo : on a une condition d'arrêt (longueur<=N), on a une règle de construction (ajouter des des points qui ne sont pas déjà dans le chemin) et on a un état final (le chemin revient au point de départ). Cela doit prendre une dizaine de lignes en récursif.

Ne pas oublier de supprimer les doublons : des circuits identiques au sens de parcours près, ou au point de départ près.

[Worm00]

A oui pas bête cette histoire d'au moins 2 segment j'aurais du y penser... Donc pour résumer je dois repéré tout mes point d' "intersection" effectuer autant de DFS que ce que j'ai de point d'intersection (en commençant a chaque fois avec un différent) je me retrouve alors avec un liste par point d'intersection, de chacune de ces liste j'extrais mes circuit grace au backtrack.

C'est bien ça ? Si oui, la prochaine fois que j'écris dans ce topic c'est pour confirmer que tout a été codé avec succès j'espère.

[pseudocode]

A oui pas bête cette histoire d'au moins 2 segment j'aurais du y penser... Donc pour résumer je dois repéré tout mes point d' "intersection" effectuer autant de DFS que ce que j'ai de point d'intersection (en commençant a chaque fois avec un différent) je me retrouve alors avec un liste par point d'intersection, de chacune de ces liste j'extrais mes circuit grace au backtrack.

C'est bien cela.

Pour être exact, tu extrais tes circuits grâce au DFS (le backtrack c'est juste une manière d'écrire un algo de DFS).

Un petit exemple en java pour cette partie de l'algo:

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
 
/**
 * @param path list of vertex in the current path
 * @param len length of the current path
 * @param used flag for used vertex
 * @param cycles list of path found so far
 */
private void findcycle(int[] path, int len, boolean[] used, List<int[]> cycles) {
	if (len>N) return; // no more possible path
 
	if (len>2 && matrix[path[len-1]][path[0]]) { // found a cycle
		addCycle(cycles, Arrays.copyOf(path, len));
	}
 
	for(int i=0;i<N;i++) { // add a vertex to the path
		if (used[i]) continue;
		if (len>0 && !matrix[path[len-1]][i]) continue;
		path[len]=i; used[i]=true;
		findcycle(path,len+1,used,cycles);
		used[i]=false;
	}
}

Appelée par un code du genre:

Code java :

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

1
2
3
4
List<int[]> cycles = new ArrayList<int[]>();
int[] path = new int[N];
boolean[] used = new boolean[N];
findcycle(path,0,used,cycles);

Avec:
N : le nombre de sommets du graphe
matrix[][] : la matrice d'adjacence
addCycle() : méthode qui ajoute le "path" dans la liste (avec detection de doublon)

[Worm00]

Waw super ! Bon c'est plus ou moins ce que je devrais avoir a la fin sauf que je n'utilise pas de matrice d'adjacence... Je me suis rendu compte que je suis stupide ... j'ai pas pensé a utiliser CONTINUE !!!

PS : pseudocode tu gères du steak ! En même temps les montpellierains sont les meilleurs en programmation

[pseudocode]

Waw super ! Bon c'est plus ou moins ce que je devrais avoir a la fin sauf que je n'utilise pas de matrice d'adjacence... Je me suis rendu compte que je suis stupide ... j'ai pas pensé a utiliser CONTINUE !!!

L'utilisation des early-exit (break, continue, return ...) est assez mal vue par les "experts" en programmation. Je n'ai jamais bien compris pourquoi. Ça ne m'empêche pas d'en abuser assez souvent.

[Worm00]

L'utilisation des early-exit (break, continue, return ...) est assez mal vue par les "experts" en programmation. Je n'ai jamais bien compris pourquoi. Ça ne m'empêche pas d'en abuser assez souvent.

Oui c'est vrai que en cours jamais on nous en parle mais moi je me dit que si quelqu'un l'as inventé il faut l'utiliser

[Worm00]

En fait le système de ne traiter que les points d'intersection c'est une très mauvaise idée car je peux tout à fait tomber sur une seule face et dans ce cas tout les point on seulement 2 lignes qui en partent

PS : J'ai fini merci pour tout . Franchement pour mon premier passage sur ce forum je suis très content ! Voilà une communauté de programmeur compétente, ça fais plaisir . Je reviendrai c'est sûr !