Tester un point dans un polygone

Question

Juste pour savoir si quelqu'un à une meilleure idée que moi, ce dont je ne doute pas que ça puisse arriver...

J'ai un polygone, et un point qui se balade. Comment je fait pour savoir si ce point se trouve à l'intérieur du polygone (dont je connais les coordonnées des sommets). On supposera également, qu'aucune arête du polygone croise une autre de ses arêtes.

us_30 · Accepted Answer

Bonsoir,

Je me permet de citer mon modeste site, http://fordom.free.fr/ où tu trouveras la fonction InRegion qui répondra à ceux qui tu cherches en VBA sous Excel, à adapter sous VB.NET. (pas difficile)

Cette fonction fut en son temps présentée à la critique sur VBF.

L'idée est identique à ce que tu expliques : "la méthode de compter le nombre de fois que l'on croise une arête du polygone" mais en plus raffiné.

Amicalement,
Us.

nhervagault · Answer

Bonjour à toi?

Peux-tu mettre le code et la création c'est poloygone.

Regardes les algorithme de collision.

Regardes la fonction hittest

cs_pingouin84k · Answer

Bah je vais peut être pas mettre l'algorithme parce qu'on va rien y comprendre.

Mon idée en fait, puisque j'ai à faire à des polygones simples et de calculer l'aire de chaque triangle formé par le centre de gravité du polygone et une des arêtes de celui-ci. Ensuite si mon point baladeur est dans l'un de ces triangles "élémentaires" alors l'aire du triangle est égale à la somme des trois petits triangle formé par le point baladeur et chacun des côtés du triangle élémentaire. Par contre si le point baladeur est à l'extérieur alors la somme des aires des petits triangles est plus grande que l'aire du triangle élémentaire.

Cette méthode marche bien pour des polygones qui ne sont pas en forme d'étoile (ça marche tant que le centre de gravité est à l'intérieur du polygone et que tous les triangles élémentaires forment bien le polygone décomposé).
Par contre je ne sais pas si cette méthode est la plus optimisée.


Je connais également la méthode de compter le nombre de fois que l'on croise une arête du polygone en partant d'un point dont on est sur qu'il est à l'extérieur.


Donc s'il y a quelqu'un qui à une idée qui serait susceptible d'être plus performante (ou même moins performante), je suis preneur au moins par curiosité mathématique

nhervagault · Answer

Avec de la trianglaution.

CF
http://www.vbfrance.com/codes/TRIANGULATION-2D-GERE-SURFACES-PLUS-COMPLEX_42528.aspx
et http://www.vbfrance.com/codes/TRIANGULATION-2D_18%20439.aspx

J'ai pas compris ton explication.

ezzoubaihi · Answer

une idée tres simple 
considérons une demi-droite qui a pour origine  le point considéré.
si la demi-droite intersecte le plygone en un nombre paire (le zero aussi) de points ,donc le point est en dehors du plygone.
si la demi-droite intersecte le plygone en un nombre impaire de points ,donc le point est en dehors du plygone.
essaie cette solution.
a+

ezzoubaihi · Answer

correction
une idée tres simple 
considérons une demi-droite qui a pour origine le point considéré. 
si la demi-droite intersecte le plygone en un nombre paire (le zero aussi) de points ,donc le point est en dehors du plygone. 
si la demi-droite intersecte le plygone en un nombre impaire de points ,donc le point est à l'intérieur du plygone. 
essaie cette solution. 
a+

jmf0 · Answer

Bonjour, ezzoubaihi

Bonne mais incomplète pensée....

us_30 · Answer

Je rajoute que la démonstration mathématique du nb de croisement est si délicate, que le mathématicien - J. Hadamar il me semble - qui a voulu le démontrer, a utilisé au moins 100 pages... Bon courage ! ... Donc bon, si la pensée de ezzoubaihi est intuitivement correcte, pour ma part, je m'en contente... 

Amicalement,
Us.

ezzoubaihi · Answer

bonjour les amis 
A mon avis c'est la solution la plus simple et la plus faisable .
essayez de la tester .
Mr jmf0 si vous pouvez expliquer davantage a quoi consiste les défaillances de la solution proposée.
Merci.
A+

jmf0 · Answer

Tout simplement : cas particulier d'une demi-droite passant par l'un des sommets ou point sur l'un des sommets

us_30 · Answer

