Faire FLOOD dans un polygone non croisé

Sujet: Faire FLOOD dans un polygone non croisé Dim 20 Sep 2015 - 4:50

La commande 2D_FILL_ON autorise le remplissage des formes
2D_CIRCLE et 2D_RECTANGLE avec la couleur 2D_FILL_COLOR.

Code:: rem ============================================================================
2d_fill_on
2d_fill_color 255,0,0 : 2d_rectangle 250,50,550,250
2d_fill_color 255,255,0 : 2d_circle 400,150,50
rem ============================================================================

Pour une surface quelconque (un polygone), la commande 2D_FILL_ON ne convient plus.
Pour pouvoir remplir la dite surface, on utilise la commande 2D_FLOOD.
Cette commande exige la connaissance des coordonnées d'un point à l'intérieur
de la surface, ce qui n'est pas toujours aisé à déterminer.

Code:: rem ============================================================================
2d_poly_from 500,300 : 2d_poly_to 500,400 : 2d_poly_to 400,350 : 2d_poly_to 500,300
2d_flood 480,320,0,0,255 : ' Le point 480,320 se trouve dans le triangle
rem ============================================================================

Soit le polygone irrégulier suivant formé par 5 segments, donc ayant 5 sommets :
P1(x1,y1) ; P2(x2,y2); P3(x3,y3); P4(x4,y4) et P5(x5,y5)
P1 : x1 = 10, y1 = 20
P2 : x2 = 70, y2 = 150
P3 : x3 = 40, y3 = 30
P4 : x4 = 60, y4 = 10
P5 : x5 = 30, y5 = 20

Code:: rem ============================================================================
dim n : n = 6 : ' Nombre des sommets + 1
dim x(n),y(n), A,Gx,Gy

x(1) = 10 : y(1) = 20
x(2) = 70 : y(2) = 150
x(3) = 40 : y(3) = 30
x(4) = 60 : y(4) = 10
x(5) = 30 : y(5) = 20
x(6) = x(1) : y(6) = y(1)

2d_poly_from x(1),y(1)
2d_poly_to x(2),y(2) : 2d_poly_to x(3),y(3) : 2d_poly_to x(4),y(4)
2d_poly_to x(5),y(5) : 2d_poly_to x(1),y(1) : ' ce dernier point est le même que le 1er pour boucler la boucle
rem ============================================================================

On veut remplir la surface de ce polygone en vert.
On n'a d'autre choix que la commande 2D_FLOOD et cette dernière exige la
connaissance des coordonnées d'un point quelconque à l'intérieur du polygone.
Pour éviter de tâtonner pour trouver ce point, on peut calculer les coordonnées
d'un point particulier dont on est certain qu'il soit à l'intérieur.
Ce point n'est autre que le centre de gravité du polygone.
Pour calculer le centre de gravité d'un polygone irrégulier, on doit d'abord
calculer l'aire de ce même polygone.

Formules :
Calcul de l'aire du polygone :
Pour chaque couple de points d'indice i et i+1, on calcule l'aire
du trapèze délimité par ces 2 points et l'axe des abcisses.
Ce qui donne :
A = 1/2 * la somme de (X(i) * Y(i+1) - X(i+1) * Y(i)) avec i variant de 1 à n-1
Cet algorithme est valable pour tous les polygones "non croisés".

Pour le centre de gravité :
Gx = 1/(6*A) * la somme de (X(i) + X(i+1)) * (X(i) * Y(i+1) - X(i+1) * Y(i))
Gy = 1/(6*A) * la somme de (Y(i) + Y(i+1)) * (X(i) * Y(i+1) - X(i+1) * Y(i))

Code:: rem ============================================================================
SUB Aire()
   dim_local i,s
   for i = 1
SUB Centre_Gravite()
   dim_local i,s
   Aire()
   for i = 1 to n-1
   s = s + (x(i) + x(i+1)) * (x(i) * y(i+1) - x(i+1) * y(i))
   next i
   Gx = s/(6*A)
   s = 0
   for i = 1 to n-1
   s = s + (y(i) + y(i+1)) * (x(i) * y(i+1) - x(i+1) * y(i))
   next i
   Gy = s/(6*A)
END_SUB
rem ============================================================================

Voici le code complet de mon blabla.

Code:: rem ============================================================================
rem FLOOD dans un polygone irrégulier
rem ============================================================================
' La commande 2D_FILL_ON autorise le remplissage des formes
' 2D_CIRCLE et 2D_RECTANGLE avec la couleur 2D_FILL_COLOR.
rem ============================================================================
2d_fill_on
2d_fill_color 255,0,0 : 2d_rectangle 250,50,550,250
2d_fill_color 255,255,0 : 2d_circle 400,150,50
rem ============================================================================
' Pour une surface quelconque (un polygone), la commande 2D_FILL_ON ne convient plus.
' Pour pouvoir remplir la dite surface, on utilise la commande 2D_FLOOD.
' Cette commande exige la connaissance des coordonnées d'un point à l'intérieur
' de la surface, ce qui n'est pas toujours aisé à déterminer.
rem ============================================================================
2d_poly_from 500,300 : 2d_poly_to 500,400 : 2d_poly_to 400,350 : 2d_poly_to 500,300
2d_flood 480,320,0,0,255 : ' Le point 480,320 se trouve dans le triangle
rem ============================================================================
' Soit le polygone irrégulier suivant formé par 5 segments, donc ayant 5 sommets :
' P1(x1,y1) ; P2(x2,y2); P3(x3,y3); P4(x4,y4) et P5(x5,y5)
' P1 : x1 = 10, y1 = 20
' P2 : x2 = 70, y2 = 150
' P3 : x3 = 40, y3 = 30
' P4 : x4 = 60, y4 = 10
' P5 : x5 = 30, y5 = 20
rem ============================================================================
dim n : n = 6 : ' Nombre des sommets + 1
dim x(n),y(n), A,Gx,Gy

x(1) = 10 : y(1) = 20
x(2) = 70 : y(2) = 150
x(3) = 40 : y(3) = 30
x(4) = 60 : y(4) = 10
x(5) = 30 : y(5) = 20
x(6) = x(1) : y(6) = y(1)

