Algorithme de dessin d'un contour de polygone

Version imprimable

Voir 40 message(s) de cette discussion en une page

03/01/2008, 11h49
defluc

C'est une vision claire qui me donne une des pistes de solution à laquelle je n'avais pas pensé et je t'en remercie.
Comme quoi, un bon dessin vaut mieux qu'un long discours.
Dès que j'aurai un moment, je m'attacherai à en construire un algorithme qui envisage tous les cas possibles (intersection ou tangence de 2 cercles, intersection ou tangence de cercle et de segment, intersection de 2 segments...).
J'espère que c'est plus simple qu'il n'y parait.
03/01/2008, 12h01
pseudocode

Citation:

Envoyé par defluc

J'espère que c'est plus simple qu'il n'y parait.

Les calculs d'intersections vont etre assez compliqués. Tu peux approximer les cercles par des segments et utiliser les algos classiques (Bentley-Ottmann, ...)

Pour moi, le plus simple serait de discretiser l'image, calculer la carte des distances et marquer tous les pixels qui sont à une distance D. Bien sur ca ne donne pas l'equation du contour, mais ca le dessine rapidement. :P
03/01/2008, 12h17
defluc

Après le tracé du contour, je dois identifier les parcelles cartographiques que celui-ci rencontre.
Je dois donc rester en coordonnées géographiques.
Mais cet algorithme n'a-t-il donc jamais été programmé dans un langage que je pourrais adapter en Delphi ?
03/01/2008, 12h42
pseudocode

Citation:

Envoyé par defluc

Après le tracé du contour, je dois identifier les parcelles cartographiques que celui-ci rencontre.
Je dois donc rester en coordonnées géographiques.

Je ne vois pas pourquoi ca necessite de rester en coordonnées géographiques au lieu des coordonnées des pixels. Mais bon, je te fais confiance sur ce point. ;)

Citation:

Mais cet algorithme n'a-t-il donc jamais été programmé dans un langage que je pourrais adapter en Delphi ?

Je ne connais pas d'algo de calcul d'enveloppe qui donne une solution sous forme d'equations. :?
03/01/2008, 13h01
defluc

Citation:

Je ne vois pas pourquoi ca necessite de rester en coordonnées géographiques au lieu des coordonnées des pixels

Les coordonnées géographiques sont exprimées en mètre avec partie entière à 5 chiffres et 4 décimales. Après transformation en pixels pour calcul du contour, il faut poursuivre le traitement sur les coordonnées géographiques de la carte et donc reconvertir les pixels dans ce système de projection.
Il y a forcément une perte significative de précision.
03/01/2008, 13h12
alex_pi

Citation:

Envoyé par defluc

Les coordonnées géographiques sont exprimées en mètre avec partie entière à 5 chiffres et 4 décimales.

Euuuuuuuuh, t'es en train de nous dire que tu connais la position de l'angle de ta parcelle au dixieme de milimetre là... Genre tu sais si elle est à droite ou à gauche du grin de sable dans la motte de terre. Y a pas comme un soucis ?
03/01/2008, 13h37
defluc

Bon, ok, j'ai une décimale de trop.
Fais une recherche sur "Coordonnées Lambert" et tu en sauras plus.
03/01/2008, 13h46
pseudocode

Citation:

Envoyé par defluc

Bon, ok, j'ai une décimale de trop.
Fais une recherche sur "Coordonnées Lambert" et tu en sauras plus.

Bon, effectivement discretiser tout l'espace est exagéré (10^18 pixels). Mais n'est-il pas possible de réduire la précision des coordonnées ? (elles ont toutes des milimetres significatifs ?)
03/01/2008, 13h47
alex_pi

Citation:

Envoyé par defluc

Bon, ok, j'ai une décimale de trop.
Fais une recherche sur "Coordonnées Lambert" et tu en sauras plus.

Je connais les cooronnées Lambert, pas de problème

Que l'on connaisse la position des point géodésique de premier ordre au milimètre passe encore (et je continue à douter, mais ça fait longtemps que je n'ai pas regardé), mais l'angle d'une parcelle, vu que même sur place on aurait du mal à la placer en dessous de la dizaine de centimètre, j'ai vraiment des *gros* doute ! Tu ne crois pas que tu es en train de t'embêter avec une précision qui n'a pas lieu d'être ? Et quand tu cherches quelle autre parcelle est à moin de n mètres de la première, est ce que si elle a 3mm² qui sont à moins de n mètre, et le reste est plus loin, on va t'en vouloir de la louper ?
03/01/2008, 13h53
defluc

Du point de vue de la précision, ou pourrait se passer des millimètres, voire des centimètres.
Mais cela laisse encore des valeurs d'amplitude élevée.
De plus, cela risque de poser des problèmes de fermeture avec les points fournis.
03/01/2008, 14h05
pseudocode

Citation:

Envoyé par defluc

Du point de vue de la précision, ou pourrait se passer des millimètres, voire des centimètres.
Mais cela laisse encore des valeurs d'amplitude élevée.
De plus, cela risque de poser des problèmes de fermeture avec les points fournis.

Au lieu d'approximer les coordonnées de la parcelle, on peut approximer la forme de l'enveloppe par un polygone avec de nombreux sommets (façon snake)
03/01/2008, 19h28
Graffito
Il me semble qu'il faut scinder le problème en 2 :
- le calcul proprement dit qui doit être aussi exact que possible,
- la représentation qui admet un peu d'imprécision.
En ce qui concerne le calcul, on n'a aucun besoin de l'envellope.
Il suffit de calculer les distances de polygone à polygone (definition géographique) et de la comparer à Dist.
03/01/2008, 22h01
defluc

D'accord, le contour c'est pour que l'utilisateur puisse visualiser les parcelles qui en font partie.
Mais je comptais rechercher les polygones qui étaient dans l'enveloppe pour les sélectionner.
04/01/2008, 00h08
Graffito
Citation:

Mais je comptais rechercher les polygones qui étaient dans l'enveloppe pour les sélectionner.

Quelles sont les routines de distances geographiques qui te manquent parmi celles-ci ?
1. distance_point_point
2. distance_point_segment,
3. point_ appartient_à_polygone
4. distance_point_polygone
5. distance_polygone_polygone

Voici ce dont je dispose :

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
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
79
80
81
82
83
84
85
86
Function Ang2Line(X1, Y1, X2, Y2, X3,Y3, X4, Y4 : Double):Double;
Var
  Ang : Double;
begin
  Ang := arctan2(Y4 - Y3, X4 - X3)- arctan2(Y2 - Y1, X2 - X1) ;  // Arc Tgte A1 Arc Tgte A2
  Result := Ang;
  if Abs(Ang) > Pi then
     Result := 2*Pi - Abs(Ang);
  Result := Abs(Result);
end;
 
Function Dist2Pnts(X1, Y1, X2, Y2 : Double):Double;
Begin
  Result := Abs(Sqrt(Sqr(X2-X1)+Sqr(Y2-Y1)));
end;
 
Function DistPntLine(X1, Y1, X2, Y2, X3,Y3 : Double) : Double;
Var
  A, B, C, L : Double;
begin
  A := Y3 - Y2;
  B := X2 - X3;
  C := (X3*Y2)-(X2*Y3);
  L := Sqrt(Sqr(X3-X2)+Sqr(Y3-Y2));
  Result := ((A*X1)+(B*Y1)+ C)/L;
end;
 
Function PointOnSegment(X1, X2, X3 : Double) : Boolean;
Var
  A: Double;
begin
//Result := (X1 <= X3) and (X3 <= X2);
A :=  (X3-X1)/(X2-X1);
if Not((A<0) or (A > 1)) then Result := True
                         else result := False;
 
end;
 
Function IntersectPnt(X1, Y1, X2, Y2, X3,Y3, X4, Y4 : Double):TInterArray;
Var
  A1, A2, B1, B2, C1, C2, Divis: Double;
begin
  Result[1] := 0;
  Result[2] := 0;
  A1 := Y2-Y1; B1 := X1-X2; C1 := (X2*Y1)- (X1*Y2);
  A2 := Y4-Y3; B2 := X3-X4; C2 := (X4*Y3)- (X3*Y4);
  Divis := A1*B2-B1*A2;
  If Divis = 0 then exit;
  Result[1] := ((B1*C2)-(C1*B2))/Divis;
  Result[2] := ((C1*A2)-(A1*C2))/Divis;
end;
 
Function InterCircSegm(X1, Y1, X2, Y2, Xc, Yc, R : Double):TFourPntsArray;
Var
  A, B, C, Dx, Dy, T, Discrim, D: Double;