Oui, mais facilement gérable... (faire un ou des tests au debut de l'algo). Soit re-dit en passant, ma modeste petite fonction InRegion sur mon site, gère cela sans problème... Ouais, c'est un peu de PUB aussi, mais bon, comme j'avais déjà traité complètement ce problème... 

Amicalement,
Us.

Freuleu · Answer

Pour info, j ai un message d erreur lorsque je commence à sélectionner la deuxième matrice (MatriceY), comme quoi il y a une erreur dans la formule... Faut-il modifier le code?

ucfoutu · Answer

De quelle "deuxième matrice" parles-tu ?
 Vas-tu te décider à ouvrir (bis repetita) ta propre discussion en en précisant :
- tous les tenants et aboutissants
- le code que tu as écrit
????

Rykudos · Answer

bonjour, j’interviens un peut tardivement mais je chercher mois aussi a savoir comment déterminer si un point était dans un polygone (quadrilatère dans mon cas), ne trouvant pas de solution j'ai développer un petit algorithme qui fonctionne comme suit:  

Pour exemple un polygone ayant 4 sommet b,a,d,c et un point p,
l'algorithme mesure la longueur de chaque arrête du polygone a partir de ses 4 sommet(ba, ad, dc, cb) puis les 4 segment reliant le point p au 4 sommet(pb, pa, pd, pc) ce qui forme 4 triangle de sommet p (bpa, apd, dpc, cpb). il mesure ensuite l'angle p de chaque triangle, si la somme de ses 4 angle = 360° le point p est dans le polygone.    

 Function test(PointX, PointY, Sommet1X, Sommet1Y, Sommet2X, Sommet2Y, Sommet3X, Sommet3Y, Sommet4X, Sommet4Y)        'angA        Dim pb = Math.Sqrt(((PointX - Sommet1X) * (PointX - Sommet1X)) + ((PointY - Sommet1Y) * (PointY - Sommet1Y)))        Dim pa = Math.Sqrt(((PointX - Sommet2X) * (PointX - Sommet2X)) + ((PointY - Sommet2Y) * (PointY - Sommet2Y)))        Dim ba = Math.Sqrt(((Sommet1X - Sommet2X) * (Sommet1X - Sommet2X)) + ((Sommet1Y - Sommet2Y) * (Sommet1Y - Sommet2Y)))        Dim radA = Math.Acos(((pa * pa) + (pb * pb) - (ba * ba)) / (2 * pa * pb))        Dim angA = radA * (180 / Math.PI)        'angB        pa = Math.Sqrt(((PointX - Sommet2X) * (PointX - Sommet2X)) + ((PointY - Sommet2Y) * (PointY - Sommet2Y)))        Dim pd = Math.Sqrt(((PointX - Sommet3X) * (PointX - Sommet3X)) + ((PointY - Sommet3Y) * (PointY - Sommet3Y)))        Dim ad = Math.Sqrt(((Sommet2X - Sommet3X) * (Sommet2X - Sommet3X)) + ((Sommet2Y - Sommet3Y) * (Sommet2Y - Sommet3Y)))        Dim radB = Math.Acos(((pa * pa) + (pd * pd) - (ad * ad)) / (2 * pa * pd))        Dim angB = radB * (180 / Math.PI)        'angC        pd = Math.Sqrt(((PointX - Sommet3X) * (PointX - Sommet3X)) + ((PointY - Sommet3Y) * (PointY - Sommet3Y)))        Dim pc = Math.Sqrt(((PointX - Sommet4X) * (PointX - Sommet4X)) + ((PointY - Sommet4Y) * (PointY - Sommet4Y)))        Dim dc = Math.Sqrt(((Sommet3X - Sommet4X) * (Sommet3X - Sommet4X)) + ((Sommet3Y - Sommet4Y) * (Sommet3Y - Sommet4Y)))        Dim radC = Math.Acos(((pc * pc) + (pd * pd) - (dc * dc)) / (2 * pc * pd))        Dim angC = radC * (180 / Math.PI)        'angD        pc = Math.Sqrt(((PointX - Sommet4X) * (PointX - Sommet4X)) + ((PointY - Sommet4Y) * (PointY - Sommet4Y)))        pb = Math.Sqrt(((PointX - Sommet1X) * (PointX - Sommet1X)) + ((PointY - Sommet1Y) * (PointY - Sommet1Y)))        Dim cb = Math.Sqrt(((Sommet4X - Sommet1X) * (Sommet4X - Sommet1X)) + ((Sommet4Y - Sommet1Y) * (Sommet4Y - Sommet1Y)))        Dim radD = Math.Acos(((pc * pc) + (pb * pb) - (cb * cb)) / (2 * pc * pb))        Dim angD = radD * (180 / Math.PI)        If angA + angB + angC + angD = 360 Then            Return True        Else : Return False        End If    End Function

ucfoutu · Answer

Bonjour,
on déterre une vieille discussion !
Je vais prendre le relais de mon frère jumeau jmf0, qui avait à l'époque préféré laisser courir ...

 1) cs_pingouin84k (le demandeur) a précisé :
 ...du polygone (dont je connais les coordonnées des sommets)....
l'utilisation de la fonction CreatePolyPolygonRgn de la librairie gdi32 de l'Api de Windows permet donc d'en déterminer la région. 
2) l'utilisation de la fonction PtInRegion de la même librairie permet de déterminer si un point dont on spécifie les coordonnées est ou non dans une région
Voilà tout.
________________________
Nul ne saurait valablement coder ce qu'il ne saurait exposer clairement.

Tester un point dans un polygone

15 réponses

Votre réponse

Discussions similaires