2d_poly_from x(1),y(1)
2d_poly_to x(2),y(2) : 2d_poly_to x(3),y(3) : 2d_poly_to x(4),y(4)
2d_poly_to x(5),y(5) : 2d_poly_to x(1),y(1) : ' ce dernier point est le même que le 1er pour boucler la boucle
rem ============================================================================
' On veut remplir la surface de ce polygone en vert.
' On n'a d'autre choix que la commande 2D_FLOOD et cette dernière exige la
' connaissance des coordonnées d'un point quelconque à l'intérieur du polygone.
' Pour éviter de tâtonner pour trouver ce point, on peut calculer les coordonnées
' d'un point particulier dont on est certain qu'il soit à l'intérieur.
' Ce point n'est autre que le centre de gravité du polygone.
' Pour calculer le centre de gravité d'un polygone irrégulier, on doit d'abord
' calculer l'aire de ce même polygone.
' Formules :
' Calcul de l'aire du polygone :
' Pour chaque couple de points d'indice i et i+1, on calcule l'aire
' du trapèze délimité par ces 2 points et l'axe des abcisses.
' Ce qui donne :
' A = 1/2 * la somme de (X(i) * Y(i+1) - X(i+1) * Y(i)) avec i variant de 1 à n-1
' Cet algorithme est valable pour tous les polygones "non croisés".

' Pour le centre de gravité :
' Gx = 1/(6*A) * la somme de (X(i) + X(i+1)) * (X(i) * Y(i+1) - X(i+1) * Y(i))
' Gy = 1/(6*A) * la somme de (Y(i) + Y(i+1)) * (X(i) * Y(i+1) - X(i+1) * Y(i))
rem ============================================================================

Centre_Gravite()
2d_flood Gx,Gy,0,255,0
end

rem ============================================================================
' L'aire obtenue est négative lorsque l'on parcours les points en sens anti-horaire
SUB Aire()
   dim_local i,s
   for i = 1 to n-1
   s = s + x(i) * y(i+1) - x(i+1) * y(i)
   next i
   A = s/2
END_SUB
rem ============================================================================
SUB Centre_Gravite()
   dim_local i,s
   Aire()
   for i = 1 to n-1
   s = s + (x(i) + x(i+1)) * (x(i) * y(i+1) - x(i+1) * y(i))
   next i
   Gx = s/(6*A)
   s = 0
   for i = 1 to n-1
   s = s + (y(i) + y(i+1)) * (x(i) * y(i+1) - x(i+1) * y(i))
   next i
   Gy = s/(6*A)
END_SUB
rem ============================================================================

Sujet: Re: Faire FLOOD dans un polygone non croisé Dim 20 Sep 2015 - 7:51

Très intéressant ce principe.

Il me semble que Klaus avez donné aussi une méthode pour savoir si on se trouvait a l'intérieur ou l'extérieur du polygone. Mais là c'est top !

Sujet: Re: Faire FLOOD dans un polygone non croisé Dim 20 Sep 2015 - 10:52

Oui la méthode donnée pour savoir si un point quelconque est dans le polygone ou non est dans le dernier article sur les collisions (le programme qui manque c'est celui testant si 2 poygones quelconques se touchent).
Parc contre là, la méthode de de Papydall c'est un peu le contraire, c'est pour déterminer automatiquement un point à l'intérieur afin de faire le flood par exemple.

Sujet: Re: Faire FLOOD dans un polygone non croisé Dim 20 Sep 2015 - 11:12

C'est un sujet intéressant, qui mérite un article. Very Happy

Le travail est déjà pratiquement fait.

A+

Sujet: Re: Faire FLOOD dans un polygone non croisé Dim 20 Sep 2015 - 13:05

Bonjour les amis et merci pour vos retours.

Jean Claude a écrit:: C'est un sujet intéressant, qui mérite un article.
Le travail est déjà pratiquement fait.

Oui, ça mérite un article et j’ai une petite idée derrière pour un autre usage. Idea

Sujet: Re: Faire FLOOD dans un polygone non croisé Lun 21 Sep 2015 - 10:44

Le centre de gravité n'est pas toujours à l'intérieur du polygone. Essayez avec x(4) = 200

Sujet: Re: Faire FLOOD dans un polygone non croisé Lun 21 Sep 2015 - 10:54

Dans ce cas, il faut faire le calcul du centre de gravité sur 3 point et faire un test que ce point est à l'intérieur. Si oui, on s'arrète, sinon on essaye avec un quatrième point si dedans, on s'arrète, sinon, on exclu le premier et on test si le centre de gravité du nouveau triangle est dedans, etc ... ? Bon ce n'est pas un algorithme, et c'est une méthode un peu bourrin mais ça doit marcher, non ?

Sujet: Re: Faire FLOOD dans un polygone non croisé Lun 21 Sep 2015 - 13:36

La méthode que j'avais déjà publiée, donne le résultat correct même pour un polygone "croisé". Petit rappel:
Soit P un polygone quelconque de n sommets.
Soit T un point à tester.
Alors, T est à l'intérieur du polygone si et seulement si les intersections d'une droite quelconque (horizontale ou verticale, par exemple) passant par T avec les faces du polygone P ont un nombre impair d'un côté et de l'autre du point T.

Il est facile de calculer les intersections d'une droite, en particulier d'une droite horizontale ou verticale, avec une droite donnée par un point. Pour un polygone P de n sommets, il y a n faces déterminées par deux points adjacents: (P1,P2), (P2,P3), ...,(pn,p1).

Sujet: Re: Faire FLOOD dans un polygone non croisé Lun 21 Sep 2015 - 13:58

Klaus: C'est ce que j'ai essayé d'expliquer, mais ta version est certainement plus claire Wink

Sujet: Re: Faire FLOOD dans un polygone non croisé Lun 21 Sep 2015 - 14:30

Salut tout le monde.
Bien vu Jean Debord, le centre de gravité n’est pas toujours dans le polygone.

@Klaus
Le problème n’est pas de tester si un point est à l’intérieur du polygone ou non.
Mais de TROUVER un point qui est à l’intérieur du polygone. Ce n’est pas le même problème.

Sujet: Re: Faire FLOOD dans un polygone non croisé Lun 21 Sep 2015 - 15:19

Ce n'est pas vraiment compliqué...

Tu prends un angle quelconque, tu décales légèrement en x, y ou les deux, et tu testes si le point est dedans. Si oui, alors bingo. Si non, alors tu pars vers le côté oppose...

Dernière édition par Klaus le Mar 22 Sep 2015 - 13:02, édité 1 fois

Voici un petit code 100 % Panoramic qui réalise cela.

Tu as des data qui définissent un polygone quelconque, et un point ) tester. Le point défini actuellement est "en-dehors", ce qui est signalé par un message "0". Mais il y a une ligne de data à activer pour tester le cas d'un point "dedans" qui provoquera un message "1".

Le programme trace le rectangle en noir, et un petit cercle en noir pour le point à tester. On peut ainsi vérifier si la SUB marche.

Après validation du message, le programme cherche un point qui est dans le polygone avec certitude. Il y affuche un cercle rouge. Ce point est toujours décalé de 1 pixels vers la droite et vers le bas d'un coin quelconque, car il y a toujours au moins un point pour lequel cet endroit se trouve dans le polygone (à moins d'avoir des polygones microscopiques...).

