[Graphisme] Winding number
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:
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:
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; |
