Tester un point dans un polygone

Signaler
Messages postés
68
Date d'inscription
vendredi 28 octobre 2005
Statut
Membre
Dernière intervention
9 janvier 2011
-
 tiri64 -
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.
A voir également:

15 réponses

Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
8
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.
Super ca marche merci ! Et super bibliothèque !
Messages postés
6063
Date d'inscription
dimanche 13 avril 2003
Statut
Modérateur
Dernière intervention
15 juillet 2011
26
Bonjour à toi?

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

Regardes les algorithme de collision.

Regardes la fonction hittest
Messages postés
68
Date d'inscription
vendredi 28 octobre 2005
Statut
Membre
Dernière intervention
9 janvier 2011

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
Messages postés
6063
Date d'inscription
dimanche 13 avril 2003
Statut
Modérateur
Dernière intervention
15 juillet 2011
26
Messages postés
7
Date d'inscription
lundi 27 juillet 2009
Statut
Membre
Dernière intervention
26 septembre 2009

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+
Messages postés
7
Date d'inscription
lundi 27 juillet 2009
Statut
Membre
Dernière intervention
26 septembre 2009

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+
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Statut
Membre
Dernière intervention
5 avril 2013
4
Bonjour, ezzoubaihi

Bonne mais incomplète pensée....
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
8
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.
Messages postés
7
Date d'inscription
lundi 27 juillet 2009
Statut
Membre
Dernière intervention
26 septembre 2009

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+
Messages postés
1566
Date d'inscription
mardi 26 décembre 2000
Statut
Membre
Dernière intervention
5 avril 2013
4
Tout simplement : cas particulier d'une demi-droite passant par l'un des sommets ou point sur l'un des sommets
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
8
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.
Messages postés
10
Date d'inscription
jeudi 9 avril 2015
Statut
Membre
Dernière intervention
14 avril 2015

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?
Messages postés
18038
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
225
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
????
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
Messages postés
416
Date d'inscription
vendredi 22 février 2008
Statut
Membre
Dernière intervention
7 janvier 2018
1
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
Messages postés
18038
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
225 >
Messages postés
416
Date d'inscription
vendredi 22 février 2008
Statut
Membre
Dernière intervention
7 janvier 2018

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
>
Messages postés
416
Date d'inscription
vendredi 22 février 2008
Statut
Membre
Dernière intervention
7 janvier 2018

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 ^^.
Messages postés
416
Date d'inscription
vendredi 22 février 2008
Statut
Membre
Dernière intervention
7 janvier 2018
1
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
Messages postés
18038
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
225 >
Messages postés
416
Date d'inscription
vendredi 22 février 2008
Statut
Membre
Dernière intervention
7 janvier 2018

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.
Messages postés
18038
Date d'inscription
lundi 7 décembre 2009
Statut
Modérateur
Dernière intervention
11 avril 2018
225
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.