Voici le code:

Code:: dim result%, i%
dim n_poly%
dim pnt(1),poly(200,1)
dim coin%

' décrire le polygone
data 6 : ' nombre de points
data 200,130
data 160,40
data 100,20
data 120,80
data 10,60
data 200,130
' décrire le point
' data 140,50 : ' dedans
data 240,50 : ' dehors

read n_poly%
for i%=0 to n_poly%-1
  read poly(i%,0)
  read poly(i%,1)
next i%
read pnt(0)
read pnt(1)

2d_poly_from poly(0,0),poly(0,1)
for i%=1 to n_poly%-1
  2d_poly_to poly(i%,0),poly(i%,1)
next i%
2d_circle pnt(0),pnt(1),3

PointInPolygon()
message str$(result%)

2d_pen_color 255,0,0
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
  pnt(0) = poly(coin%,0) + 2
  pnt(1) = poly(coin%,1) + 2
  PointInPolygon()
  if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
   end
  end_if
next coin%
message "oups"

end

sub PointInPolygon()
  result% = 0

  dim_local ToTheLeftofPoint%, ToTheRightofPoint%
  dim_local np%, OpenPolygon%, XIntersection
  dim_local lg1%, lg2%

  ToTheLeftofPoint% = 0
  ToTheRightofPoint% = 0
  OpenPolygon% = 1

  ' tests if the polygon is closed

  if Poly(0,0)=Poly(n_poly%-1,0)
   if Poly(0,1)=Poly(n_poly%-1,1)
   OpenPolygon% = 0
   end_if
  end_if
  if OpenPolygon%=1 then exit_sub : ' !!!!!!! impossible pour un polygone non fermé
  ' tester chaque couple de points (faces) pour voir si la droite entre eux
  ' coupe l'horizontale passant par le point de test

  for np%=1 to n_poly%-1
   lg1% = 0
   lg2% = 0
   if (Poly(np%-1,1)<=pnt(1)) and (Poly(np%,1)>pnt(1)) then lg1% = 1
   if (Poly(np%-1,1)>pnt(1)) and (Poly(np%,1)<=pnt(1)) then lg2% = 1
   if (lg1%=1) or (lg2%=1)
   ' si tel est le cas
   ' calculer les coordonnées x de l'intersection
   XIntersection = Poly(np%-1,0) + ((Poly(np%,0)-Poly(np%-1,0)) / (Poly(np%,1)-Poly(np%-1,1))) * (pnt(1)-Poly(np%-1,1))

   ' incrementer e compteur approprié
   if XIntersection<pnt(0) then ToTheLeftofPoint% = ToTheLeftofPoint% + 1
   if XIntersection>pnt(0) then ToTheRightofPoint% = ToTheRightofPoint% + 1
   end_if
  next np%

  ' if the polygon is open, test for the last side

  if (bin_and(ToTheLeftofPoint%,1)=1) and (bin_and(ToTheRightofPoint%,1)=1) then Result% = 1
end_sub

Le code est brut, sans commentaires. Je vous laisse l'analyser...

EDIT

Légère modificaction, avec remplissage automatique du polygone...

Sujet: Re: Faire FLOOD dans un polygone non croisé Mar 22 Sep 2015 - 2:35

Merci Klaus pour le code.
Je l’analyserai sûrement.
Actuellement je suis sur un autre problème qui me donne du fil à retordre !
J’en viendrai à bout , c’est certain.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mar 22 Sep 2015 - 2:41

Bon courage ! Je suis également sur un gros morceau, dont j'espère venir à bout. J'avance, mais je n'ai pas encore de certitude. C'est ce qui donne du piment à l'affaire...

Sujet: Re: Faire FLOOD dans un polygone non croisé Mar 22 Sep 2015 - 2:49

Bon courage à toi également.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mar 22 Sep 2015 - 7:09

Bonjour a tous !

Je vois que l'on rencontre tous des problèmes donc ça me rassure, D'autant plus quand c'est Klaus ! Laughing

Sujet: Re: Faire FLOOD dans un polygone non croisé Mar 22 Sep 2015 - 13:53

Voici une version un peu plus aboutie. Au début, on répond à une question si l'on veut choisir les coins par un clic de souris. En cas de réponse négative, le programme fonctionne comme avant. Mais en cas de réponse positive, le programme affiche 3 boutons: Effacer, Fermer et Chercher. Un clic dans la surface de dessin définit un angle du polygone. Le premier n'est pas visible directement (juste un 2d_line_from). Puis, point par point, le polygone est dessiné. Pour le fermer, cliquer sur le bouton "Fermer". Ensuite, le bouton "Chercher" cherche un point dans le polygone et le remplit de rouge. Le bouton "Effacer" efface le polygone et permet de recommencer.

Code:: ' chercher_un_point_dans_un_polygone.bas

label nouveau_coin, effacer, fermer, chercher

dim result%, i%
dim n_poly%
dim pnt(1),poly(200,1)
dim coin%

' décrire le polygone
data 6 : ' nombre de points
data 200,130
data 160,40
data 100,20
data 120,80
data 10,60
data 200,130
' décrire le point
' data 140,50 : ' dedans
data 240,50 : ' dehors

picture 10 : full_space 10 : color 10,255,255,255
2d_target_is 10

if message_confirmation_yes_no("Sélection des coins par clic de souris ?")=1
on_click 10,nouveau_coin
button 1 : top 1,0 : left 1,0 : caption 1,"Effacer" : on_click 1,effacer
button 2 : top 2,25 : left 2,0 : caption 2,"Fermer" : on_click 2,fermer
button 3 : top 3,50 : left 3,0 : caption 3,"Chercher" : on_click 3,chercher
end
end_if

read n_poly%
for i%=0 to n_poly%-1
read poly(i%,0)
read poly(i%,1)
next i%
read pnt(0)
read pnt(1)

2d_poly_from poly(0,0),poly(0,1)
for i%=1 to n_poly%-1
2d_poly_to poly(i%,0),poly(i%,1)
next i%
2d_circle pnt(0),pnt(1),3

PointInPolygon()
message str$(result%)

2d_pen_color 255,0,0
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
pnt(0) = poly(coin%,0) + 2
pnt(1) = poly(coin%,1) + 2
PointInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
end
end_if
next coin%
message "oups"
end

nouveau_coin:
n_poly% = n_poly% + 1
poly(n_poly%-1,0) = mouse_x_left_down(10)
poly(n_poly%-1,1) = mouse_y_left_down(10)
if n_poly%=1
2d_poly_from poly(n_poly%-1,0),poly(n_poly%-1,1)
else
2d_poly_to poly(n_poly%-1,0),poly(n_poly%-1,1)
end_if
return