begin
  Dy := -(y2-y1); Dx := (x2-x1); // Droite de la forme Dx + Dy + C = 0
  C := X1*Y2 - X2*Y1; // où C := X1*Y2 - X2*Y1
  Discrim := Sqrt(Sqr(Dx)+Sqr(Dy)) ;
  A := DY/Discrim ;  // Cercle (Sqr(X - Xc) + Sqr(Y - Yc) := Sqr(R)
  B := DX/Discrim ;
  D := ((Dy*Xc)+(Dx*Yc)+C)/Discrim ;
  T := Sqr(R)-Sqr(D) ;  //  si T = 0 tangence, si T < 0
  Result[3] := T;
  Result[4] := T;
  if T < 0 then Exit ;  //  pas d'intersection
  Result[1] := Xc-A*D+B*Sqrt(T);
  Result[2] := Yc-B*D-A*Sqrt(T);
  if T = 0 then Exit;   //  C'est le point de Tangence
  Result[3] := Xc-A*D-B*Sqrt(T);
  Result[4] := Yc-B*D+A*Sqrt(T);
end;
 
Function ParallelPnt(X1, Y1, X2, Y2, ParallelDist : Double):TFourPntsArray;
Var
  Ang : Double;
begin
  Ang := ArcTan((Y1-Y2)/(X1-X2));
  if Ang < 0 then Ang := Ang + Pi;
  Ang := -Ang;
  if  (Y2 <= Y1) then Ang := Pi + Ang;
  Result[1] := X1+(ParallelDist*Sin(Ang));
  Result[2] := Y1+(ParallelDist*Cos(Ang));
  Result[3] := X2+(ParallelDist*Sin(Ang));
  Result[4] := Y2+(ParallelDist*Cos(Ang));
end;

04/01/2008, 18h53
Graffito
Il manque donc :
- point_ appartient_à_polygone
- distance_point_polygone
- distance_polygone_polygone
Pour tester l'appartenance d'un point à un polygone, tester la parité du nombre d'intersection de la demi-droite partant du point et dirigée au Nord. Si un sommet est exactement à la mème longitude, le déplacer d'epsilon.

Pour la distance d'un point à polygone, c'est soit inclus (point_ appartient_à_polygone ) ou c'est le Min de la distance à tous les segments.

Pour la distance d'un polygone à un autre polygone, on calcule les distances de chaque sommets des 2 ploygones à l'autre polygone et on rend le min.
05/01/2008, 15h03
defluc

La distance de polygone constitue une solution dans la mesure où elle est inférieure à la distance de référence (Dist).
Mais avec des centaines de parcelles, le temps d'exécution risque d'en pâtir.
Dans un premier temps, il faut tester si la parcelles est contigüe.
Puis, je propose d'extraire de chaque polygone le sommet le plus au nord, le plus à l'est, le plus au sud et le plus à l'ouest, puis de comparer leur distance à chaque sommet.
Il doit y avoir moyen de limiter encore le nombre de tests à effectuer.
05/01/2008, 15h40
Graffito

Citation:

Mais avec des centaines de parcelles, le temps d'exécution risque d'en pâtir.

Je fais ça avec des calculs de distances géographiques exact (pas la projection 2D) et ça ne pose pas de problème de performance sauf quand on est en simulation avec des centaines de milliers de calculs sur les polygones.

Dans ce cas, on utilise une méthode d'optimisation qui consiste à :
- définir pour chaque polygone le centre (barycentre des sommets pondérés par la somme des longueur des 2 segments de chaque coté)
- calculer un cercle insrit (min des distance du barycentre aux segments)
- calculer un cercle externe (max des dist du barycentre aux sommets)
- de comparer les résultats du cercle inscrit et externe,
- ne faire le calcul exact poly-poly que si le résultat est différent.
05/01/2008, 16h52
defluc

Citation:

Pour la distance d'un polygone à un autre polygone, on calcule les distances de chaque sommets des 2 ploygones à l'autre polygone et on rend le min.

Ne serait-ce pas plutôt la distance entre chaque sommet du polygone voisin et chaque arête du polygone de référence qui est à prendre en considération ?
05/01/2008, 21h51
Graffito

Citation:

Ne serait-ce pas plutôt la distance entre chaque sommet du polygone voisin et chaque arête du polygone de référence qui est à prendre en considération ?

C'est ce que je voulais dire;).
Distance de chaque sommet à l'autre polygone, c.à.d à ses segments.
Et ne pas oublier de tester l'inclusion du sommet dans l'autre polygone

Voir 40 message(s) de cette discussion en une page