Discussion :

[defluc]

Code :

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

1
2
3
4
Function Dist2Pnts(X1, Y1, X2, Y2 : Double):Double;
Begin
  Result := Abs(Sqrt(Sqr(X2-X1) + Sqr(Y2-Y1)));
end;

[souviron34]

Code :

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

1
2
3
4
Function Dist2Pnts(X1, Y1, X2, Y2 : Double):Double;
Begin
  Result := Abs(Sqrt(Sqr(X2-X1) + Sqr(Y2-Y1)));
end;

où as-tu pris cette distance ?????

d'une part c'est faux :

Code :

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

d = sqrt ( ((xa-xb)*(xa-xb)) + ((ya -yb)*(ya-yb)) )

et dans ton algo précédent tu reprends SQR du resultat

note : à moins que sqr en Pacal veuille dire carré, mais j'en doute

[defluc]

En Delphi, Sqr est bien le carré d'un nombre alors que Sqrt est sa racine carrée.

[souviron34]

ooops ton erreur vient de là :

Code :

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

1
2
  ParamR := ((Xpnt - Xb)*(Xe - Xb) + (YPnt - Yb) + (Ye - Yb))/Sqr(Len);

c'est pas un +, mais un *

Code :

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

1
2
  ParamR := ( ((Xpnt - Xb)*(Xe - Xb)) + ((YPnt - Yb) * (Ye - Yb)))/Sqr(Len);

[souviron34]

La formule de Dist2Pnts n'est pas fausse: attention à la différence SQRT (racine) et SQR (carré) . (par contre le ABS ne sert à rien)

Mais effectivement, il ne faut pas employer "Sqr(Len)" mais directement "Len" dans DistPntSegm.

non non c'est correct, le dénominateur est le carré de la distance (mais c'est la formule qui a un bug, voir ci-dessus)

[pseudocode]

non non c'est correct, le dénominateur est le carré de la distance (mais c'est la formule)

Oui, j'avais pas vu qu'il remultipliait le résultat par "Len". C'est pas vraiment optimal !!

[Saita]

Bonjour,
Je remonte ce post pour poser une petite question :
Je vais peut être commence par le contexte..
C'est en fait un problème bien connu (j'ai l'impression).
J'ai un point qui se trouve dans un polygone (non croise) et je veux savoir a quelle distance minimum il se trouve du bord. Le but étant de faire sonner une alarme quand le point (qui est donc en mouvement) se trouve a une distance inférieure a une constante définie du bord.
Voila pour la première partie.
J'ai lu avec intérêt http://www.exaflop.org/docs/cgafaq/ a la section 1.02 mais il y a quelquechose que je ne comprend pas pourquoi faut-il diviser le produit scalaire de AC et AB par la norme au carre de AB ?

(1) AC dot AB
r = ---------
||AB||^2

N'est-il pas possible de tout simplement faire le produit scalaire de AB et AC => si il est négatif alors la plus petite distance est AC, s'il est positif on test AC.CB s'il est négatif la plus petite distance est CB sinon on calcule le projeté et la distance CP (et la c'est pas de la tarte avec des divisions des racines carrées et tout et tout )
J'ai aussi lu ce sujet : http://www.developpez.net/forums/d53...ygone-convexe/
Mais j'avoue n'avoir pas tout compris..
Cette histoire de comparer d'abord la distance point sommet ne mène pas je pense...
Désolée pour le pitoyable dessin mais en gros tout ca pour dire que si on ne
considère que les sommets c'est pas bon.
...... __
....../....\
...../......\
..../ x...../
.../........\
../..........\
.|............\
.|________\

Ca j'ai pas compris :

Pour chercher la distance de O au cotés du polygone P_i pour 1<=i<= n. On fait comme si P_{n+1} valait P_1. Le point P_i le plus proche de O n'a rien à voir avec la réponse car si deux sommets consécutifs sont trés éloignés de 0 mais symétriques par rapport à 0 , la réponse sera 0 et obtenu pour ce côte et il pourra y avoir des points P_i beaucoup plus proches.
Je propose de chercher le signe du produit scalaire r_i=P_iO* P_i P_{i+1} et aussi le signe de s_i=P_{i+1}O* P_i P_{i+1} et enfin le signe du produit t_i= r_i* s_i.
Si t_i < 0 alors on doit chercher la distance d_i de O à la droite P_i P_{i+1}.
Si t_i >= 0 alors on ne fait rien.
Enfin on cherche le minimum des distances de O à tous les sommets P_i qu'on compare avec le minimum des d_i. La réponse est le minimum du tout.

Mais si ca marche ca serait cool car pas de division ni de racine carre !
Voili voulou..
Si c'est mieux d'ouvrir un autre sujet dites le moi..
Merci pour votre aide

[SpiceGuid]

Code :

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

1
2
3
4
5
6
7
Function TMapForm.DistPntSegm(XPnt, YPnt, Xb, Yb, Xe, Ye : Double) : Double;
Var
 Len, ParamR, ParamS, X, Y : Double;
begin                               
  Result := 999999;
  ...
end;