effacer:
color 10,255,255,255
n_poly% = 0
return

fermer:
if n_poly%<1 then return
if (poly(0,0)<>poly(n_poly%-1,0)) or (poly(0,1)<>poly(n_poly%-1,1))
n_poly% = n_poly% + 1
poly(n_poly%-1,0) = poly(0,0)
poly(n_poly%-1,1) = poly(0,1)
2d_poly_to poly(0,0),poly(0,1)
end_if
return

chercher:
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
PointSurMediane(coin%,0)
PointInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
return
end_if
PointSurMediane(coin%,1)
PointInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
return
end_if
return
next coin%
message "oups"
return

sub PointInPolygon()
result% = 0

dim_local ToTheLeftofPoint%, ToTheRightofPoint%
dim_local np%, OpenPolygon%, XIntersection
dim_local lg1%, lg2%

ToTheLeftofPoint% = 0
ToTheRightofPoint% = 0
OpenPolygon% = 1
if n_poly%<3 then exit_sub

' test si le polygone est fermé
if Poly(0,0)=Poly(n_poly%-1,0)
if Poly(0,1)=Poly(n_poly%-1,1)
OpenPolygon% = 0
end_if
end_if
if OpenPolygon%=1 then exit_sub : ' impossible pour polygone non fermé

' tester chaque couple de points (faces) pour voir si la droite entre eux
' coupe l'horizontale passant par le point de test
for np%=1 to n_poly%-1
lg1% = 0
lg2% = 0
if (Poly(np%-1,1)<=pnt(1)) and (Poly(np%,1)>pnt(1)) then lg1% = 1
if (Poly(np%-1,1)>pnt(1)) and (Poly(np%,1)<=pnt(1)) then lg2% = 1
if (lg1%=1) or (lg2%=1)
' si tel est le cas
' calculer les coordonnées x de l'intersection
XIntersection = Poly(np%-1,0) + ((Poly(np%,0)-Poly(np%-1,0)) / (Poly(np%,1)-Poly(np%-1,1))) * (pnt(1)-Poly(np%-1,1))

' incrementer e compteur approprié
if XIntersection<pnt(0) then ToTheLeftofPoint% = ToTheLeftofPoint% + 1
if XIntersection>pnt(0) then ToTheRightofPoint% = ToTheRightofPoint% + 1
end_if
next np%

' if the polygon is open, test for the last side

if (bin_and(ToTheLeftofPoint%,1)=1) and (bin_and(ToTheRightofPoint%,1)=1) then Result% = 1
end_sub

sub PointSurMediane(p%,act%)
dim_local pm1%, pp1%, xm, ym, x, y, m, fact%
fact% = 1
if act%=1 then fact% = -1
pm1% = p% - 1
if pm1%<0 then pm1% = n_poly% -2
pp1% = p% + 1
if pp1%>=n_poly% then pp1% = 0

xm = (poly(pm1%,0)-poly(pp1%,0))/2
ym = (poly(pm1%,1)-poly(pp1%,1))/2
x = poly(pp1%,0) + xm
y = poly(pp1%,1) + ym
m = 0 - (poly(p%,1)-y)/(poly(p%,0)-x)
pnt(0) = poly(p%,0) + fact%*sgn(poly(p%,0)-x)*10
pnt(1) = poly(p%,1) + fact%*sgn(poly(p%,1)-y)*abs(m)*10
end_sub

Et voici une capture:
Faire FLOOD dans un polygone non croisé Aa116

EDIT

Correction d'un bug, prise en compte complète des angles obtus internes. On calcule maintenant systématiquement un point interieur en partant du coin 0. Le procéde consiste à calculer la médiane de l'angle au point 0, formé par les côtés (P0,P1) et (P0,Pmax-1). On se décale de 10 pixels à l'intérieur pour déterminer le point. Ce chiffre de 10 peut être réduit si besoin, mais pas en-dessous de 2. Si le point trouvé est en-dehors du polygone (cas d'un angle obtus interne), on projete le même point de l'autre côté (à 180°) pour obtenir un poinrt qui est systématiquement dans le polygone.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 9:44

Merci Klaus.

Je teste cela dès que possible.

Ce serait parfait pour l'article que je suis en train de préparer sur les sprites.

Peut-être Papydall et toi pourriez-vous faire un article à paraître dans le même numéro ?

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 9:49

Voici une version légèrement modifiée pour simplifier la détection si un point est à l'intérieur d'un polygone:

Code:: ' chercher_un_point_dans_un_polygone.bas

label nouveau_coin, effacer, fermer, chercher

dim result%, i%
dim n_poly%
dim pnt(1),poly(200,1)
dim coin%

' décrire le polygone
data 6 : ' nombre de points
data 200,130
data 160,40
data 100,20
data 120,80
data 10,60
data 200,130
' décrire le point
' data 140,50 : ' dedans
data 240,50 : ' dehors

picture 10 : full_space 10 : color 10,255,255,255
2d_target_is 10

if message_confirmation_yes_no("Sélection des coins par clic de souris ?")=1
  on_click 10,nouveau_coin
  button 1 : top 1,0 : left 1,0 : caption 1,"Effacer" : on_click 1,effacer
  button 2 : top 2,25 : left 2,0 : caption 2,"Fermer" : on_click 2,fermer
  button 3 : top 3,50 : left 3,0 : caption 3,"Chercher" : on_click 3,chercher
  end
end_if

read n_poly%
for i%=0 to n_poly%-1
  read poly(i%,0)
  read poly(i%,1)
next i%
read pnt(0)
read pnt(1)

2d_poly_from poly(0,0),poly(0,1)
for i%=1 to n_poly%-1
  2d_poly_to poly(i%,0),poly(i%,1)
next i%
2d_circle pnt(0),pnt(1),3

PointInPolygon()
message str$(result%)

2d_pen_color 255,0,0
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
  pnt(0) = poly(coin%,0) + 2
  pnt(1) = poly(coin%,1) + 2
  PointInPolygon()
  if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
   end
  end_if
next coin%
message "oups"
end

nouveau_coin:
  n_poly% = n_poly% + 1
  poly(n_poly%-1,0) = mouse_x_left_down(10)
  poly(n_poly%-1,1) = mouse_y_left_down(10)
  if n_poly%=1
   2d_poly_from poly(n_poly%-1,0),poly(n_poly%-1,1)
  else
   2d_poly_to poly(n_poly%-1,0),poly(n_poly%-1,1)
  end_if
  return

effacer:
  color 10,255,255,255
  n_poly% = 0
  return

fermer:
  if n_poly%<1 then return
  if (poly(0,0)<>poly(n_poly%-1,0)) or (poly(0,1)<>poly(n_poly%-1,1))
   n_poly% = n_poly% + 1
   poly(n_poly%-1,0) = poly(0,0)
   poly(n_poly%-1,1) = poly(0,1)
   2d_poly_to poly(0,0),poly(0,1)
  end_if
  return

chercher:
  2d_fill_color 255,0,0
  for coin%=0 to n_poly%-1
   PointSurMediane(coin%,0)
   PointInPolygon()
   if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
   return
   end_if
   PointSurMediane(coin%,1)
   PointInPolygon()
   if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
   return
   end_if
return
  next coin%
  message "oups"
  return

sub PointInPolygon()
  result% = 0

  dim_local aDroite%, aGauche%
  dim_local np%, OpenPolygon%, XIntersection
  dim_local lg1%, lg2%

  aDroite% = 0
  aGauche% = 0
  OpenPolygon% = 1
  if n_poly%<3 then exit_sub

  ' test si le polygone est fermé
  if Poly(0,0)=Poly(n_poly%-1,0)
   if Poly(0,1)=Poly(n_poly%-1,1)
   OpenPolygon% = 0
   end_if
  end_if
  if OpenPolygon%=1 then exit_sub : ' impossible pour polygone non fermé

  ' tester chaque couple de points (faces) pour voir si la droite entre eux
  ' coupe l'horizontale passant par le point de test
  for np%=1 to n_poly%-1
   lg1% = 0
   lg2% = 0
   if (Poly(np%-1,1)<=pnt(1)) and (Poly(np%,1)>pnt(1)) then lg1% = 1
   if (Poly(np%-1,1)>pnt(1)) and (Poly(np%,1)<=pnt(1)) then lg2% = 1
   if (lg1%=1) or (lg2%=1)
   ' si tel est le cas
   ' calculer les coordonnées x de l'intersection
   XIntersection = Poly(np%-1,0) + ((Poly(np%,0)-Poly(np%-1,0)) / (Poly(np%,1)-Poly(np%-1,1))) * (pnt(1)-Poly(np%-1,1))

   ' adapter l'indicateur approprié
   if XIntersection<pnt(0) then aGauche% = 1 - aGauche%
   if XIntersection>pnt(0) then aDroite% = 1 - aDroite%
   end_if
  next np%
  if (aDroite%=1) and (aGauche%=1) then Result% = 1
end_sub

sub PointSurMediane(p%,act%)
  dim_local pm1%, pp1%, xm, ym, x, y, m, fact%
  fact% = 1
  if act%=1 then fact% = -1
  pm1% = p% - 1
  if pm1%<0 then pm1% = n_poly% -2
  pp1% = p% + 1
  if pp1%>=n_poly% then pp1% = 0

  xm = (poly(pm1%,0)-poly(pp1%,0))/2
  ym = (poly(pm1%,1)-poly(pp1%,1))/2
  x = poly(pp1%,0) + xm
  y = poly(pp1%,1) + ym
  m = 0 - (poly(p%,1)-y)/(poly(p%,0)-x)
  pnt(0) = poly(p%,0) + fact%*sgn(poly(p%,0)-x)*10
  pnt(1) = poly(p%,1) + fact%*sgn(poly(p%,1)-y)*abs(m)*10
end_sub

EDIT

