Tester un point dans un polygone

cs_pingouin84k 68 Messages postés vendredi 28 octobre 2005Date d'inscription 9 janvier 2011 Dernière intervention - 19 juil. 2009 à 11:45 - Dernière réponse :  Rykudos
- 24 janv. 2016 à 11:22
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.
Afficher la suite 

Votre réponse

20 réponses

nhervagault 6069 Messages postés dimanche 13 avril 2003Date d'inscription 15 juillet 2011 Dernière intervention - 19 juil. 2009 à 14:06
0
Merci
Bonjour à toi?

Peux-tu mettre le code et la création c'est poloygone.

Regardes les algorithme de collision.

Regardes la fonction hittest
Commenter la réponse de nhervagault
cs_pingouin84k 68 Messages postés vendredi 28 octobre 2005Date d'inscription 9 janvier 2011 Dernière intervention - 19 juil. 2009 à 20:13
0
Merci
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
Commenter la réponse de cs_pingouin84k
nhervagault 6069 Messages postés dimanche 13 avril 2003Date d'inscription 15 juillet 2011 Dernière intervention - 19 juil. 2009 à 22:00
Commenter la réponse de nhervagault
us_30 2117 Messages postés lundi 11 avril 2005Date d'inscription 14 mars 2016 Dernière intervention - 20 juil. 2009 à 22:24
0
Merci
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.
Commenter la réponse de us_30
ezzoubaihi 7 Messages postés lundi 27 juillet 2009Date d'inscription 26 septembre 2009 Dernière intervention - 27 sept. 2009 à 23:36
0
Merci
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+
Commenter la réponse de ezzoubaihi
ezzoubaihi 7 Messages postés lundi 27 juillet 2009Date d'inscription 26 septembre 2009 Dernière intervention - 27 sept. 2009 à 23:38
0
Merci
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+
Commenter la réponse de ezzoubaihi
jmf0 1566 Messages postés mardi 26 décembre 2000Date d'inscription 5 avril 2013 Dernière intervention - 28 sept. 2009 à 08:08
0
Merci
Bonjour, ezzoubaihi

Bonne mais incomplète pensée....
Commenter la réponse de jmf0
us_30 2117 Messages postés lundi 11 avril 2005Date d'inscription 14 mars 2016 Dernière intervention - 28 sept. 2009 à 18:24
0
Merci
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.
Commenter la réponse de us_30
ezzoubaihi 7 Messages postés lundi 27 juillet 2009Date d'inscription 26 septembre 2009 Dernière intervention - 28 sept. 2009 à 22:37
0
Merci
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+
Commenter la réponse de ezzoubaihi
jmf0 1566 Messages postés mardi 26 décembre 2000Date d'inscription 5 avril 2013 Dernière intervention - 29 sept. 2009 à 09:02
0
Merci
Tout simplement : cas particulier d'une demi-droite passant par l'un des sommets ou point sur l'un des sommets
Commenter la réponse de jmf0
us_30 2117 Messages postés lundi 11 avril 2005Date d'inscription 14 mars 2016 Dernière intervention - 29 sept. 2009 à 12:42
0
Merci
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.
Commenter la réponse de us_30
Freuleu 10 Messages postés jeudi 9 avril 2015Date d'inscription 14 avril 2015 Dernière intervention - 9 avril 2015 à 14:01
0
Merci
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?
Commenter la réponse de Freuleu
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionModérateurStatut 11 avril 2018 Dernière intervention - 9 avril 2015 à 18:51
0
Merci
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
????
Commenter la réponse de ucfoutu
0
Merci
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
CGSI3 417 Messages postés vendredi 22 février 2008Date d'inscription 7 janvier 2018 Dernière intervention - 24 janv. 2016 à 00:10
Bonjour a tous,

Je vais faire par ordre pour ceux qui veulent quand même essayer de refaire la roue et qui adore se torturer les meninges ... (Pour un Quadrilatère)


1, Vérifier que le quadrilatère est non croisé

Si ce n'est pas le cas, il convient de trouver le point d'intersection des 2 segments de coté qui se croisent et ainsi trouver les 2 triangles formant la surface du quadrilatère ( Attention aux cas particuliers )

