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;