On détecte si un point P est à l'intérieur d'un polygone fermé non croise si le nombre d'intersections d'une droite (horizontale, mais c'est vrai pour une droite quelconque) avec les faces su polygone, compté séparément à gauche et à droite du point P, est impair.

En réalité, ces deux nombres sont, soit tous les deux impairs, soit tous les deux pairs. Il suiffit donc de ne tester qu'un seul côté, ce qui simplifie et accélère la détection. Dans mon code, cela revient à supprimer tout ce qui se réfère à la variable aDroite%.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 13:18

Bonjour Klaus

Je viens de tester ton code.
Ok pour des polygones non croisés.

Le programme tel quel n’est pas satisfaisant pour un polygone croisé.

Spoiler:

Une petite modification du code (suppression de 3 instructions RETURN dans le S/P Chercher: permet de « Flooder » un polygone croisé

Spoiler:

Et même un polygone « Poly-croisé »

Spoiler:

Mais il y en toujours des exceptions :

Spoiler:

Voici le code modifié

Code:: ' chercher_un_point_dans_un_polygone.bas

label nouveau_coin, effacer, fermer, chercher

dim result%, i%
dim n_poly%
dim pnt(1),poly(200,1)
dim coin%

' décrire le polygone
data 6 : ' nombre de points
data 200,130
data 160,40
data 100,20
data 120,80
data 10,60
data 200,130
' décrire le point
' data 140,50 : ' dedans
data 240,50 : ' dehors

picture 10 : full_space 10 : color 10,255,255,255
2d_target_is 10

if message_confirmation_yes_no("Sélection des coins par clic de souris ?")=1
  on_click 10,nouveau_coin
  button 1 : top 1,0 : left 1,0 : caption 1,"Effacer" : on_click 1,effacer
  button 2 : top 2,25 : left 2,0 : caption 2,"Fermer" : on_click 2,fermer
  button 3 : top 3,50 : left 3,0 : caption 3,"Chercher" : on_click 3,chercher
  end
end_if

read n_poly%
for i%=0 to n_poly%-1
  read poly(i%,0)
  read poly(i%,1)
next i%
read pnt(0)
read pnt(1)

2d_poly_from poly(0,0),poly(0,1)
for i%=1 to n_poly%-1
  2d_poly_to poly(i%,0),poly(i%,1)
next i%
2d_circle pnt(0),pnt(1),3

PointInPolygon()
message str$(result%)

2d_pen_color 255,0,0
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
  pnt(0) = poly(coin%,0) + 2
  pnt(1) = poly(coin%,1) + 2
  PointInPolygon()
  if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
   end
  end_if
next coin%
message "oups"
end

nouveau_coin:
  n_poly% = n_poly% + 1
  poly(n_poly%-1,0) = mouse_x_left_down(10)
  poly(n_poly%-1,1) = mouse_y_left_down(10)
  if n_poly%=1
   2d_poly_from poly(n_poly%-1,0),poly(n_poly%-1,1)
  else
   2d_poly_to poly(n_poly%-1,0),poly(n_poly%-1,1)
  end_if
  return

effacer:
  color 10,255,255,255
  n_poly% = 0
  return

fermer:
  if n_poly%<1 then return
  if (poly(0,0)<>poly(n_poly%-1,0)) or (poly(0,1)<>poly(n_poly%-1,1))
   n_poly% = n_poly% + 1
   poly(n_poly%-1,0) = poly(0,0)
   poly(n_poly%-1,1) = poly(0,1)
   2d_poly_to poly(0,0),poly(0,1)
  end_if
  return

chercher:
  2d_fill_color 255,0,0
  for coin%=0 to n_poly%-1
   PointSurMediane(coin%,0)
   PointInPolygon()
   if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
' return : ' < ==================== Supprimer cette ligne
   end_if
   PointSurMediane(coin%,1)
   PointInPolygon()
   if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
  ' return : ' < ==================== Supprimer cette ligne
   end_if
' return : ' < ==================== Supprimer cette ligne
  next coin%
message "oups"
  return

sub PointInPolygon()
  result% = 0

  dim_local aDroite%, aGauche%
  dim_local np%, OpenPolygon%, XIntersection
  dim_local lg1%, lg2%

  aDroite% = 0
  aGauche% = 0
  OpenPolygon% = 1
  if n_poly%<3 then exit_sub

  ' test si le polygone est fermé
  if Poly(0,0)=Poly(n_poly%-1,0)
   if Poly(0,1)=Poly(n_poly%-1,1)
   OpenPolygon% = 0
   end_if
  end_if
  if OpenPolygon%=1 then exit_sub : ' impossible pour polygone non fermé

  ' tester chaque couple de points (faces) pour voir si la droite entre eux
  ' coupe l'horizontale passant par le point de test
  for np%=1 to n_poly%-1
   lg1% = 0
   lg2% = 0
   if (Poly(np%-1,1)<=pnt(1)) and (Poly(np%,1)>pnt(1)) then lg1% = 1
   if (Poly(np%-1,1)>pnt(1)) and (Poly(np%,1)<=pnt(1)) then lg2% = 1
   if (lg1%=1) or (lg2%=1)
   ' si tel est le cas
   ' calculer les coordonnées x de l'intersection
   XIntersection = Poly(np%-1,0) + ((Poly(np%,0)-Poly(np%-1,0)) / (Poly(np%,1)-Poly(np%-1,1))) * (pnt(1)-Poly(np%-1,1))

   ' adapter l'indicateur approprié
   if XIntersection<pnt(0) then aGauche% = 1 - aGauche%
   if XIntersection>pnt(0) then aDroite% = 1 - aDroite%
   end_if
  next np%
  if (aDroite%=1) and (aGauche%=1) then Result% = 1
end_sub

sub PointSurMediane(p%,act%)
  dim_local pm1%, pp1%, xm, ym, x, y, m, fact%
  fact% = 1
  if act%=1 then fact% = -1
  pm1% = p% - 1
  if pm1%<0 then pm1% = n_poly% -2
  pp1% = p% + 1
  if pp1%>=n_poly% then pp1% = 0

  xm = (poly(pm1%,0)-poly(pp1%,0))/2
  ym = (poly(pm1%,1)-poly(pp1%,1))/2
  x = poly(pp1%,0) + xm
  y = poly(pp1%,1) + ym
  m = 0 - (poly(p%,1)-y)/(poly(p%,0)-x)
  pnt(0) = poly(p%,0) + fact%*sgn(poly(p%,0)-x)*10
  pnt(1) = poly(p%,1) + fact%*sgn(poly(p%,1)-y)*abs(m)*10
end_sub

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 13:27

Merci pour ton analyse, Papydall.

Le cas des polygones poly-croisés est complexe. Certes, il restent des exceptions dans ta version. Pour ma part, je me suis concentré sur le titre de ce fil de discussion: "Faire FLOOD dans un polygone non croisé". Et là, ça le fait...

Je garde également ta version - je verrai bien ce que je pourrai en faire.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 13:32

Merci Klaus.

Ça permet, tout de même de faire des bonnes choses avec ce code.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 13:47

Oui, ça répond à plus de 95% des besoins "normaux"
Un code a garder dans un coin ou à ressortir dans un article sur le dessin avec Panoramic si ça tente quelqu'un.

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 14:10

Avec la version suivante de ce code, on colorie systématiquement toutes les parties qui sont issues d'un angle du polygone. Celles qui sont visuellement créées par des intersections de faces, sont ignorés:

Code:: ' chercher_un_point_dans_un_polygone_poly_croise.bas

label nouveau_coin, effacer, fermer, chercher

dim result%, i%
dim n_poly%
dim pnt(1),poly(200,1)
dim coin%

' décrire le polygone
data 6 : ' nombre de points
data 200,130
data 160,40
data 100,20
data 120,80
data 10,60
data 200,130
' décrire le point
' data 140,50 : ' dedans
data 240,50 : ' dehors

picture 10 : full_space 10 : color 10,255,255,255
2d_target_is 10

if message_confirmation_yes_no("Sélection des coins par clic de souris ?")=1
  on_click 10,nouveau_coin
  button 1 : top 1,0 : left 1,0 : caption 1,"Effacer" : on_click 1,effacer
  button 2 : top 2,25 : left 2,0 : caption 2,"Fermer" : on_click 2,fermer
  button 3 : top 3,50 : left 3,0 : caption 3,"Chercher" : on_click 3,chercher
  end
end_if

read n_poly%
for i%=0 to n_poly%-1
  read poly(i%,0)
  read poly(i%,1)
next i%
read pnt(0)
read pnt(1)

2d_poly_from poly(0,0),poly(0,1)
for i%=1 to n_poly%-1
  2d_poly_to poly(i%,0),poly(i%,1)
next i%
2d_circle pnt(0),pnt(1),3

PointInPolygon()
message str$(result%)

2d_pen_color 255,0,0
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
  pnt(0) = poly(coin%,0) + 2
  pnt(1) = poly(coin%,1) + 2
  PointInPolygon()
  if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
' end
  end_if
next coin%
' message "oups"
end

nouveau_coin:
  n_poly% = n_poly% + 1
  poly(n_poly%-1,0) = mouse_x_left_down(10)
  poly(n_poly%-1,1) = mouse_y_left_down(10)
  if n_poly%=1
   2d_poly_from poly(n_poly%-1,0),poly(n_poly%-1,1)
  else
   2d_poly_to poly(n_poly%-1,0),poly(n_poly%-1,1)
  end_if
  return

effacer:
  color 10,255,255,255
  n_poly% = 0
  return

fermer:
  if n_poly%<1 then return
  if (poly(0,0)<>poly(n_poly%-1,0)) or (poly(0,1)<>poly(n_poly%-1,1))
   n_poly% = n_poly% + 1
   poly(n_poly%-1,0) = poly(0,0)
   poly(n_poly%-1,1) = poly(0,1)
   2d_poly_to poly(0,0),poly(0,1)
  end_if
  return

chercher:
  2d_fill_color 255,0,0
  for coin%=0 to n_poly%-1
   PointSurMediane(coin%,0)
   PointInPolygon()
   if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
   else
   PointSurMediane(coin%,1)
   PointInPolygon()
   if result%=1
' 2d_circle pnt(0),pnt(1),3
   2d_flood pnt(0),pnt(1),255,0,0
   display
   end_if
   end_if
  next coin%
  return

sub PointInPolygon()
  result% = 0

  dim_local aDroite%, aGauche%
  dim_local np%, OpenPolygon%, XIntersection
  dim_local lg1%, lg2%

  aDroite% = 0
  aGauche% = 0
  OpenPolygon% = 1
  if n_poly%<3 then exit_sub

  ' test si le polygone est fermé
  if Poly(0,0)=Poly(n_poly%-1,0)
   if Poly(0,1)=Poly(n_poly%-1,1)
   OpenPolygon% = 0
   end_if
  end_if
  if OpenPolygon%=1 then exit_sub : ' impossible pour polygone non fermé

  ' tester chaque couple de points (faces) pour voir si la droite entre eux
  ' coupe l'horizontale passant par le point de test
  for np%=1 to n_poly%-1
   lg1% = 0
   lg2% = 0
   if (Poly(np%-1,1)<=pnt(1)) and (Poly(np%,1)>pnt(1)) then lg1% = 1
   if (Poly(np%-1,1)>pnt(1)) and (Poly(np%,1)<=pnt(1)) then lg2% = 1
   if (lg1%=1) or (lg2%=1)
   ' si tel est le cas
   ' calculer les coordonnées x de l'intersection
   XIntersection = Poly(np%-1,0) + ((Poly(np%,0)-Poly(np%-1,0)) / (Poly(np%,1)-Poly(np%-1,1))) * (pnt(1)-Poly(np%-1,1))

   ' adapter l'indicateur approprié
   if XIntersection<pnt(0) then aGauche% = 1 - aGauche%
   if XIntersection>pnt(0) then aDroite% = 1 - aDroite%
   end_if
  next np%
  if (aDroite%=1) and (aGauche%=1) then Result% = 1
end_sub

sub PointSurMediane(p%,act%)
  dim_local pm1%, pp1%, xm, ym, x, y, m, fact%
  fact% = 1
  if act%=1 then fact% = -1
  pm1% = p% - 1
  if pm1%<0 then pm1% = n_poly% -2
  pp1% = p% + 1
  if pp1%>=n_poly% then pp1% = 0

  xm = (poly(pm1%,0)-poly(pp1%,0))/2
  ym = (poly(pm1%,1)-poly(pp1%,1))/2
  x = poly(pp1%,0) + xm
  y = poly(pp1%,1) + ym
  m = 0 - (poly(p%,1)-y)/(poly(p%,0)-x)
  pnt(0) = poly(p%,0) + fact%*sgn(poly(p%,0)-x)*10
  pnt(1) = poly(p%,1) + fact%*sgn(poly(p%,1)-y)*abs(m)*10
end_sub

Voici un exemple:
Faire FLOOD dans un polygone non croisé Aa117

Dans le cas d'un polygone poly-croisé, ça veut dire quoi, être "à l'intérieur" du polygone ? Dans mon algorithme, je pars des coins du polygone. Une surface créée uniquement par l'intersection de côtés du polygone n'est pas détectable.

D'ailleurs, si l'on regarde attentivement le résultat ci-dessus, on constate que pour un point dans une des sections restées blanches, le nombre d'intersection de la droite horizontale passant par ce point avec les côtés du polygone est soit pair, soit pas du même nombre à droite et à gauche.

Maintenant, on pourrait imaginer la détection de chaque segment fermé et le colorer également. Cela passe par le calcul de tous les point d'intersection entre côtés du polygone, on les ajoute à la liste des points et on refait la détection. Mais c'est complexe et potentiellement long pour un polygone en peu plus grand et ploy-croisé.

Quel est l'intérêt de cela ? Veux-tu changer le sujet en "remplissage d'un polygone quelconque poly-croisé" ? Je pourrais y réfléchir...

Sujet: Re: Faire FLOOD dans un polygone non croisé Mer 23 Sep 2015 - 17:12

Voici une version qui ajoute un bouton "Sections". Cela permet de trouver toutes les intersections entre faces du polygone, et de les mémoriser séparément. Il faut donc:
1. tracer le polygone par des clics successifs dans la surface de dessin
2. fermer le polygone par le bouton "Fermer"
3. calculer les intersections par le bouton "Sections" (il y aura un message de confirmation)
4. faire le remplissage par le bouton "Chercher"

Les coins seront alors visualisés par un cercle noir et un chiffre 0,1,...
Les intersections seront alors visualisées par un cercle bleuet une lettre A,B,...

Code:: ' chercher_un_point_dans_un_polygone_poly_croise.bas

label nouveau_coin, effacer, fermer, chercher, sections

dim result%, i%
dim n_poly%, n_sect%
dim pnt(1),poly(200,1),sect(200,1)
dim coin%

' décrire le polygone
data 6 : ' nombre de points
data 200,130
data 160,40
data 100,20
data 120,80
data 10,60
data 200,130
' décrire le point
' data 140,50 : ' dedans
data 240,50 : ' dehors

picture 10 : full_space 10 : color 10,255,255,255
2d_target_is 10
print_target_is 10

if message_confirmation_yes_no("Sélection des coins par clic de souris ?")=1
on_click 10,nouveau_coin
button 1 : top 1,0 : left 1,0 : caption 1,"Effacer" : on_click 1,effacer
button 2 : top 2,25 : left 2,0 : caption 2,"Fermer" : on_click 2,fermer
button 3 : top 3,50 : left 3,0 : caption 3,"Chercher" : on_click 3,chercher
button 4 : top 4,75 : left 4,0 : caption 4,"Sections" : on_click 4,sections
end
end_if

read n_poly%
for i%=0 to n_poly%-1
read poly(i%,0)
read poly(i%,1)
next i%
read pnt(0)
read pnt(1)

2d_poly_from poly(0,0),poly(0,1)
for i%=1 to n_poly%-1
2d_poly_to poly(i%,0),poly(i%,1)
next i%
2d_circle pnt(0),pnt(1),3

PointInPolygon()
message str$(result%)

2d_pen_color 255,0,0
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
pnt(0) = poly(coin%,0) + 2
pnt(1) = poly(coin%,1) + 2
PointInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
' end
end_if
next coin%
' message "oups"
end

nouveau_coin:
n_poly% = n_poly% + 1
poly(n_poly%-1,0) = mouse_x_left_down(10)
poly(n_poly%-1,1) = mouse_y_left_down(10)
' 2d_circle poly(n_poly%-1,0),poly(n_poly%-1,1),3
if n_poly%=1
2d_poly_from poly(n_poly%-1,0),poly(n_poly%-1,1)
else
2d_poly_to poly(n_poly%-1,0),poly(n_poly%-1,1)
end_if
return

effacer:
color 10,255,255,255
n_poly% = 0
n_sect% = 0
return

fermer:
if n_poly%<1 then return
if (poly(0,0)<>poly(n_poly%-1,0)) or (poly(0,1)<>poly(n_poly%-1,1))
n_poly% = n_poly% + 1
poly(n_poly%-1,0) = poly(0,0)
poly(n_poly%-1,1) = poly(0,1)
2d_poly_to poly(0,0),poly(0,1)
end_if
return

chercher:
2d_fill_color 255,0,0
for coin%=0 to n_poly%-1
PointSurMediane(coin%,0)
PointInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
else
PointSurMediane(coin%,1)
PointInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
end_if
end_if
next coin%
2d_fill_color 0,0,0
for coin%=0 to n_poly%-2
2d_circle poly(coin%,0),poly(coin%,1),3
2d_fill_color 255,255,255
print_locate poly(coin%,0)+5,poly(coin%,1)
print str$(coin%)
2d_fill_color 0,0,0
next coin%
if n_sect%>0
2d_fill_color 0,0,255
for coin%=0 to n_sect%-1
2d_circle sect(coin%,0),sect(coin%,1),3
2d_fill_color 255,255,255
print_locate sect(coin%,0)+5,sect(coin%,1)
print chr$(coin%+65)
2d_fill_color 0,0,255
next coin%
end_if

if n_sect%>0
for coin%=0 to n_sect%-1
pnt(0) = sect(coin%,0)
pnt(1) = sect(coin%,1)
SectInPolygon()
if result%=1
' 2d_circle pnt(0),pnt(1),3
2d_flood pnt(0),pnt(1),255,0,0
display
end_if
next coin%
end_if

2d_fill_color 255,255,255

print_locate 200,height(10)-50
print "Coins: 0-"+str$(n_poly%-2)
if n_sect%>0
print_locate 200,height(10)-30
print "Sections: A-"+chr$(n_sect%+64)
end_if
return

sections:
' ajouter toutes les intersections de faces à la liste des coins du polygone
if n_sect%>0 then return
if n_poly%<4 then return
CalculerIntersections()
message str$(n_sect%)+" points de section ont été trouvés"
return

sub SectInPolygon()

end_sub

sub PointInPolygon()
result% = 0

dim_local aDroite%, aGauche%
dim_local np%, OpenPolygon%, XIntersection
dim_local lg1%, lg2%

aDroite% = 0
aGauche% = 0
OpenPolygon% = 1
if n_poly%<3 then exit_sub

' test si le polygone est fermé
if Poly(0,0)=Poly(n_poly%-1,0)
if Poly(0,1)=Poly(n_poly%-1,1)
OpenPolygon% = 0
end_if
end_if
if OpenPolygon%=1 then exit_sub : ' impossible pour polygone non fermé

' tester chaque couple de points (faces) pour voir si la droite entre eux
' coupe l'horizontale passant par le point de test
for np%=1 to n_poly%-1
lg1% = 0
lg2% = 0
if (Poly(np%-1,1)<=pnt(1)) and (Poly(np%,1)>pnt(1)) then lg1% = 1
if (Poly(np%-1,1)>pnt(1)) and (Poly(np%,1)<=pnt(1)) then lg2% = 1
if (lg1%=1) or (lg2%=1)
' si tel est le cas
' calculer les coordonnées x de l'intersection
XIntersection = Poly(np%-1,0) + ((Poly(np%,0)-Poly(np%-1,0)) / (Poly(np%,1)-Poly(np%-1,1))) * (pnt(1)-Poly(np%-1,1))

' adapter l'indicateur approprié
if XIntersection<pnt(0) then aGauche% = 1 - aGauche%
if XIntersection>pnt(0) then aDroite% = 1 - aDroite%
end_if
next np%
if (aDroite%=1) and (aGauche%=1) then Result% = 1
end_sub

sub PointSurMediane(p%,act%)
dim_local pm1%, pp1%, xm, ym, x, y, m, fact%
fact% = 1
if act%=1 then fact% = -1
pm1% = p% - 1
if pm1%<0 then pm1% = n_poly% -2
pp1% = p% + 1
if pp1%>=n_poly% then pp1% = 0

xm = (poly(pm1%,0)-poly(pp1%,0))/2
ym = (poly(pm1%,1)-poly(pp1%,1))/2
x = poly(pp1%,0) + xm
y = poly(pp1%,1) + ym
m = 0 - (poly(p%,1)-y)/(poly(p%,0)-x)
pnt(0) = poly(p%,0) + fact%*sgn(poly(p%,0)-x)*10
pnt(1) = poly(p%,1) + fact%*sgn(poly(p%,1)-y)*abs(m)*10
end_sub

sub CalculerIntersections()
dim_local n_face%, max_face%, i%, j%
max_face% = n_poly% - 1
for i%=1 to max_face%-1
for j%=i%+1 to max_face%
CalculerIntersection(i%,j%)
next j%
next i%
end_sub

sub CalculerIntersection(ip%,jp%)
' PROCEDURE GetIntersectionPB(
dim_local x1, y1, x2, y2, x3, y3, x4, y4
dim_local ix, iy
dim_local S1,S2,S3,S4,S5,S6,S7,Ua,Ub,M1,M2

x1 = poly(ip%-1,0)
y1 = poly(ip%-1,1)
x2 = poly(ip%,0)
y2 = poly(ip%,1)

x3 = poly(jp%-1,0)
y3 = poly(jp%-1,1)
x4 = poly(jp%,0)
y4 = poly(jp%,1)

S1 = x4 - x3
S2 = x2 - x1
S5 = y2 - y1
S6 = y4 - y3

M1 = S1 * S5
M2 = S6 * S2

if M1 <> M2 : ' Si les lignes ne sont pas parallèles

S3 = y1 - y3
S4 = x1 - x3
S7 = M2 - M1

Ua = ( S1 * S3 - S6 * S4 ) / S7
Ub = ( S2 * S3 - S5 * S4 ) / S7

if Ua > 0
if Ua < 1
if Ub > 0
if Ub < 1
ix = x1 + Ua * S2
iy = y1 + Ua * S5
n_sect% = n_sect% + 1
sect(n_sect%-1,0) = ix
sect(n_sect%-1,1) = iy
end_if
end_if
end_if
end_if

end_if

end_sub

A partir de là, je cherche un moyen d'identifier le segment non coloré pour y injecter une couleur...

» Tester si un point est dans un polygone
» Faire apparaitre fichier$ dans SAVE_DIALOG
» Faire apparaître PAnoramic_Editor dans la barre des tâches
» Faire des marques lignes dans l'éditeur (signets)
» Faire un trou complexe dans un objet FORM