Je ne crois pas que le lien donné par souviron signale un cas particulier pour lequel la distance vaudrait 999999. Il faut suivre un raisonnement plutôt que de poluer l'algo avec des valeurs arbitraires.

Ca ce n'est qu'une question de convention, non ? Tout dépend de l'énoncé et de ce qu'on considère comme valide comme distance point / segment.

Je ne vois pas quelle est la convention qui t'interdit de suivre le raisonnement du post n°3 (ou du lien donné par souviron), surtout que l'auteur a fait l'effort de proposer un code dans le post n°5, un code qui, tout comme celui de pseudocode, a le bon goût de ne renvoyer aucune valeur arbitraire.

Désolée pour le pitoyable dessin mais en gros tout ca pour dire que si on ne considère que les sommets c'est pas bon.
...... __
....../....\
...../......\
..../ x...../
.../........\
../..........\
.|............\
.|________\

On avait dit convexe.


N'ayant pas participé à ce fil de discussion c'est en toute objectivité que je peux dire combien il est désolant que vous ne prêtiez pas davantage de crédit et d'attention à l'excellente qualité des réponses qui vous sont faites.

[Saita]

Bonjour SpiceGuid,
J'ai remonte cette conversation d'il y a un an car elle correspondait en partie au probleme que je voulais evoquer.
Mes polygones ne sont pas tous convexes en effet, il peuvent ne pas l'etre.
Je ne suis pas sure que defulc ni Alikendarfen ne liront tes remarques car le sujet est un peu vieux A moins que j'ai fait erreur et que ces remarques ne s'appliquait a moi..

Cette histoire de comparer d'abord la distance point sommet ne mène pas je pense...

J'aurais peut etre du rajouter a la fin de la phrase "pour mon cas".
Car au debut j'avais bien precise :

J'ai un point qui se trouve dans un polygone (non croise)

pas convexe..
Peut etre aurais-je du ouvrir un autre sujet pour eviter la confusion avec les remarques des post precedents..
A propos du post 3, il rejoins ma question car il me semble que c'est a peu pres la meme demarche :

N'est-il pas possible de tout simplement faire le produit scalaire de AB et AC => si il est négatif alors la plus petite distance est AC, s'il est positif on test AC.CB s'il est négatif la plus petite distance est CB sinon on calcule le projeté et la distance CP (et la c'est pas de la tarte avec des divisions des racines carrées et tout et tout )

N'ayant pas participé à ce fil de discussion c'est en toute objectivité que je peux dire combien il est désolant que vous ne prêtiez pas davantage de crédit et d'attention à l'excellente qualité des réponses qui vous sont faites.

Je prete beaucoup de credit a l'excellente qualite des reponses sinon je ne posterai pas ici ! Mais excuses moi, si il y a des choses que je n'ai pas compris, ben j'aime bien poser des questions... Ais-je tort ?

[pseudocode]

N'est-il pas possible de tout simplement faire le produit scalaire de AB et AC => si il est négatif alors la plus petite distance est AC, s'il est positif on test AC.CB s'il est négatif la plus petite distance est CB sinon on calcule le projeté et la distance CP (et la c'est pas de la tarte avec des divisions des racines carrées et tout et tout )

C'est l'algo que j'ai donné au post #2

Mais si ca marche ca serait cool car pas de division ni de racine carre !

Si ton problème est de savoir quand un point est trop proche d'un bord, tu peux comparer les distances "au carré". Comme cela, tu n'as pas a calculer les racines carrés.

[Saita]

Ok je voulais juste etre sure pour le produit scalaire car je n'avais pas compris ca :

(1) AC dot AB
r = ---------
||AB||^2

donc je voulais etre sure de n'etre pas passe a cote de qqch d'important.

Ta remarque est tres bonne pseudocode ! En effet s'il ne s'agit que de comparaison autant tout elever au carre..
Mais on voudrait aussi la distance "exacte" ( mais bon, c'est juste une info au moins mon alarme sera precise )

La derniere question (pour le moment) etant : vu que mon polygone n'est pas convexe, y aurait-il un autre moyen que de tester la distance du point a chaque cote du polygone et de prendre le minimum..
Merci pseudocode en tout cas pour ta reponse

[pseudocode]

La derniere question (pour le moment) etant : vu que mon polygone n'est pas convexe, y aurait-il un autre moyen que de tester la distance du point a chaque cote du polygone et de prendre le minimum..

Disons que c'est la méthode la plus simple.

On peut toujours optimiser pour éviter de tester certains segments mais a mon avis le jeu n'en vaut pas la chandelle sur des "petits" polygones.

[Saita]

Et sur des petits polygones a 1000 sommets ?

[souviron34]

1000 c'est encore petit...

vu que c'est une distance, un test sur Dx ou Dy éliminera déjà un bon nombre.

Code C :

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

1
2
3
4
5
6
7
8
 
for ( i = 0 ; i < NSommets ; i++ )
{
   if ( Dx <= Dist )
     if ( Dy <= Dist )
       {
       }
}

Ensuite, comme pour tout algo comprenant des comparaisons de distances, le mieux est de tout faire par rapport au carré, et ne se servir de la racine qu'à la toute fin, lorsqu'on veut vraiment calculer la distance..


L'autre solution est de trier les sommets, mais il faudra alors calculer au moins N*Log(N) distances (par un qsort par exemple)..

Là tu auras moins que N..

[Saita]

Merci souviron34 de te joindre a la discussion
Ton idée me parait bonne si mon polygone est convexe... Or s'il ne l'est pas j'ai un doute que cela marche. Tout le problème est la.
Dans le "pire" des cas, mon point est situe sur la médiatrice du segment qui lui est le plus proche, a ma distance critique.
Dans ce cas, la distance du point a l'un des 2 sommets est racine(dist²+a²), en considérant a la distance entre mes deux sommets divises par deux. Si je ne me trompe pas...
Le problème étant que a varie en fonction de chaque segment du polygone... Donc "a l'aveuglette' je ne peux pas me mettre de valeur fixe en fonction uniquement de dist. Et si je voulais calculer le a le plus grand...Ça reviendrait a faire aussi un algorithme de calcul de distance ce qui serait a mon avis un peu idiot, non ?

Je n'ai pas encore la notion de ce qui est grand ou pas en informatique il me semblais qu'en dépassant le millier ça commençait a être "grand".

[pseudocode]

Merci souviron34 de te joindre a la discussion
Ton idée me parait bonne si mon polygone est convexe... Or s'il ne l'est pas j'ai un doute que cela marche. Tout le problème est la.
Dans le "pire" des cas, mon point est situe sur la médiatrice du segment qui lui est le plus proche, a ma distance critique.

Est-ce que ton point et ton polygone peuvent avoir des coordonnées quelconques (décimales, infinies, ...) ou alors est-ce qu'on est dans le cas d'une image avec des coordonnées "pixel" (entier entre 0 et Largeur/Hauteur) ?

[Saita]

Mes coordonnees sont des coordonnes latitude, longitude avec 2 decimales de precision apres la virgule. Pourquoi ?

[souviron34]

il y a une idée extrêmement simple, à mon avis :

une boucle sur tous les sommets, en ne gardant qu'un point par (le plus proche) par quadrant.

Puis juste une vérification sur ces 4 points lesquels se suivent : si il ne se suivent pas, ce n'est pas un côté.

Alors on calcule effectivement N distances....

Code C :

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
79
int      ind[4], i1, j1 ;
double dmax[4], d, d1 ;
 
 
/* Initialisation */
for ( i = 0 ; i < 4 ; i++ )
   dmax[i] = DBL_MAX ;
 
 
/* Calcul du point le plus proche par quadrant */
for ( i = 0 ; i < NSommets ; i++ )
 {
     d = ((xi - x)*(xi-x)) + (yi - y)*(yi-y);
 
     if ( yi < y )
       {
          if  ( xi < x )
            {
               if ( d < dmax(0) )
                  {
                     dmax(0) = d ;
                     ind[0] = i ;
                  }
             }
          else
            {
               if ( d < dmax(1) )
                  {
                     dmax(1) = d ;
                     ind[1] = i ;
                  }
            }
        }
      else
        {
          if  ( xi < x )
            {
               if ( d < dmax(2) )
                  {
                     dmax(2) = d ;
                     ind[2] = i ;
                  }
             }
          else
            {
               if ( d < dmax(3) )
                  {
                     dmax(3) = d ;
                     ind[3] = i ;
                  }
            }
        }
}
 
 
/* Vérification du segment le plus proche */
i1 = -1 ;
j1 = -1 ;
d1 = DBL_MAX ;
 
for ( i = 0 ; i < 4 ; i++ )
   {
        for ( j = 0 ; j < 4 ; j++ )
          {
              if ( i != j )
                {
                    if ( iabs(ind[i]-(ind[j]) == 1 )
                       {
                             d = distance_point_segment (x, y, x[ind[i]], y..)
                             if ( d < d1 )
                               {
                                    i1 = i ;
                                    j1 = j ;
                                    d1 = d ;
                               }
                       }
                }
          }
   }

Est-ce qu'il peut y voir des cas où ça ne marche pas ??

[souviron34]

Mes coordonnees sont des coordonnes latitude, longitude avec 2 decimales de precision apres la virgule. Pourquoi ?

le plus simple est, à mon avis, de prendre le problème en sens inverse


Tu as ton polygone de départ..

Tu calcules un "faux" polygone dézoomé (avec la distance en moins).
Et là, tout ce que tu as à faire, c'est vérifier si ton point est dans le premier et pas dans le deuxième..

Avec les algos cités (pt-in-polygon) ça se fera vite...


Moi je l'avais fait en sens inverse dans un soft :

j'avais une région polygonale, et je mettais une alerte quand le point était à l'intérieur d'une certaine distance du polygone. Ce que j'avas fait était calculer au départ le nouveau polygone (avec l'ajout de la distance), et simplement vérifier ensuite que le point était dans ce polygone..

[souviron34]

Est-ce qu'il peut y voir des cas où ça ne marche pas ??

je me répond tout seul : oui