Transformer une ligne en polygone

Version imprimable

01/09/2003, 16h52
bl4d3

[Résolu] Transformer une ligne en polygone

Bonjour,
je suis actuellement en train de developper une application dans laquelle on peut tracer des lignes multiples... Chaque polyline est stockee dans un tableau de points. Il faut pouvoir selectionner ces lignes. Mon probleme est a ce niveau. Une polyline est trop fine pour etre selectionnee efficacement. Il me faudrait donc un algorithme pour 'l'entourer' dans un polygone. A noter que les lignes sont soit horizontales soit verticales. Il m'est aussi impossible d'encadrer cet element par un simple rectangle car cela serait trop grossier et pas assez performant. Le mieux est, je pense, d'elargir la ligne ds toute les direction avec un certain rayon. J'ai deja essayer d'ecrire quelques algos mais a chage fois j'ai des problemes au niveau des angles (qui font 90°). Les lignes se croisent. Mon algo se base sur les point precedents et suivants du polyline pour calculer le point central et le dedoubler. Si vous avez des idees ou des suggestion elle seront les bienvenues.
Merci d'avance,

Nico
01/09/2003, 17h12
Kangourou

Salut,

D'abord une remarque :
le probleme initial est juste de pouvoir selectionner une polyline ? Dans ce cas, une solution simple consiste a cacluler la distance minimum entre la polyline et le point clique, et a considerer que tu selectionne si cette distance est inferieure a une valeur que tu fixes en fonction de ton echelle. Ca se fait assez rapidement, car ce sont des segments de droite.

Pour ton algo, ce que tu veux, en fait, c'est entourer une polyline par un polygone, tel que la distance du polygone a la polyline soit d'au moins un certain rayon 'r', c'est ca ?
Si les segments sont horizontaux et verticaux, tu dois pouvoir t'en tirer avec une succesion de boites englobantes rectangulaires.
Si ton premier point est en (x0,y0), et qu'il va dans la direction (ox), vers la droite, tu peux initialiser deux points du polygone a (x0-r, y0-r) et (x0-r,y0+r).
Ensuite tu considere la direction du deuxieme segment. Si c'est vers le haut (je compte les y positivment vers le haut, a l'ecran c'est vers le bas), tu peux placer deux autres points a (x1+r,y1-r) et (x1-r,y1+r). Si c'est vers le bas, tu les places a (x1+r,y1+r) et (x1-r,y1-r). Tu me suis ? Apres, en fonction de la direction du segment courant et du segment suivant, tu peux determiner les coordonnees successives des sommets du polygone entourant la polyline.

voila pour l'instant hesite pas a poser des questions si c'est pas clair.

A+
01/09/2003, 18h45
bl4d3

Ok, j ai lu attentivement ta reponse et c'est exactement ce que je fais.
L'algo est bon, les points sont bien places mais le probleme n'est pas la. Je t'explique. J'ai une polyline de disons 10 element stockee dans un tableau. Je cree donc un autre tableau de 20 pour le polygone. Ensuite je parcour le premier tableau et je rempli le second 2 par 2. Au point 0 correspondra le points 0 et n/2 du polygone. Et le probleme est la. Le polygone 'tourne' et ainsi parfois des fils se croisent. Je m explique. Le point 1 genera les points 1a et 1b. Le 2 les points 2a et 2b. Mais parfois il faut connecter 1a/2a et 1b/2b et d'autre fois 1a/2b 1b/2a. Ce qui fait que le polygone se recoupe. Et je n'arrive pas a savoir quand il faut faire les echange.

ps: cela ne sert pas qu'a identifier les collisions mais aussi a determiner la zone a mettre a jour pour redessiner la ligne. En effet cette derniere doit etre completement contenu dans la zone et ne pas chevaucher (en gros je ne peu pas me contenter de la ligne)

vala ^^
02/09/2003, 09h20
Kangourou

salut,

En fait, je n'arrive pas a voir exactement ton probleme. Normalement, ca devrait etre possible de trouver les coord des points juste en fonction de l'angle (+pi/2 ou -pi/2) entre deux lignes consecutives, et des coordonnees du sommet courant.
Peux-tu donner un exemple (simple, si possible), de confi qui te pose probleme ?

A+

Ok une analyse plus approfondi sur papier m'a permis de soudre le probleme. Pour ce que ca interresse voici l'algo utilisé (en C++) pour les points intermediaire uniquement (ni le premier, ni le dernier). Pour chaque 'angle': f correspond au point precedent, t au suivant et m et le point central. cl et le tableau contenant la polyline. qpa le tableau qui stock le polygone. up et dn les indices correspondant a l'endroit du polygone actuellement modifie (au debut up vaut 0 et dn vaut 2*taille cl-1).

Code:

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
 
 
  // Parcourir les points
  for (uint i=0;i<cl.count();i++){
 
    // C'est le premier point
    if (i==0){ ... }
 
    // C'est le dernier point
    else if (i==cl.count()-1){ ... }
 
    // Ce point est encadre par 2 autres points
    else{
 
      // Obtenir les donnees
      fx = cl.at(i-1).x();
      fy = cl.at(i-1).y();
      mx = cl.at(i).x();
      my = cl.at(i).y();
      tx = cl.at(i+1).x();
      ty = cl.at(i+1).y();
 
      // Placer en fonction de l'angle (8 cas mais correspondent 2 a2)
      if      ( fx<tx  && fy<ty  ){
       qpa.setPoint(up++,mx+5,my-5);
       qpa.setPoint(dn--,mx-5,my+5); 
      }
      else if ( fx<tx  && fy>=ty ){ 
        qpa.setPoint(up++,mx-5,my-5);
        qpa.setPoint(dn--,mx+5,my+5); 
      }
      else if ( fx>=tx && fy<ty  ){ 
        qpa.setPoint(up++,mx+5,my+5);
        qpa.setPoint(dn--,mx-5,my-5); 
      }
      else if ( fx>=tx && fy>=ty ){  // else ?
        qpa.setPoint(up++,mx-5,my+5);
        qpa.setPoint(dn--,mx+5,my-5); 
      }
    }
  }

02/09/2003, 09h29
bl4d3

Au fait merci Kangourou pour ton aide c'est toi qui m'a mis sur la voie :p
A bientot sur ce forum j'espere
Nico
02/09/2003, 09h35
Kangourou

pas de probleme, tu me rendras la pareille un jour.

A+