FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC

Développement d'applications avec le langage Panoramic
 
AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  GroupesGroupes  Connexion  
Derniers sujets
» KGF_dll - nouvelles versions
par Yannick Aujourd'hui à 21:30

» Synedit Parameters
par Yannick Aujourd'hui à 21:26

» Un bug avec USER_EVENT ?
par Yannick Aujourd'hui à 21:16

» Concours de Morpions
par Froggy One Aujourd'hui à 17:30

» Bienvenue à Irikte
par papydall Aujourd'hui à 14:59

» Comment changer le graphisme d’un menu
par Yannick Aujourd'hui à 12:53

» LIBRARY COMMAND FUNCTION
par Jean Claude Aujourd'hui à 11:38

» OBJECT_PARENT NE FONCTIONNE PLUS ?! (RESOLU)
par Jack Aujourd'hui à 10:40

» Menu personalisé avec icones et menu contextuel
par Yannick Aujourd'hui à 10:10

» Doublon - Désolé !
par Laurent (Minibug) Aujourd'hui à 9:55

» Mac OS X sierra
par Irikte Aujourd'hui à 8:01

» Recherche de traductions de mots (@Klaus).
par Pedro Alvarez Hier à 18:34

» Problème avec SendStringAsText.
par Pedro Alvarez Hier à 18:32

» Version instantanée V 0.9.28i10 du 24/06/2017
par Yannick Hier à 16:19

» Mais qui a le focus ?
par Jack Hier à 14:35

Navigation
 Portail
 Index
 Membres
 Profil
 FAQ
 Rechercher
Rechercher
 
 

Résultats par :
 
Rechercher Recherche avancée
Juin 2017
LunMarMerJeuVenSamDim
   1234
567891011
12131415161718
19202122232425
2627282930  
CalendrierCalendrier

Partagez | 
 

 Faire FLOOD dans un polygone non croisé

Voir le sujet précédent Voir le sujet suivant Aller en bas 
Aller à la page : 1, 2  Suivant
AuteurMessage
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Faire FLOOD dans un polygone non croisé   Dim 20 Sep 2015 - 3: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 ============================================================================
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
Laurent (Minibug)

avatar

Nombre de messages : 2351
Age : 50
Localisation : Vienne (86)
Date d'inscription : 09/02/2012

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Dim 20 Sep 2015 - 6: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 !
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Jicehel

avatar

Nombre de messages : 5838
Age : 44
Localisation : 77500
Date d'inscription : 18/04/2011

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Dim 20 Sep 2015 - 9: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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Jean Claude

avatar

Nombre de messages : 4953
Age : 63
Localisation : 83 Var
Date d'inscription : 07/05/2009

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

C'est un sujet intéressant, qui mérite un article. Very Happy
Le travail est déjà pratiquement fait.

A+

Revenir en haut Aller en bas
Voir le profil de l'utilisateur
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Dim 20 Sep 2015 - 12: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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
jean_debord

avatar

Nombre de messages : 725
Age : 62
Localisation : Limoges
Date d'inscription : 21/09/2008

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

Le centre de gravité n'est pas toujours à l'intérieur du polygone. Essayez avec x(4) = 200
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://www.unilim.fr/pages_perso/jean.debord/index.htm
Jicehel

avatar

Nombre de messages : 5838
Age : 44
Localisation : 77500
Date d'inscription : 18/04/2011

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Lun 21 Sep 2015 - 9: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 ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Lun 21 Sep 2015 - 12: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).
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
Jicehel

avatar

Nombre de messages : 5838
Age : 44
Localisation : 77500
Date d'inscription : 18/04/2011

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

Klaus: C'est ce que j'ai essayé d'expliquer, mais ta version est certainement plus claire Wink
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Lun 21 Sep 2015 - 13: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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Lun 21 Sep 2015 - 14: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...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mar 22 Sep 2015 - 0:12

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...


Dernière édition par Klaus le Mar 22 Sep 2015 - 12:02, édité 1 fois
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mar 22 Sep 2015 - 1: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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mar 22 Sep 2015 - 1: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...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

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

Bon courage à toi également.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
Laurent (Minibug)

avatar

Nombre de messages : 2351
Age : 50
Localisation : Vienne (86)
Date d'inscription : 09/02/2012

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mar 22 Sep 2015 - 6: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

Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mar 22 Sep 2015 - 12: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:


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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
jean_debord

avatar

Nombre de messages : 725
Age : 62
Localisation : Limoges
Date d'inscription : 21/09/2008

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 8: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 ?
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://www.unilim.fr/pages_perso/jean.debord/index.htm
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 8: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%.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 12: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
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 12: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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
papydall

avatar

Nombre de messages : 5387
Age : 66
Localisation : Moknine (Tunisie) Entre la chaise et le clavier
Date d'inscription : 03/03/2012

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

Merci Klaus.

Ça permet, tout de même de faire des bonnes choses avec ce code.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://papydall-panoramic.forumarabia.com/ En ligne
Jicehel

avatar

Nombre de messages : 5838
Age : 44
Localisation : 77500
Date d'inscription : 18/04/2011

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 12: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.
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 13: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:


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...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
Klaus

avatar

Nombre de messages : 9998
Age : 68
Localisation : Ile de France
Date d'inscription : 29/12/2009

MessageSujet: Re: Faire FLOOD dans un polygone non croisé   Mer 23 Sep 2015 - 16: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...
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://klauspanoramic.comxa.com/index.html En ligne
Contenu sponsorisé




MessageSujet: Re: Faire FLOOD dans un polygone non croisé   

Revenir en haut Aller en bas
 
Faire FLOOD dans un polygone non croisé
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 2Aller à la page : 1, 2  Suivant
 Sujets similaires
-
» liens inactifs dans ma boite de messagerie
» Balises pour faire clignoter du texte
» [Résolu] MsConfig
» Action répétés sous Photoshop
» [Tutoriel] Le Multijoueur sous GameMaker expliqué

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
FORUM DE DISCUSSION SUR LE LANGAGE PANORAMIC :: PANORAMIC 32 bits :: Vos sources, vos utilitaires à partager-
Sauter vers: