Nous utilisons des cookies pour vous garantir la meilleure expérience sur notre site. Si vous continuez à utiliser ce dernier, nous considèrerons que vous acceptez l'utilisation des cookies. J'ai compris ! ou En savoir plus !.
banniere

Le portail francophone de la géomatique


Toujours pas inscrit ? Mot de passe oublié ?
Nom d'utilisateur    Mot de passe              Toujours pas inscrit ?   Mot de passe oublié ?

Annonce

Printemps des cartes 2024

Pages: 1

 

#1 Thu 03 October 2019 12:35

preliator
Participant assidu
Date d'inscription: 17 Nov 2018
Messages: 433

Points dans polygone

Bonjour à tous,

Admettons une couche de points "Sommet_polygones" représentant tous les sommets d'un polygone fermé, et une couche points "Maison" possédant des points à l'intérieur et à l'extérieur de l'emprise "Sommet_polygone". Ces deux couches ont, dans leur champ, la coordonnée en lat et long sur le
SCR WGS 84.

Quelle formule mathématique me permettrait de trouver les points situés dans l'emprise de "Sommet_polygone" ? Je ne souhaite pas utiliser de fonctions sur QGis ou autre, juste comprendre comment cela fonctionne sur le papier.

Image pour illustrer ma question : http://zupimages.net/viewer.php?id=19/40/9q77.png

Merci à vous.

Hors ligne

 

#2 Thu 03 October 2019 14:16

tevrard
Participant assidu
Date d'inscription: 23 May 2016
Messages: 319

Re: Points dans polygone

https://en.wikipedia.org/wiki/Point_in_polygon


Tu traces une demi droite tu comptes le nombre de fois que tu traverses (crosses) le périmètre du polygone : pair, le point est en dehors, impair, le point est à l'intérieur

Hors ligne

 

#3 Thu 03 October 2019 15:04

ChristopheV
Membre
Lieu: Ajaccio
Date d'inscription: 7 Sep 2005
Messages: 3169
Site web

Re: Points dans polygone

Bonjour

Autre méthode, transformer les arêtes du polygone en arc orienté, par exemple sens horaire, puis une fonction booléenne EstAGauchede()
Si pour chaque arête la fonction conserve la même valeur alors le point est à l'intérieur.

Christophe
L'avantage d'être une île c'est d'être une terre topologiquement close

Hors ligne

 

#4 Thu 03 October 2019 15:36

tevrard
Participant assidu
Date d'inscription: 23 May 2016
Messages: 319

Re: Points dans polygone

ChristopheV a écrit:

Bonjour

Autre méthode, transformer les arêtes du polygone en arc orienté, par exemple sens horaire, puis une fonction booléenne EstAGauchede()
Si pour chaque arête la fonction conserve la même valeur alors le point est à l'intérieur.


J'ai l'impression qu'il y a des cas particuliers pour lesquels cette méthode ne fonctionne pas.

Du genre un polygone en forme de "M", si le point est dans un pied

Dernière modification par tevrard (Thu 03 October 2019 15:36)

Hors ligne

 

#5 Thu 03 October 2019 17:28

preliator
Participant assidu
Date d'inscription: 17 Nov 2018
Messages: 433

Re: Points dans polygone

Merci à vous tous pour ces réponses. Existe t-il une façon de résoudre ce problème en faisant un calcul avec les coordonnées des ces points ?
Merci

Hors ligne

 

#6 Thu 03 October 2019 17:43

p.jeremie
Participant assidu
Lieu: Valence
Date d'inscription: 10 Sep 2017
Messages: 380

Re: Points dans polygone

Je suis curieux, comment définis-tu "emprise Sommet_polygones"?

Hors ligne

 

#7 Thu 03 October 2019 17:48

preliator
Participant assidu
Date d'inscription: 17 Nov 2018
Messages: 433

Re: Points dans polygone

Peut être que ma formulation n'est pas la bonne ^^'

En considérant un polygone dont j'ai extrais tous ses sommets sous forme de points (comme l'image que j'ai posté plus haut), j'appelle "emprise Sommet_polygones" la surface à l'intérieur de ces points, qui représenterais l'aire du polygone si ces points étaient reliés par des lignes smile

Hors ligne

 

#8 Thu 03 October 2019 18:17

Yves Egels
Participant assidu
Lieu: Paris
Date d'inscription: 29 Sep 2011
Messages: 252
Site web

Re: Points dans polygone

La méthode proposée par Tevrard fonctionne parfaitement et peut être bien optimisée :

On considère les intersections des côtés avec une droite horizontale passant par M (x,y)
Pour chaque côté P1 P2, si y est entre y1 et y2 il y a intersection : on calcule l'abscisse de l'intersection. Si elle est supérieur à X elle compte. Si à la fin le nombre est impair, le point est intérieur. Pour traiter les cas où le point est sur l'horizontale d'un sommet, qui ne doit pas être compté deux fois, il est préférable d'avoir un polygone orienté (peu importe le sens, il faut que tous les arcs soient dans le même sens) l'intersection compte si elle est au premier sommet, pas au second.
en Pascal, ça donne :

Code:

   function PointInPolygon(x, y : Single) : Boolean;
   // The code below is from Wm. Randolph Franklin <wrf@ecse.rpi.edu>
   // with some minor modifications for speed.  It returns 1 for strictly
   // interior points, 0 for strictly exterior, and 0 or 1 for points on
   // the boundary.
   var
      I, J: Integer;
   begin
      Result:=False;
     for I:=0 to pred(High(Poly)) do begin
         j := succ(i);
         if ((((Poly[i].Y<=Y) and (Y<Poly[J].Y)) or
              ((Poly[J].Y<=Y) and (Y<Poly[i].Y))) and
            (X<(Poly[J].X-Poly[i].X)*(Y-Poly[i].Y)/(Poly[J].Y-Poly[i].Y)+Poly[i].X)) then
            Result:=not Result;
      end;
   end;

Dernière modification par Yves Egels (Thu 03 October 2019 18:20)

Ingénieur géographe honoraire
École nationale des sciences géographiques
Société française de photogrammétrie et télédétection

Hors ligne

 

#9 Fri 04 October 2019 10:33

ChristopheV
Membre
Lieu: Ajaccio
Date d'inscription: 7 Sep 2005
Messages: 3169
Site web

Re: Points dans polygone

Bonjour,

@tevrard : si si ça marche, nous l'utilisons dans certains codes. Après je n'ai pas évoqué le cas des polygones à trous, mais si à l'intérieur de l'anneau extérieur et à l'extérieure du trou ça marche, juste une étape de plus.
Bon on parle de polygones "standard" (pas de papillon par exemple).

Les deux méthodes, celle décrite par Y. Egels, Tevrad et la mienne sont très bien explicitée dans l'ouvrage https://www.dunod.com/sciences-techniqu … imation-3d

Christophe
L'avantage d'être une île c'est d'être une terre topologiquement close

Hors ligne

 

#10 Fri 04 October 2019 10:38

preliator
Participant assidu
Date d'inscription: 17 Nov 2018
Messages: 433

Re: Points dans polygone

Merci a vous

Hors ligne

 

#11 Fri 04 October 2019 10:58

Yves Egels
Participant assidu
Lieu: Paris
Date d'inscription: 29 Sep 2011
Messages: 252
Site web

Re: Points dans polygone

La méthode "est_toujours_du_même_côté" est équivalente au test du signe du produit vectoriel P1M vect P1P2. Je suis d'accord avec Tevrard, ça ne marche que si le polygone est convexe.

Dans le cas précis évoqué ici, il manque une étape : passer des sommets au polygone. Un ensemble de points ne définit pas un polygone unique. Je suppose qu'il s'agit d l'enveloppe convexe (à construire? ) Du coup le polygone est très probablement orienté. Dans ce cas il n'y a que deux intersections au maximum... et pas de trou. On peut arrêter l'algo à la détection de la seconde intersection.

Dernière modification par Yves Egels (Fri 04 October 2019 11:51)

Ingénieur géographe honoraire
École nationale des sciences géographiques
Société française de photogrammétrie et télédétection

Hors ligne

 

 

Pages: 1

Pied de page des forums

Powered by FluxBB