Algorithme du point dans un polygone en PHP

L’algorithme du point dans un polygone permet de vérifier par programme si un point particulier est à l’intérieur d’un polygone ou en dehors de celui-ci. Une façon commune d’aborder le problème est de compter combien de fois une ligne tracée à partir du point (dans n’importe quelle direction) croise le bord du polygone. Si la ligne et le polygone se croisent un nombre de fois pair (ou pas du tout), le point est à l’extérieur. S’ils se croisent un nombre de fois impair, le point est à l’intérieur. Ceci est vrai même pour des formes complexes qui ont beaucoup de coordonnées et ont donc un bord très précis.

Voyons un exemple d’image avant de passer au code.

Cette image montre comment on peut déterminer si un point est à l'intérieur ou à l'extérieur d'un polygone.Ici, les lignes tracées à partir du point 1 croisent le bord deux fois ou pas du tout, parce qu’il est à l’extérieur.

Le point 2 est à l’intérieur et donc les lignes croisent le bord une ou trois fois, en fonction de la direction.

Même dans des cas particuliers, tels que le point 3, nous voyons que cette méthode fonctionne : la ligne croise deux fois le bord et le point est donc à l’extérieur.

J’utilise cette approche dans le code PHP ci-dessous, qui retourne l’une de ces 4 valeurs possibles :

  • inside (= dedans) si le point est à l’intérieur du polygone.
  • outside (= dehors) si, vous l’aurez deviné, le point est à l’extérieur du polygone.
  • vertex (= sommet) si le point se trouve exactement sur un sommet ET $pointOnVertex = true (ligne 2)
  • boundary (= bord) si le point est situé sur le bord. Si $pointOnVertex = false, la valeur boundary est également retournée quand le point est sur un sommet.

Utiliser le code PHP du point dans un polygone

Définissez les valeurs du ou des point(s) et un tableau contenant les sommets du polygone (sous la forme « coordonnéeX coordonnéeY »), puis appelez la fonction pointInPolygon. Les premières et dernières coordonnées du polygone doivent être identiques, pour « boucler la boucle ».

Comme vous pouvez le voir dans l’exemple suivant, il est facile vérifier plusieurs points à la fois. Ce code fonctionne également avec des coordonnées négatives, pour le polygone ainsi que pour les points à vérifier.

Point dans un polygone - exempleCeci donnera :

point 1 (50 70): vertex (= sommet)
point 2 (70 40): inside (= dedans)
point 3 (-20 30): inside (= dedans)
point 4 (100 10): outside (= dehors)
point 5 (-10 -10): outside (= dehors)
point 6 (40 -20): inside (= dedans)
point 7 (110 -20): boundary (= bord)

Leave a comment