2, Nous obtenons dans de nombreux cas une division de 2 triangles sur lequel on peut vérifier si le point a tester est a l’intérieur de l'un ces 2 triangles.

3, Calculer l'air d'un triangle ...

La formule la plus simple a ma connaissance est la suivante:
http://villemin.gerard.free.fr/GeomLAV/Triangle/Types/Quelconq.htm

L'astuce ce situe dans les dernières formules possibles qui permet
d'aboutir a cette simplification :

Pour trois points A B C formant un triangle

Dim SignSurface As Double = 0.5 * ( A.X * (B.Y - C.Y) - B.X * (A.Y - C.Y) - C.X * (B.Y - A.Y) )
( je fais remarquer que vous ne distinguez aucune division, racine carré ou fonctions trigonométriques )

On obtient ainsi 2 informations essentiels:
- Un chiffre soit positif, soit négatif, ceci en fonction du sens Horaire ou Anti Horaire que forment les 3 points.
- La valeur absolue du chiffre étant la surface du triangle.

Si on nomme Z le point a tester, il ne te reste plus qu'a tester que l'aire de chaque triangle ABZ , BCZ et CAZ soient de même signe pour en conclure que le point Z est, soit a l’intérieur, ou soit a l’extérieur du triangle ABC

Je vous laisse optimiser tout cela car il existe quelques astuces supplémentaires

Bonne Prog
CGSI3
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionModérateurStatut 11 avril 2018 Dernière intervention > CGSI3 417 Messages postés vendredi 22 février 2008Date d'inscription 7 janvier 2018 Dernière intervention - 24 janv. 2016 à 07:49
Je ne vois nulle part, dans la demande faite, que le polygone à traiter est limité à un quadrilatère.
La demande concerne un polygone. Elle ne limite ni le nombre de ses sommets, ni le caractère (convexe ou concave) du polygone
Rykudos > CGSI3 417 Messages postés vendredi 22 février 2008Date d'inscription 7 janvier 2018 Dernière intervention - 24 janv. 2016 à 11:22
bonjour,
merci cgsi3 pour ta solution je vais y jetais un œil, histoire de me "torturer les meninges" =), j'ai rejoins la discussion car je chercher aussi comment procéder. Ayant trouver une solution (a adapter au nombre de sommet mais le principe reste le même) et voyant que le post n'était pas marquer comme résolut je me suis permit d'apporter mon petit grains de sel ^^.
CGSI3 417 Messages postés vendredi 22 février 2008Date d'inscription 7 janvier 2018 Dernière intervention - 24 janv. 2016 à 08:47
Rykudos :je chercher mois aussi a savoir comment déterminer si un point était dans un polygone (quadrilatère dans mon cas)
Function test(PointX, PointY, Sommet1X, Sommet1Y, Sommet2X, Sommet2Y, Sommet3X, Sommet3Y, Sommet4X, Sommet4Y)

Le quadrilatère fait bien parti de cette famille qu'est le polygone.

Je sais pas .. a voir avec Rykudos si l'on doit lui répondre, ou refaire un post

Post similaire : http://codes-sources.commentcamarche.net/forum/affich-10047416-tester-un-point-dans-un-polygone-vba#p10047606
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionModérateurStatut 11 avril 2018 Dernière intervention > CGSI3 417 Messages postés vendredi 22 février 2008Date d'inscription 7 janvier 2018 Dernière intervention - 24 janv. 2016 à 10:41
Bonjour, CGSI3,
Le lien que tu as donné est déjà sa réponse.

Pour ce qui est d'une autre approche (géométrique, celle-là) :
Il me semble que x étant le point dont on veut savoir s'il est ou non à l'intérieur d'un polygone de sommets connus (S1,S2,S3 ...Sn)
x est à l'intérieur si la somme des distances entre x et S1, x et S2, ... x et SN est plus petite que celle de la somme des distances entre l'un quelconque des sommets et chacun des autres sommets.
Il est à l'extérieur dans le cas contraire.
Commenter la réponse de Rykudos
ucfoutu 18039 Messages postés lundi 7 décembre 2009Date d'inscriptionModérateurStatut 11 avril 2018 Dernière intervention - Modifié par ucfoutu le 23/01/2016 à 17:20
0
Merci
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.
Commenter la réponse de ucfoutu

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.