Discussion :

[Pascal Jankowski]

Winding number ou « indice d’un point autour d’un cycle (lacet) »

C’est une notion mathématique qui joue un rôle essentiel en analyse complexe et qui appliquée au domaine informatique permet notamment de résoudre un problème auquel est souvent confronté le quidam développant des applications graphiques à savoir :

« On dispose à l’écran d’un polygone quelconque et on aimerait savoir si un point pris au hasard sur l’écran se situe ou non à l'intérieur du polygone ».

Immédiatement, on voit l’intérêt de « la chose » sur une image par exemple où l’on détoure plusieurs formes chacune par un polygone. Construire un algorithme qui permet de savoir quelle forme de l’image est survolée par le pointer de la souris, devra utiliser un algorithme mettant en œuvre ce fameux Winding number.

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
unit uWindingNumberTest;
interface
 
uses
  Types;
 
function IsPointInPolygon(X, Y: Integer; Points: array of TPoint): Boolean;
 
implementation
 
function IsPointInPolygon(X, Y: Integer; Points: array of TPoint): Boolean;
var Count, K, J : Integer;
begin
  Result := False;
  Count := Length(Points) ;
  J := Count-1;
  for K := 0 to Count-1 do
  begin
    if ((Points[K].Y <=Y) and (Y < Points[J].Y)) or
       ((Points[J].Y <=Y) and (Y < Points[K].Y)) then
    begin
     if (x < (Points[j].X - Points[K].X) * (y - Points[K].Y) /
        (Points[j].Y - Points[K].Y) + Points[K].X)
       then Result := not Result;
     end;
     J := K;
  end;
end;
 
end.

Exemple d'utilisation :

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
 
var
  wn: boolean;
begin
  wn := IsPointInPolygon(24,543,
                  [
                   Point(311,527),
                   Point(311,545),
                   Point(326,544),
                   Point(326,526)
                   ]);
  if wn
    then ShowMessage('yes')
    else ShowMessage('no');
end;

[Andnotor]

Tu peux faire ce test en utilisant une région

Code :

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

1
2
3
4
5
6
7
8
function IsPointInPolygon(X, Y: Integer; Points: array of TPoint): Boolean;
var
  Rgn :hRgn;
begin
  Rgn := CreatePolygonRgn(Points, Length(Points), WINDING);
  Result := PtInRegion(Rgn, X, Y);
  DeleteObject(Rgn);
end;

[ShaiLeTroll]

Pour ma part, j'ai utilisé PtInPoly de Zarko Gajic dans Is Point in Polygon que l'on trouve dans les archives Embarcadero Newsgroups...

Savoir si un point est dans un polygone.

Dommage TPolygon ne soit qu'un simple tableau et non une class\record ne fournisse pas une Contains comme TRect.Contains

[tourlourou]

N'est-il pas possible de le masquer par une classe du même nom à laquelle on ajouterait un class helper, sur le modèle de ce qu'on voit dans la discussion de Andnotor ?

[Andnotor]

Dommage TPolygon ne soit qu'un simple tableau et non une class\record ne fournisse pas une Contains comme TRect.Contains

J'ai essayé de créer un assistant et... ça fonctionne
Par contre, il faut passer par la fonction à Pascal puisque CreatePolygonRgn travaille sur des TPoint.

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
type
  TPolygonHelper = record helper for TPolygon
    function Contains(X, Y :integer) :boolean;
  end;
 
function TPolygonHelper.Contains(X, Y: integer): boolean;
var
  Count, K, J : Integer;
begin
  Result := False;
  Count  := Length(self);
  J      := Count -1;
 
  for K := 0 to Count-1 do
  begin
    if ((self[K].Y <=Y) and (Y < self[J].Y)) or
       ((self[J].Y <=Y) and (Y < self[K].Y)) then
    begin
     if (x < (self[j].X - self[K].X) * (y - self[K].Y) /
        (self[j].Y - self[K].Y) + self[K].X)
       then Result := not Result;
     end;
     J := K;
  end;
end;

[Pascal Jankowski]

@ShaiLeTroll

Le source que tu as fourni de Zarco Gajic est identique à celui que j'ai posté. J'ai recherché dans mes archives l'algorithme que j'avais copié à l'époque sur son site.
Je l'ai retrouvé et voici ce que j'avais copié à l'époque.

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
function IsInPolygon(P: TPoint; V: array of TPoint):Boolean;
var
  I,w: Integer;
 
  function isLeft(P0,P1,P2: TPoint):Integer;
  begin
    Result := (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
  end;
 
begin
  w := 0;
  for I := 0 to Pred(High(V)) do
    if isLeft(V[I],V[I+1],P) > 0
      then Inc(w)
      else
    if (V[I+1].y <= P.Y) and (isLeft(V[I],V[I+1],P) < 0)
      then Dec(w);
  Result := w > 0;
end;

Qui fonctionne également.

@ Andnotor

[Pascal Jankowski]

@Andnotor

Effectivement ces fonctions de gdi32.dll (accessibles via l'unité Windows.pas ) répondent également au problème.

CreatePolygonRgn, PtInRegion

En revanche, extrait de la dll, nous n'avons pas accès au code source de ces fonctions (ie : on ne connait pas la technique utilisée) et Microsoft n'est pas réputé pour communiquer ses sources.

Pour les fonctions mathématiques cela me dérange car bien souvent avec une approche différente voire nouvelle, on peut bien souvent améliorer les performances.

Pour ma part, j'ai utilisé PtInPoly de Zarko Gajic dans Is Point in Polygon

J'ai vu le source de ptInPoly, c'est une autre approche mais toujours avec la technique du Winding number